Speedrun

Interview

Time limit6sMemory limit1024 MB

Summary

Given N levels where each level points to a next level, find the minimum total time (sum of level numbers) to complete levels until entering a completed one.

Level: Medium4 of 10
Topics: Graph, DFS
Solved: No attempts yet

Problem

The game has $N$ levels numbered from 1 to $N$ . A player can start on any level from 1 to $N$ . For each level $i$ , the level $T_i$ follows it. The player wins as soon as they enter a level that is already completed. Completing every level is not required. Bajtosia can complete every level, and completing level $i$ takes exactly $i$ minutes. Write a program that reads the game description, computes the minimum number of minutes Bajtosia needs to win, and prints it.

Input

The first line contains one natural number $N$ ( $1 \le N \le 100000$ ), the number of levels. The second line contains $N$ integers $T_i$ ( $1 \le T_i \le N$ ) separated by single spaces. The $i$ -th number means that level $T_i$ follows level $i$ .

Output

Print one integer, the minimum number of minutes Bajtosia needs to win.

Examples3

Example 1
Input
```
10
4 1 1 3 4 1 6 9 10 10
```
Expected output
```
8
```
Example 2
Input
```
6
2 3 1 4 6 5
```
Expected output
```
4
```
Example 3
Input
```
7
5 4 1 2 3 7 6
```
Expected output
```
6
```