题目描述
Problem Description
There are $N$ people, numbered from $1$ to $N$, where the height of the $h$-th person is $h$.
There are $N$ steps, numbered from $1$ to $N$ in increasing order of height, where the $i$-th step is $2$ units lower than the $(i+1)$-th step. Each step can only accommodate one person, and the $H_i$-th person stands on the $i$-th step.
You can perform the following operation any number of times:
- Choose $i \in [1, N-1]$, and swap the person on the $i$-th step with the person on the $(i+1)$-th step.
Assume the height of the person standing on the $i$-th step is $a_i$. You need to satisfy:
- For any $i \in [1, N-1]$, $a_i < a_{i+1} + 2$.
Find the minimum number of operations required.
Input Format
The first line contains an integer $N$ representing the number of people.
The second line contains $N$ integers $H_i$ representing that the $H_i$-th person stands on the $i$-th step.
Output Format
A single line containing an integer representing the minimum number of operations required.
Sample Input and Output
Sample Input #1
5
3 5 2 4 1
Sample Output #1
3
Sample Input #2
5
3 2 1 5 4
Sample Output #2
0
Sample Input #3
9
6 1 3 4 9 5 7 8 2
Sample Output #3
9
Notes
Sample 1 Explanation
Let $h_i$ be the height of the person standing on the $i$-th step:
- Swap the 2nd and 3rd persons, $h_i = \{3, 2, 5, 4, 1\}$.
- Swap the 4th and 5th persons, $h_i = \{3, 2, 5, 1, 4\}$.
- Swap the 3rd and 4th persons, $h_i = \{3, 2, 1, 5, 4\}$.
3 steps are just enough to meet the requirement.
Sample 2 Explanation
The requirement is already met, no operations are needed.
Data Size and Constraints
This problem is bundled.
- 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 special constraints.
For $100\%$ of the data, $3 \le N \le 5000$, $1 \le H_i \le N$, and $H_i$ are distinct.
Notes
Translated from The 20th Japanese Olympiad in Informatics Final Round C Group Photo.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分