C. Circularly
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Luis likes to play with permutations. A permutation is an arrangement of integers such that if its length is $$$N$$$, then each of its elements is between $$$1$$$ and $$$N$$$, and no element appears more than once. For example, $$$[1,3,4,2]$$$ and $$$[1,2]$$$ are permutations, while $$$[1,3,4]$$$ and $$$[1,2,4,2]$$$ are not. In a permutation $$$P$$$ of length $$$N$$$, we denote $$${P[1]}, {P[2]}, \ldots, {P[N]}$$$ as its elements in the order they appear in $$$P$$$. For example, for $$$P=[1,3,4,2]$$$, we have $$$P[3]=4$$$.

Luis is interested in the semi-fixed points of permutations. An integer $$$x$$$ is a semi-fixed point of a permutation $$$P$$$ if $$$P[P[x]]=x$$$. We denote $$$s(P)$$$ as the number of semi-fixed points of the permutation $$$P$$$. For example, for $$$P=[3,6,1,4,2,5]$$$, we have $$$s(P)=3$$$ since $$$1$$$, $$$3$$$, and $$$4$$$ are the semi-fixed points of $$$P$$$.

Luis is also interested in the rotations of permutations. Given a permutation $$$P$$$, $$$\mathop{\mathrm{rot}}\nolimits(P)$$$ is the permutation obtained by rotating $$$P$$$ one position to the left. More generally, $$$\mathop{\mathrm{rot}}\nolimits^k(P)$$$ is the result of rotating the permutation $$$P$$$ exactly $$$k$$$ positions to the left. For example, for $$$P=[1,3,4,2]$$$, we have $$$\mathop{\mathrm{rot}}\nolimits(P)=[3,4,2,1]$$$, $$$\mathop{\mathrm{rot}}\nolimits^2(P)=[4,2,1,3]$$$, and $$$\mathop{\mathrm{rot}}\nolimits^3(P)=[2,1,3,4]$$$.

Luis came up with a brilliant idea: to combine semi-fixed points with rotations. Given a permutation $$$P$$$ of length $$$N$$$, Luis wants to calculate $$$$$$ s(P) + s(\mathop{\mathrm{rot}}\nolimits(P)) + s(\mathop{\mathrm{rot}}\nolimits^2(P)) + \cdots + s(\mathop{\mathrm{rot}}\nolimits^{N-1}(P))$$$$$$ but he does not know how to do it. Would you help him calculate it?

Input

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 2 \cdot 10^5$$$) indicating the length of the permutation.

The second line contains $$$N$$$ distinct integers $$${P[1]}, {P[2]}, \ldots, {P[N]}$$$ ($$$1 \leq P[i] \leq N$$$), the elements of the permutation $$$P$$$.

Output

A line with an integer, the result of the calculation that Luis wants to compute.

Examples
Input
4
1 3 4 2
Output
6
Input
2
1 2
Output
4
Note

In the first example, $$$P=[1,3,4,2]$$$ and its rotations are:

  • $$$P = [1, 3, 4, 2]$$$, with $$$1$$$ semi-fixed point, which is $$$1$$$.
  • $$$\mathop{\mathrm{rot}}\nolimits(P) = [3, 4, 2, 1]$$$, with no semi-fixed points.
  • $$$\mathop{\mathrm{rot}}\nolimits^2(P) = [4, 2, 1, 3]$$$, with $$$1$$$ semi-fixed point, which is $$$2$$$.
  • $$$\mathop{\mathrm{rot}}\nolimits^3(P) = [2, 1, 3, 4]$$$, with $$$4$$$ semi-fixed points, which are $$$1, 2, 3$$$, and $$$4$$$.

Then, $$$s(P) + s(\mathop{\mathrm{rot}}\nolimits(P)) + s(\mathop{\mathrm{rot}}\nolimits^2(P)) + s(\mathop{\mathrm{rot}}\nolimits^{3}(P)) = 1 + 0 + 1 + 4 = 6$$$.