Children

On the playground a rectangle of unit width and length $n$ is drawn and divided into $n$ square cells. Each cell holds one natural number between $1$ and $n$, and all of the numbers are different (so together they form a permutation of $1$ through $n$). At the start one child stands on each cell. Every minute each child walks to the cell whose number is written on the cell it is currently standing on.

The children grow bored and start thinking about a different question. They want that, over the course of the whole game, every child eventually stands on every cell. To make this happen they may swap the numbers written on two adjacent cells (two cells that sit next to each other in the row). Redrawing the digits takes time, so they want to make as few swaps as possible. Find the minimum number of swaps needed.

The first line contains one integer $n$ ($1 \le n \le 10^6$), the number of square cells. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), where $a_i$ is the number written on the $i$-th cell. All values are distinct, so they form a permutation of $1$ through $n$.

Print a single integer: the minimum number of swaps the children must make.

In the case where $n = 5$ and the cells read $3\ 4\ 1\ 5\ 2$, it is enough to swap the numbers on cells $3$ and $4$. After that a child starting on cell $1$ moves $1 \to 3 \to 5 \to 2 \to 4 \to 1$ and thereby visits every cell, so the minimum number of swaps is $1$.