Score : $450$ points

问题陈述

有一个有向图，包含 $N$ 个顶点，编号从 $1$ 到 $N$，以及 $N$ 条边。 每个顶点的出度为 $1$，从顶点 $i$ 出发的边指向顶点 $a_i$。 计算顶点对 $(u, v)$ 的数量，使得从顶点 $u$ 可以到达顶点 $v$。

这里，如果存在一个顶点序列 $w_0, w_1, \dots, w_K$，长度为 $K+1$，满足以下条件，则顶点 $v$ 可以从顶点 $u$ 到达。特别是，如果 $u = v$，则总是可以到达。

• $w_0 = u$。
• $w_K = v$。
• 对于每个 $0 \leq i < K$，存在一条从顶点 $w_i$ 到顶点 $w_{i+1}$ 的边。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

There is a directed graph with $N$ vertices numbered $1$ to $N$ and $N$ edges.
The out-degree of every vertex is $1$, and the edge from vertex $i$ points to vertex $a_i$.
Count the number of pairs of vertices $(u, v)$ such that vertex $v$ is reachable from vertex $u$.

Here, vertex $v$ is reachable from vertex $u$ if there exists a sequence of vertices $w_0, w_1, \dots, w_K$ of length $K+1$ that satisfies the following conditions. In particular, if $u = v$, it is always reachable.

• $w_0 = u$.
• $w_K = v$.
• For every $0 \leq i \lt K$, there is an edge from vertex $w_i$ to vertex $w_{i+1}$.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq a_i \leq N$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$

$a_1$ $a_2$ $\dots$ $a_N$

Output

Print the number of pairs of vertices $(u, v)$ such that vertex $v$ is reachable from vertex $u$.

Sample Input 1

4
2 1 1 4

Sample Output 1

8

The vertices reachable from vertex $1$ are vertices $1, 2$.
The vertices reachable from vertex $2$ are vertices $1, 2$.
The vertices reachable from vertex $3$ are vertices $1, 2, 3$.
The vertex reachable from vertex $4$ is vertex $4$.
Therefore, the number of pairs of vertices $(u, v)$ such that vertex $v$ is reachable from vertex $u$ is $8$.
Note that the edge from vertex $4$ is a self-loop, that is, it points to vertex $4$ itself.

Sample Input 2

5
2 4 3 1 2

Sample Output 2

14

Sample Input 3

10
6 10 4 1 5 9 8 6 5 1

Sample Output 3

41