TSSPC Contest 2 P3 - Joe's Dominoes

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 64M

Authors:
Problem type

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)


Comments

There are no comments at the moment.