ZigZag Jumps
ZigZag just got a new array \(A\) as a present and has been playing with it all day long. ZigZag uses the array to jump around the elements. He came up with the following rules for his jumps:
ZigZag can only jump from index \(i\) to index \(j\) such that \(j > i\) in the following way:
during odd-numbered jumps (i.e., jumps 1, 3, 5, and so on), you jump to the smallest index \(j\) such that \(A_i < A_j\) and \(A_j - A_i\) is minimal among all possible \(j\)'s.
during even-numbered jumps (i.e., jumps 2, 4, 6, and so on), you jump to the smallest index \(j\) such that \(A_i > A_j\) and \(A_i - A_j\) is minimal among all possible \(j\)'s.
It may be that there is no legal jump for some index \(i\). In this case, the jumping stops.
ZigZag considers the jumps to be satisfying if he can reach the end of the array (i.e., index \(n-1\) where \(n\) is the size of the array) respecting the rules explained above.
ZigZag is now wondering that given an Array \(A\), he can choose any index where he can start his ZigZag jumps following the rules above; how many valid starting positions are there?
Input Specification
The first line of the input consists of an integer \(n\) denoting the number of elements in the array \(A\). The second line of the input contains \(n\) elements of the array such that \(0 \le A_i \le 10^9\).
Output Specification
Print one integer, the number of valid starting positions.
Sample Input
5
10 13 12 14 15Sample Output
2Sample Input
5
10 11 14 11 10Sample Output
2
Comments
Hi programmers,can someone explain to me why the answer of the second sample is 2 .
What is upper bound limit of n??
consider it to be \(n \le 2 \cdot 10^5\)