Permutations I

Program time limit: 1 second

Program memory limit: 512 MB

In the kingdom of Numerica, the Grand Bazaar is the highlight of the Odd-Even Festival. Merchants from across the land set up their stalls, each presenting a unique treasure. However, Numerica’s ancient tradition requires these treasures to be arranged in perfect order by the end of the festival.

The stalls are lined up in a single row, numbered from 1 to $N$ . Initially, the treasures are placed in a random order. The festival’s rules dictate a special way in which you can reorder these treasures. This year, the rule is particularly tricky:

The Festival Rules: - You can rearrange the treasures, but only by exchanging them between specific pairs of stalls: two stalls can only swap treasures if they are either both “next to a tree” or both “next to a fountain.” - The stalls alternate between being “next to a tree” and “next to a fountain”.

Your task is to figure out how to place the treasures in ascending order following these rules. If it’s possible, find the minimum number of exchanges needed to accomplish this. If it cannot be done according to the festival’s swapping rules, declare it “IMPOSSIBLE.”

Input

The first line contains an integer $N$, the number of stalls.

The next line contains $N$ integers which is a permutation of $1, 2, \dots, n$, the original ordering of the treasures.

Constraints

For all test cases:

$1 \le N \le 100\;000$.

Output

If is it possible to sort the permutation with the given constraints, output a single integer, the minimum number of swaps required.

Otherwise, output the string IMPOSSIBLE.

In Python, you could use the line print(answer) or print("IMPOSSIBLE").

In C or C++, you could use the line printf("%d\n", answer); or printf("IMPOSSIBLE\n");.

Sample Input 1

5
3 4 5 2 1

Sample Output 1

Explaination 1

   [3, 4, 5, 2, 1]
-> [5, 4, 3, 2, 1]
-> [5, 2, 3, 4, 1]
-> [1, 2, 3, 4, 5]

To sort the permutation with $3$ swaps, we swap values $3$ and $5$, then values $2$ and $4$, then values $1$ and $5$.

Its not possible to sort the permutation with less than $3$ swaps.

Scoring

Your program will be run on the 1 sample case and multiple secret test cases one after another, and if it produces the correct output for all test cases, it solves the task. Recall that your final score on the task is the score of your highest scoring submission.

Submit

Past submissions

You haven't submitted to this task.