ZigZag Jumps

Submit solution

Points: 100
Time limit: 2.0s
Memory limit: 256M

Problem types

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

10 13 12 14 15

Sample Output


Sample Input

10 11 14 11 10

Sample Output



  • 0
    Benelakir  commented on Aug. 26, 2023, 11:23 p.m.

    Hi programmers,can someone explain to me why the answer of the second sample is 2 .

  • 0
    YassirSalama  commented on April 24, 2023, 8:24 p.m.

    What is upper bound limit of n??

    • 0
      AkramElOmrani  commented on April 25, 2023, 12:13 a.m.

      consider it to be \(n \le 2 \cdot 10^5\)