P7406 [JOI 2021 Final] Group Photo

There are $N$ people, numbered from $1$ to $N$. The height of person $h$ is $h$. There are $N$ steps, numbered from $1$ to $N$ from lowest to highest. Step $i$ is lower than step $i+1$ by $2$ units of height. Each step can hold at most one person. Person $H_i$ stands on step $i$. You may perform the following operation any number of times: - Choose $i \in [1, N-1]$ and swap the person on step $i$ with the person on step $i+1$. Suppose the height of the person standing on step $i$ is $a_i$. You must make the arrangement satisfy: - For every $i \in [1, N-1]$, $a_i < a_{i+1} + 2$. Find the minimum number of operations.

The first line contains an integer $N$, the number of people. The second line contains $N$ integers $H_i$, meaning that person $H_i$ stands on step $i$.

Print one integer, the minimum number of operations.

#### Explanation for Sample 1 Let $h_i$ be the height of the person standing on step $i$: - Swap person $2$ and person $3$, $h_i = \{3, 2, 5, 4, 1\}$. - Swap person $4$ and person $5$, $h_i = \{3, 2, 5, 1, 4\}$. - Swap person $3$ and person $4$, $h_i = \{3, 2, 1, 5, 4\}$. After exactly $3$ steps, the condition is satisfied. #### Explanation for Sample 2 The condition is already satisfied, so no operations are needed. #### Constraints **This problem uses bundled testdata.** - Subtask 1 (5 pts): $N \le 9$. - Subtask 2 (7 pts): $N \le 20$. - Subtask 3 (32 pts): $N \le 200$. - Subtask 4 (20 pts): $N \le 800$. - Subtask 5 (36 pts): no additional constraints. For all testdata, $3 \le N \le 5000$, $1 \le H_i \le N$, and all $H_i$ are distinct. #### Note Translated from [The 20th Japanese Olympiad in Informatics Final Round C 集合写真 English version: Group Photo](https://www.ioi-jp.org/joi/2020/2021-ho/2021-ho-t3-en.pdf)。 Translated by ChatGPT 5