스피드런

면접 대비

시간 제한6초메모리 제한1024 MB

요약

각 레벨이 다음 레벨을 가리키는 구조에서, 이미 완료한 레벨에 들어갈 때까지 완료해야 하는 레벨 번호의 합의 최솟값을 구합니다.

난이도: 보통10점 중 4점
유형: 그래프, DFS
정답자: 아직 제출이 없습니다

문제

이 게임에는 1번부터 N번까지 번호가 붙은 N개의 레벨이 있다. 플레이어는 1번부터 N번까지 원하는 레벨에서 게임을 시작할 수 있다. 각 레벨 $i$ 다음에는 레벨 $T_i$ 가 이어진다. 플레이어는 이미 클리어한 레벨에 들어가는 순간 이긴다. 모든 레벨을 클리어할 필요는 없다. 베이토시아는 모든 레벨을 클리어할 수 있으며, 레벨 $i$ 를 클리어하는 데 정확히 $i$ 분이 걸린다. 게임 설명을 읽고, 베이토시아가 이기는 데 필요한 최소 시간(분)을 계산해 출력하는 프로그램을 작성하라.

입력

첫 번째 줄에 레벨 수를 나타내는 자연수 $N$ ( $1 \le N \le 100000$ )이 주어진다. 두 번째 줄에는 한 칸씩 띄워 구분한 $N$ 개의 정수 $T_i$ ( $1 \le T_i \le N$ )가 주어진다. $i$ 번째 수는 레벨 $i$ 다음에 레벨 $T_i$ 가 이어진다는 뜻이다.

출력

베이토시아가 이기는 데 필요한 최소 시간(분)을 정수 하나로 출력한다.

예제3

예제 1
입력
```
10
4 1 1 3 4 1 6 9 10 10
```
예상 출력
```
8
```
예제 2
입력
```
6
2 3 1 4 6 5
```
예상 출력
```
4
```
예제 3
입력
```
7
5 4 1 2 3 7 6
```
예상 출력
```
6
```