Problem Description

IOI Zoo is famous for its giraffes. There are $N$ giraffes in the zoo, numbered from 1 to $N$ in increasing order of their heights. The heights of the giraffes are all different. There are $N$ cages arranged in a row, numbered from 1 to $N$ from left to right. Each cage houses one giraffe. The giraffe in cage $i$ is $P_i$.

Mr. APIO, the director of IOI Zoo, is concerned about the zoo's rating. The zoo has received a poor review due to "poor visual appearance of giraffes." Specifically, when a visitor takes a photo with the giraffes, the visitor chooses two integers $l, r$ ($1 \le l \le r \le N$) and takes a photo of the giraffes in cages $l, l+1, \ldots, r$. The visual appearance of these giraffes is considered poor if both of the following conditions are met:

• There exists a giraffe that is taller than both the giraffes at the ends. In other words, there exists an integer $k$ ($l < k < r$) such that $P_l < P_k > P_r$.
• There exists a giraffe that is shorter than both the giraffes at the ends. In other words, there exists an integer $k$ ($l < k < r$) such that $P_l > P_k < P_r$.

Mr. APIO will rearrange the giraffes such that for any choice of $l, r$ ($1 \le l \le r \le N$) by the visitors, the visual appearance of the giraffes will not be poor. Since moving a giraffe from one cage to another is laborious, he wants to minimize the number of giraffes moved. After the rearrangement, each cage should still house exactly one giraffe.

Given the current information about the giraffes, write a program to calculate the minimum number of giraffes that need to be moved. Since Mr. APIO's current arrangement of giraffes is random, you can assume that the values of $P_i$ ($1 \le i \le N$) are generated randomly (see the Data Generation section for detailed information).

Input Format

The first line contains a single positive integer $N$.

The second line contains $N$ positive integers $P_1, P_2, \ldots, P_N$.

Output Format

Output a single integer on one line, representing the minimum number of giraffes that need to be moved.

Sample Input and Output

Sample Input #1

6
5 4 6 1 3 2

Sample Output #1

2

Sample Input #2

4
4 1 3 2

Sample Output #2

0

Sample Input #3

7
3 1 6 7 4 2 5

Sample Output #3

2

Sample Input #4

13
8 5 6 13 4 2 11 3 9 1 10 7 12

Sample Output #4

6

Notes/Hints

Sample Explanation #1

There are 6 giraffes in the IOI Zoo. The giraffes 5, 4, 6, 1, 3, 2 are housed in their respective cages from left to right. With this arrangement, if a visitor takes a photo of the giraffes in cages $l = 2$ to $r = 5$, the visual appearance is poor. Both conditions are met as follows:

• The giraffe in cage 3 is taller than both the giraffes in the leftmost (cage 2) and rightmost (cage 5) cages.
• The giraffe in cage 4 is shorter than both the giraffes in the leftmost (cage 2) and rightmost (cage 5) cages.

If Mr. APIO moves giraffe 1 from cage 4 to cage 1 and giraffe 5 from cage 1 to cage 4, then for any visitor's choice, the visual appearance will not be poor. Mr. APIO achieves this by moving 2 giraffes. Since this is the minimum number of moves, the output is 2.

This sample satisfies the constraints of all subtasks.

Sample Explanation #2

There are 4 giraffes in the IOI Zoo. The giraffes 4, 1, 3, 2 are housed in their respective cages from left to right. With this arrangement, for any visitor's choice, the visual appearance will not be poor. Mr. APIO does not need to move any giraffes, so the output is 0.

This sample satisfies the constraints of all subtasks.

Sample Explanation #3

Taking an example where Mr. APIO arranges the giraffes 3, 5, 6, 7, 4, 2, 1 in their respective cages from left to right. For any visitor's choice, the visual appearance will not be poor. Mr. APIO achieves this by moving 2 giraffes. Since this is the minimum number of moves, the output is 2.

This sample satisfies the constraints of all subtasks.

Sample Explanation #4

This sample satisfies the constraints of subtasks 2, 3, and 4.

Data Range

This problem is bundled test cases.

• Subtask 1 (10 points): $N \le 7$.
• Subtask 2 (22 points): $N \le 13$.
• Subtask 3 (27 points): $N \le 300$.
• Subtask 4 (41 points): No additional constraints.

For all data, $1 \le N \le 8000$, $1 \le P_i \le N$, $P_i$ are all different, and $P_i$ are generated randomly (see the Data Generation section for detailed information).

Data Generation

For this problem, in addition to the sample input, there are 10 test cases satisfying the constraints of subtasks 1, 2, 3, and 4, 10 test cases satisfying the constraints of subtasks 2, 3, and 4, 10 test cases satisfying the constraints of subtasks 3 and 4, and 10 test cases satisfying the constraints of subtask 4. Including the sample, there are a total of 44 test cases for scoring. All 44 test cases are generated as follows:

1. First, generate $N$ satisfying the constraints of the subtask.
2. Then, among the $N! = 1 \times 2 \times \cdots \times N$ valid permutations $(P_1, P_2, \ldots, P_N)$, choose one uniformly at random as $P_1, P_2, \ldots, P_N$.

见题面 Input 部分

见题面 Output 部分