Graph Packing

You have recently been selected for a government-funded graph distribution program run by the National Graph Resources Commission and received a functional graph with $N$ vertices. A functional graph is a directed graph in which every vertex has exactly one outgoing edge. Thus, your graph has the same number of vertices and edges.

However, it is common knowledge that preparing so many vertices only to give them the same number of edges is a waste of vertices. You therefore want to pack more edges into this graph. The National Graph Resources Commission also agreed that as many edges as possible should be added to demonstrate that the vertices in this taxpayer-funded graph are being put to good use, and commissioned you to carry out the work.

The Commission knows perfectly well that, without any restrictions, you would simply add a huge number of edges between vertices $1$ and $2$ and call it a day. It has therefore imposed the following rules:

• You cannot add a duplicate edge. In other words, if an edge from vertex $u$ to vertex $v$ already exists, you cannot add another edge from $u$ to $v$.
• Adding an edge must not create a new directed cycle. In other words, if a directed path from vertex $u$ to vertex $v$ already exists in the graph, you cannot add an edge from to . An edge from a vertex to itself is also a cycle.

Given the graph, find the maximum number of additional edges you can add.

The first line contains the number of vertices $N$.

The second line contains $N$ integers separated by spaces. The $u$-th integer $A_u$ means that there is an edge from vertex $u$ to vertex .

Print the maximum number of edges that can be added to the graph.

• $1 \le N \le 200\,000$
• $1 \le A_u \le N$