Circular Token Sorting

You are given a circular track with n tokens. The tokens are arranged in a circle and each token is labeled with a unique integer from 1 to n. The tokens are initially placed in some order, and your task is to determine the minimum number of moves required to rotate the circular arrangement so that the tokens appear in increasing order (i.e. 1, 2, 3, ..., n). A single move consists of rotating the entire circle by one position. The rotation can be performed in either the clockwise or counterclockwise direction.

Mathematically, given a permutation P of the numbers 1 through n, find the smallest non-negative integer k such that either $$ P_{(i+k)\mod n} = i+1 \quad\text{for all } 0 \leq i < n, $$ or $$ P_{(i-k+n)\mod n} = i+1 \quad\text{for all } 0 \leq i < n. $$ If no such k exists, output -1.

If the tokens are already in sorted order, the answer is 0.

inputFormat

The input consists of two lines:

• The first line contains an integer n (the number of tokens).
• The second line contains n space-separated integers representing the token arrangement on the circle.

outputFormat

Output a single integer: the minimum number of moves required to obtain the sorted order, or -1 if it is impossible.

5
3 4 5 1 2

2