April Fools Day Contest 2019 A. Thanos Sort

Thanos sort is a supervillain sorting algorithm, which works as follows: if the array is not sorted, snap your fingers* to remove the first or the second half of the items, and repeat the process.

Given an input array, what is the size of the longest sorted array you can obtain from it using Thanos sort?

*Infinity Gauntlet required.

Input

The first line of input contains a single number

The second line of input contains

Output

Return the maximal length of a sorted array you can obtain using Thanos sort. The elements of the array have to be sorted in non-decreasing order.

Examples

Input

Copy

4
1 2 2 4

Output

Copy

Input

Copy

8
11 12 1 2 13 14 3 4

Output

Copy

Input

Copy

4
7 6 5 4

Output

Copy

Note

In the first example the array is already sorted, so no finger snaps are required.

In the second example the array actually has a subarray of 4 sorted elements, but you can not remove elements from different sides of the array in one finger snap. Each time you have to remove either the whole first half or the whole second half, so you'll have to snap your fingers twice to get to a 2-element sorted array.

In the third example the array is sorted in decreasing order, so you can only save one element from the ultimate destruction.

解题思路：就是告诉你有一种算法，它只能整体删除前半部分或者后半部分，使其升序的数目最多，我们可以先判断是否改数列使升序，然后如果不是，则不断递归左半部分和右半部分，取升序数目最大的；

代码如下：

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int n ;
 5 int a[25];
 6 int mmx(int x , int y)
 7 {
 8     int sum = 1;   //注意这里sum从1开始；因为一个数字就算是升序；
 9     int flag = 1;
10     for(int i = x ; i < y ;i++)
11     {
12         if(a[i]<=a[i+1])  //看是否该序列已经升序；
13         {
14             sum++;
15         }else
16         {
17             flag = 0;   //一旦有不升序的就标记；
18         }
19     }
20     if(flag==1)
21     {
22         return sum ;
23     }else
24     if(flag==0)   //不断递归；
25     {
26         int m = (x+y)/2;
27         return max(mmx(x,m),mmx(m+1,y));//取最大；
28     }
29 }
30 int main()
31 {
32     int ans = 0;
33     cin>>n;
34     for(int i = 1 ; i <= n ;i++)
35     {
36         cin>>a[i];
37     }
38     ans = mmx(1,n);
39     cout<<ans;
40 }