Stationing

Interview

Time limit1sMemory limit1024 MB

Summary

Place troops in regions to maximize the total number of neighboring regions without troops, where each region links to one other region d_i.

Level: Medium6 of 10
Topics: Dynamic programming, Graph, Tree
Solved: No attempts yet

Problem

Thanks to the driver Haechan, country A was able to win the war against country B. However, A also suffered heavy damage in the war, so A plans to reorganize its army to prepare for B, which may invade at any time.

Country A has $N$ regions. To restore the road network destroyed by the war, each region built one bidirectional road leading to another region. The road built in region $i$ is a bidirectional road that leads to region $d_i$ .

To prepare for an invasion by B, A plans to station troops in each region. However, stationing too many troops reduces their usefulness, so A wants to place the troops efficiently in each region to maximize usefulness. Here, the usefulness of a troop is defined as the number of distinct regions that the troop can reach by using only one road, among those regions where no troop is stationed.

Find the maximum total usefulness when the troops are placed so that the sum of all troops' usefulness is maximized.

Input

The first line contains the number of regions $N$ . $(2 \le N \le 100\,000)$

The second line contains $N$ integers $d_1, \cdots, d_N$ , separated by spaces. Each $d_i$ is the region connected by the bidirectional road built in region $i$ . $(1 \le d_i \le N;\ d_i \neq i)$

Output

Print the maximum possible sum of usefulness over all troops.

Examples1

Example 1
Input
```
6
2 4 1 6 2 5
```
Expected output
```
6
```