Problem Description

On the final day of a certain camp, the $N$ participants decided to take a group photo. The participants are numbered from $1$ to $N$ in increasing order of their heights. The height of participant $h$ is $h$ ($1 \leq h \leq N$).

The group photo will be taken on a staircase, which consists of exactly $N$ steps, numbered from $1$ to $N$ in increasing order of height. Step $i + 1$ is exactly $2$ units higher than step $i$ ($1 \leq i \leq N - 1$). The width of the staircase is very narrow, so each step can only accommodate one participant, and they will stand in a single vertical line for the photo.

The photo shoot is about to begin, and each step currently has one participant standing on it. Currently, participant $H_i$ is standing on step $i$ ($1 \leq i \leq N$).

However, due to the significant difference in heights among the participants, some participants might not be visible in the photo. Therefore, you want to rearrange the participants' positions so that at least the top of everyone's head is visible. Specifically, you want to satisfy the following condition:

• Let the height of the participant standing on step $i$ ($1 \leq i \leq N$) be $a_i$. For all $i$ ($1 \leq i \leq N - 1$), $a_i < a_{i + 1} + 2$ must hold.

Note that you can only swap the positions of adjacent participants. That is, in one operation, you can choose any step $i$ ($1 \leq i \leq N - 1$) and swap the participants on step $i$ and step $i + 1$.

You want to achieve this condition with the minimum number of operations.

Given the current arrangement of participants, write a program to find the minimum number of operations required to satisfy the condition.

Input Format

The input is given from the standard input in the following format. All values are integers.

$N$ $H_1$ $H_2$ $\cdots$ $H_N$

Output Format

Output the minimum number of operations required to the standard output in one line.

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/Hints

Constraints

• $3 \leq N \leq 5,000$.
• $1 \leq H_i \leq N$ ($1 \leq i \leq N$).
• $H_i \neq H_j$ ($1 \leq i < j \leq N$).

Subtasks

1. ($5$ points) $N \leq 9$.
2. ($7$ points) $N \leq 20$.
3. ($32$ points) $N \leq 200$.
4. ($20$ points) $N \leq 800$.
5. ($36$ points) No additional constraints.

Sample Explanation 1

You can satisfy the condition with $3$ operations as follows:
- First, swap the participants on step $2$ and step $3$. The heights become $3, 2, 5, 4, 1$.
- Next, swap the participants on step $4$ and step $5$. The heights become $3, 2, 5, 1, 4$.
- Finally, swap the participants on step $3$ and step $4$. The heights become $3, 2, 1, 5, 4$, which satisfies the condition.

It is not possible to satisfy the condition with $2$ or fewer operations, so output $3$.

Sample Explanation 2

The condition is already satisfied, so no operations are needed.

见题面 Input 部分

见题面 Output 部分