Joe is making a domino trail. After placing all the pieces, he decides to change the trail so the heights of the dominoes (strictly) increase then (strictly) decrease. Find the minimum number of dominoes he must remove. (A strictly increasing sequence satisfies ~a_i < a_{i+1}~ and a strictly decreasing sequence satisfies ~a_i > a_{i+1}~).

Input Specification

The first line of input contains a single integer ~N~ ~(3 \leq N \leq 500\,000)~.

The next line contains ~N~ space-seperated integers ~a~ ~(-10\,000 \leq a_i \leq 10\,000)~.

Output Specification

Output the minimum number of dominoes to remove.

The maximal height ~a_j~ must satisfy ~a_{j-1}, a_{j+1} < a_j~.

It is guaranteed that there is at least one valid solution.

Sample Input

10
1 2 3 5 4 6 2 4 3 1

Sample Output

2

Explanation

Joe can remove dominoes ~4~ and ~2~ to get the sequence ~(1,2,3,5,6,4,3,1)~