Dimensional Gate

A dimensional gate is a very convenient means of transport. It looks like an ordinary door, but once you open it and walk through, you arrive in a different space. However, the gates cannot be used in the reverse direction.

ANA country has $N$ cities, numbered $1, 2, \cdots, N$. Insu, a dimensional magician who handles these gates, made one gate leading to each of cities $1, 2, \cdots, N$, numbered each gate $1, 2, \cdots, N$, and installed them one per city at random. The gate installed in city $i$ has number $a_i$, and it leads to city $a_i$.

Insu found that it may be impossible to visit every other city from a given city using only gates. So he plans to cast a spell several times. Each spell swaps the gates of two different cities he chooses. The spell costs mana equal to the square of the difference between the two gate numbers. For example, if city 1 has gate 4 (leading to city 4) and city 4 has gate 6 (leading to city 6), swapping them costs $(4-6)^2=4$ mana.

Find the minimum mana needed to make it possible to visit all other cities from any single city using only gates. Also find how the spells should be cast. The number of spells does not need to be minimal.

The first line contains an integer $N$ ($2 \le N \le 200\,000$).

The second line contains integers $a_1, a_2, \cdots, a_N$ ($1 \le a_i \le N$), separated by spaces.

Print the minimum mana $C$ and the number of spells $M$, separated by a space. The number of spells does not need to be minimal.

From the second line, print $M$ lines in order. Each line contains the two city numbers whose gates are swapped, separated by a space.