Chorale Formation

There are n students standing in a line. The music teacher wants to ask some of them to step out so that the remaining students form a chorale formation. A chorale formation is defined as follows: assume the remaining k students are numbered from 1 to k from left to right with heights t₁, t₂, ..., t_k. There must exist an index i (1 ≤ i ≤ k) such that:

$$t_1 < t_2 < \cdots t_{i+1} > \cdots > t_k$$

Your task is to determine the minimum number of students that need to be asked to step out so that the remaining ones (in their original left-to-right order) form a chorale formation. Equivalently, if you can find a longest subsequence of students that forms a bitonic sequence (strictly increasing then strictly decreasing, where a purely increasing or purely decreasing sequence is allowed by taking i = k or i = 1 respectively), then the answer is the total number of students n minus the length of this subsequence.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 1000), the number of students.

The second line contains n space-separated integers representing the heights of the students.

outputFormat

Output a single integer representing the minimum number of students that need to step out to form a valid chorale formation.

sample

6
1 2 3 4 3 1

0