Problem Description
Rar the cat has been observing mountains and has recorded the heights of a particular mountain range at every specific interval and recorded them into a list, forming a landscape. Now, he wants to process these data in order to make a better interpretation of the landscape. To do so, Rar the cat has decided to identify peaks. Rar the cat consider a place as a 1st-degree peak if the heights of the surroundings are strictly lower than itself. (Eg. 2 7 3, 7 will be the peak).
However this is not enough! A 1st-degree peak can be 'upgraded' to a 2nd-degree peak if the 2 adjacent 1st-degree peaks are lower than it. For example: If the heights recorded of the landscape are 2 5 3 7 4 1 6 2, then the 1st-degree peaks would be 5, 7 and 6. Since the 2 adjacent 1st-degree peaks of 7 is lower than itself, 7 is considered a 2nd-degree peak but 5 and 6 are still 1st-degree peaks.
Extending this rule, a X-degree peak can be 'upgraded' to a X+1-degree peak if the 2 adjacent X-degree peaks are lower than it.
Given the landscape, Rar the cat wants to know the degree of the highest degree peak.
Input
A single integer, N. N denotes the number of positive integral heights that Rar the cat has recorded.
The following line consists of N integers, with each being in the range of 1 to 1000000000.
Output
Output a single integer, the degree of the highest degree peak. If there are no 1st-degree peaks at all, then output 0 instead.
Limits
Subtask 1 (35%): 0 < N ≤ 5000
Subtask 2 (65%): 0 < N ≤ 3000000
Subtask 3 (0%): As per sample testcases.
Sample Testcase 1
Input:
8
2 5 3 7 4 1 6 2
Output:
2
Sample Testcase 2
Input:
8
1 2 3 4 5 6 7 8
Output:
0