Minimum Adjacent Swaps to Satisfy Height Constraint

There are (N) people, numbered from (1) to (N), where the height of person (h) is (h). There are also (N) steps, numbered from (1) to (N) in increasing order of height. In particular, the (i)th step is exactly 2 units lower than the (i+1)th step. Initially, the person numbered (H_i) stands on the (i)th step (each step can hold exactly one person).\n\nYou are allowed to perform the following operation any number of times:\n- Choose an index (i) ((1 \le i < N)) and swap the persons on step (i) and step (i+1).\n\nLet (a_i) be the height of the person standing on the (i)th step after some operations. The configuration is called valid if it satisfies (a_i < a_{i+1} + 2) for every (1 \le i < N). Note that when (a_i > a_{i+1}) (i.e. a descent occurs) this condition forces (a_i = a_{i+1} + 1) because the heights are positive integers.\n\nThe task is to determine the minimum number of adjacent swaps required to obtain a valid configuration.

inputFormat

The first line contains a single integer (N) (the number of people and steps).\nThe second line contains (N) distinct integers (H_1, H_2, \dots, H_N) — a permutation of (1,2,\dots,N) indicating that person (H_i) initially stands on step (i).

outputFormat

Output a single integer — the minimum number of adjacent swap operations needed to obtain a configuration where, for every (i) ((1 \le i < N)), the heights satisfy (a_i < a_{i+1} + 2).

sample

3
2 1 3

0