Description

At the end of a training camp, a group photo is taken with the $N$ participants. The participants are numbered from $1$ to $N$, in order of height. The height of the participant $h$ is $h$ ($1 ≤ h ≤ N$).

The participants stand on the stairs for the photo. There are $N$ steps in the stairs. The steps are numbered from $1$ to $N$, from a lower place to a higher place.

The step $i + 1$ is higher than the step $i$ by $2$ ($1 \leq i \leq N − 1$). Since the steps of the stairs are narrow, only one participant will stand on each step. A group photo will be taken when the participants are lined up behind each other.

A group photo will be taken soon. One participant stands on each step. Now, the participant $H_i$ stands on the step $i$ ($1 \leq i \leq N$).

However, since the difference of the heights of the participants are too large, if a photo is taken with the current order of the participants, some participants might be hidden behind other participants. Hence, you want to change the order of the participants so that at least the head of every participant shows on the photo. In other words, the following condition should be satisfied.

• Let $a_i$ be the height of the participant on the step $i$ ($1 \leq i \leq N$). Then, the inequality $a_i < a_{i+1} + 2$ is satisfied for every $i$ ($1 \leq i \leq N − 1$).

You can only swap two consecutive participants. In other words, by an operation, you choose a step $i$ ($1 \leq i \leq N − 1$) arbitrarily, and you swap the participant on the step i and the participant on the step $i + 1$.

You want to minimize the number of operations so that the above condition is satisfied.

Write a program which, given the order of the participants, calculates the minimum number of operations.

Input

Read the following data from the standard input. Given values are all integers.

$N$
$H_1 \ldots H_N$

Output

Write one line to the standard output. The output should contain the minimum number of operations.

Sample 1

5
3 5 2 4 1

3

The condition is satisfied if you perform three operations as follows.

• First, you swap the participants on the steps $2$ and $3$. The heights of the participants become $3, 2, 5, 4, 1$ from a lower place to a higher place.
• Second, you swap the participants on the steps $4$ and $5$. The heights of the participants become $3, 2, 5, 1, 4$ from a lower place to a higher place.
• Finally, you swap the participants on the steps $3$ and $4$. The heights of the participants become $3, 2, 1, 5, 4$ from a lower place to a higher place. Then the condition is satisfied.

Since the condition is not satisfied if you perform operations less than three times, output $3$.

5
3 2 1 5 4

0

The condition is already satisfied. You do not need to do any operation.

9
6 1 3 4 9 5 7 8 2

9

Constraints

• $3 \leq N \leq 5000$.
• $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.