Description

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.

Input Format

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$.

Output Format

Print one integer, the minimum number of operations.

5
3 5 2 4 1

3

5
3 2 1 5 4

0

9
6 1 3 4 9 5 7 8 2

9

Hint

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。

Translated by ChatGPT 5