Group Photo
Time limit4sMemory limit512 MB
Given a permutation of heights on steps with rise 2, swap adjacent participants to reach an order where a_i < a_{i+1} + 2 for all i, minimizing swaps.
Problem
At the end of a training camp, N participants gather for a group photo. The participants are numbered 1 through N in order of height. The height of participant h is h (1 ≤ h ≤ N).
The participants stand on a staircase for the photo. The staircase has N steps. The steps are numbered 1 through N from the bottom to the top.
Step i + 1 is higher than step i by 2 (1 ≤ i ≤ N − 1). Because the steps are narrow, only one participant stands on each step. The group photo is taken with the participants lined up one behind another.
The group photo will be taken soon. Right now, one participant stands on each step. Participant H_i stands on step i (1 ≤ i ≤ N). However, the differences in the participants' heights are so large that if the photo is taken in the current order, some participants might be hidden behind others. So you want to change the order of the participants so that at least the head of every participant shows in the photo. In other words, the following condition must be satisfied.
Let a_i be the height of the participant on step i (1 ≤ i ≤ N). Then the inequality a_i < a_{i+1} + 2 must hold for every i (1 ≤ i ≤ N − 1).
You may swap only two adjacent participants. That is, in one operation, you choose a step i (1 ≤ i ≤ N − 1) arbitrarily and swap the participant on step i with the participant on step i + 1.
You want to minimize the number of operations needed to satisfy the condition above.
Write a program that, given the order of the participants, computes the minimum number of operations.
Input
Read the following data from standard input. All given values are integers.
N
H1 · · · HN
Output
Write one line to standard output. The output must contain the minimum number of operations.
Constraints
- 3 ≤ N ≤ 5 000.
- 1 ≤ Hi ≤ N (1 ≤ i ≤ N).
- Hi ≠ Hj (1 ≤ i < j ≤ N).