25423번 - Giraffes 서브태스크다국어

IOI Zoo is famous for giraffes. There are $N$ giraffes in IOI Zoo, numbered from $1$ to $N$ in ascending order of their heights. The heights of the giraffes are different from each other. There are $N$ cages placed in a straight line, numbered from $1$ to $N$ from left to right. In each cage, a giraffe is living in it. The giraffe $P_i$ is living in the cage $i$.

Mr. APIO is the curator of IOI Zoo. He is worrying about the ratings of IOI Zoo in reviews. IOI Zoo receives low ratings for the reason that “the visual quality of the giraffes is bad.” Precisely, when a visitor takes a picture of giraffes, the visitor chooses integers $l$, $r$ ($1 ≤ l ≤ r ≤ N$) and takes a picture of the giraffes in the cages $l, l + 1, \dots ,r$. Then, the visual quality of the giraffes becomes bad if both of the following conditions are satisfied.

• There is a giraffe in the picture which is taller than the giraffes in the both ends of the picture. In other words, there is an integer $k$ ($l < k < r$) satisfying $P_l < P_k > P_r$.
• There is a giraffe in the picture which is shorter than the giraffes in the both ends of the picture. In other words, there is an integer $k$ ($l < k < r$) satisfying $P_l > P_k < P_r$.

Mr. APIO will arrange the positions of the giraffes so that the visual quality of the giraffes does not become bad for any choice of $l$, $r$ ($1 ≤ l ≤ r ≤ N$) when a visitor takes a picture. Since it takes a lot of work to move a giraffe from one cage to another cage, he wants to minimize the number of giraffes which are moved. Of course, after he finishes moving the giraffes, in each cage, a giraffe should be living in it.

Given information of the current positions of the giraffes, write a program which calculates the minimum number of giraffes which are moved. Since Mr. APIO arranged the current positions of the giraffes at random, you may assume that the values $P_i$ ($1 ≤ i ≤ N$) are generated at random (See Generation of Input Data for details).

Read the following data from the standard input. Given values are all integers.

$N$

$P_1 P_2 \cdots P_N$

Write one line to the standard output. The output should contain the minimum number of giraffes which are moved.

• $1 ≤ N ≤ 8\,000$.
• $1 ≤ P_i ≤ N$ ($1 ≤ i ≤ N$).
• $P_i ≠ P_j$ ($1 ≤ i < j ≤ N$).
• The values $P_i$ ($1 ≤ i ≤ N$) are generated at random (See Generation of Input Data for details).

Generation of Input Data

In this task, except for Sample Input, there are 10 test cases which satisfy the constraints of Subtasks 1, 2, 3, 4. Also, there are 10 test cases which satisfy the constraints of Subtasks 2, 3, 4 only, there are 10 test cases which satisfy the constraints of Subtasks 3, 4 only, and there are 10 test cases which satisfy the constraints of Subtask 4 only. In total, including Sample Input, 44 test cases are used for grading. All the 44 test cases for this task are generated by the following way.

1. First, choose $N$ satisfying the constraints of each subtask.
2. Then, among the $N! = 1 × 2 × \cdots × N$ permutations $(P_1, P_2, \dots , P_N)$ satisfying the constraints, choose one permutation at random with equal probability and generate $P_1, P_2, \dots , P_N$.