## ZigZag Jumps

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

5
10 13 12 14 15

#### Sample Output

2

#### Sample Input

5
10 11 14 11 10

#### Sample Output

2

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