P8425 [JOI Open 2022] Giraffes / Giraffes

**Translated from [JOI Open 2022](https://contests.ioi-jp.org/open-2022/index.html) T2. [キリン](http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2022/giraffes/2022-open-giraffes-statement.pdf) / [Giraffes](http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2022/giraffes/2022-open-giraffes-statement-en.pdf).**

The IOI Zoo is famous for giraffes. There are $N$ giraffes in the IOI Zoo, numbered $1$ to $N$ in increasing order of height. All giraffes have distinct heights. There are $N$ cages arranged in a row, numbered $1$ to $N$ from left to right. Each cage contains exactly one giraffe. Cage $i$ contains giraffe $P_i$. Mr. APIO is the director of the IOI Zoo. He is worried about the zoo’s rating. The IOI Zoo has received bad reviews because “the giraffes look bad”. More precisely, when a visitor takes a photo of 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$. Then, the giraffes in the photo look bad if **both** of the following conditions are satisfied. - There exists a giraffe that is taller than both end giraffes. 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 end giraffes. 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 so that for any choice of $l, r$ ($1 \le l \le r \le N$) by a visitor, the giraffes in the photo will never look bad. Since moving a giraffe from one cage to another is troublesome, he wants to minimize the number of giraffes that are moved. Of course, after moving, each cage must still contain exactly one giraffe. Given the current information about the giraffes, write a program to compute the minimum number of giraffes that need to be moved. Since Mr. APIO’s current arrangement is random, you may assume that the values of $P_i$ ($1 \le i \le N$) are generated randomly (see the **Testdata Generation** section for details).

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

Output one line containing one integer, the minimum number of giraffes that need to be moved.

**Sample Explanation #1.** There are $6$ giraffes in the IOI Zoo. The giraffes $5, 4, 6, 1, 3, 2$ live in cages from left to right in that order. With this arrangement, if a visitor takes a photo with $l = 2, r = 5$, then the giraffes look bad. The two conditions are satisfied as follows. - The giraffe in cage $3$ is taller than the giraffes in the leftmost cage (cage $2$) and the rightmost cage (cage $5$). - The giraffe in cage $4$ is shorter than the giraffes in the leftmost cage (cage $2$) and the rightmost cage (cage $5$). If Mr. APIO moves giraffe $1$ from cage $4$ to cage $1$, and then moves giraffe $5$ from cage $1$ to cage $4$, then no matter what the visitor chooses, the giraffes will not look bad. Mr. APIO achieves the goal by moving $2$ giraffes. Since this is the minimum possible number of moved giraffes, 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$ live in cages from left to right in that order. With this arrangement, for any choice by the visitor, the giraffes will not look bad. 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.** For example, suppose Mr. APIO arranges the giraffes $3, 5, 6, 7, 4, 2, 1$ in cages from left to right in that order. For any choice by the visitor, the giraffes will not look bad. Mr. APIO achieves the goal by moving $2$ giraffes. Since this is the minimum possible number of moved giraffes, 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. ---- **Constraints** **This problem uses bundled testdata.** - 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 testdata, $1 \le N \le 8000$, $1 \le P_i \le N$, all $P_i$ are distinct, and it is guaranteed that $P_i$ is generated randomly (see the **Testdata Generation** section for details). ---- **Testdata Generation** In this problem, besides the sample inputs, 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 samples, there are $44$ test cases in total for scoring. All $44$ test cases are generated as follows: 1. First, generate $N$ that satisfies the subtasks. 2. Then, among the $N! = 1 \times 2 \times \cdots \times N$ permutations $(P_1, P_2, \ldots, P_N)$ that satisfy the constraints, choose one uniformly at random as $P_1, P_2, \ldots, P_N$. Translated by ChatGPT 5