Cow Photographs

Farmer John wants to take a single group photo of his entire herd of $N$ cows ($1 \le N \le 100{,}000$), numbered $1$ through $N$, so he can show off to his friends.

On picture day the cows line up in some arbitrary order; the $i$-th position from the left holds the cow numbered $c_i$ ($1 \le c_i \le N$). Since all $N$ cows have distinct numbers, $c_1, c_2, \dots, c_N$ is a permutation of $1 \dots N$.

Farmer John has his own idea of a good photo: the cow immediately to the right of cow $i$ must be cow $i+1$ (for every $1 \le i \le N-1$), and the cow immediately to the right of cow $N$ must be cow $1$. In other words, read from left to right the line must be $s,\ s+1,\ \dots,\ N,\ 1,\ 2,\ \dots,\ s-1$ for some starting cow $s$. There is no cow to the left of the leftmost cow, so the leftmost cow is unconstrained. Call such a line an acceptable lineup.

The cows are hungry for the post-photo dinner, so Farmer John wants to take the picture as quickly as possible. The cows follow directions poorly, so once per minute he may pick one pair of adjacent cows and swap their places. Determine the minimum amount of time, in minutes, needed to reach some acceptable lineup.

For example, suppose $5$ cows start in the order $3\ 5\ 4\ 2\ 1$. Swapping the $5$ and the $4$ gives $3\ 4\ 5\ 2\ 1$, and then swapping the rightmost $2$ and $1$ gives $3\ 4\ 5\ 1\ 2$, which is acceptable. This took $2$ minutes.

• Line $1$: a single integer $N$.
• Lines $2 \dots N+1$: line $i+1$ contains $c_i$, the number of the cow standing in the $i$-th position from the left.

Print a single line: the minimum amount of time, in minutes, that Farmer John needs to get the cows into some acceptable lineup.