402511: GYM100796 E Permutation Polygon

There are n cities in Regularia, Alice's homeland. They are located at the vertices of a regular n-gon. The cities are numbered from 1 to n in a clockwise order (see the figure).

The people of Regularia love Alice so much that they made her the queen of the country. Alice wants to prove herself, so she has ordered a construction of a new highway system connecting cities of Regularia. Alice has come up with a plan to build the highways, which is an n-permutation p₁, p₂, ..., p_n. Specifically, for a city numbered i, Alice wants to build a highway between the cities i and p_i, where p_i is the number of some other city. A highway is a straight line connecting two cities. According to Alice's plan, any two cities will be connected by no more than a single highway.

Of course, some of the highways may intersect one another. Two highways are said to intersect if and only if there is a unique point that belongs to both of the highways and is not a city. This point is called a junction of the two highways. Even if more than two highways meet at a single point, each pair has its own separate junction. As a complicated and expensive interchange has to be built at each junction, Alice is interested in the total number of junctions in her plan. Help her find this number!

For example, the plan for a permutation 4, 1, 5, 3, 2 is shown in the figure.

The first line contains a single integer n, the number of cities in Regularia (3 ≤ n ≤ 10⁵). The next line contains n space-separated integers p₁, p₂, ..., p_n, which is a permutation of length n. It is guaranteed that i ≠ p_i for any i and that no two cities will be connected by more than a single highway.

Output a single integer — the total number of junctions in Alice's plan.

5
4 1 5 3 2

2

6
4 5 6 3 1 2

6

A permutation of length n is any rearrangement of the sequence 1, 2, ..., n.