매년 위스콘신에서는 소들이 미국의 기념일인 할로윈을 기념한다. 소들은 할로윈 복장을 입고 농부 존이 N (1 <= N <= 100000) 개의 마굿간에 남겨놓은 사탕들을 모은다. 곳간이 너무 넓기 때문에 농부 존은 소들에게 그들의 재미를 위해 특정한 경로를 따르도록 지정해주었다. 이 기준을 따르기 위해 소들은 마굿간과 곳간을 왔다갔다해야만 한다. 농부 존은 i 번째 마굿간에 다음에 들러야 할 다음 마굿간의 번호 next_i 를 표시해놓는다. 그러면 소들은 그 규칙을 따르면서 사탕을 모으기 위해서 마굿간과 곳간을 계속해서 왔다갔다 해야한다. 농부 존은 i 번째 소에게 i 번째 마굿간부터 사탕을 모으기 시작하라고 명령했다. 소들은 만약 한 번 방문했던 적이 있는 마굿간에 다시 방문하게 되면 사탕을 모으는 것을 멈춘다. 당신은 각각의 소들이 멈추기 전에 몇 개의 마굿간을 방문하는지 계산해야 한다.

입력

• 첫번째 줄에는 N 이 주어진다.
• 두번째 줄부터 i 번째 마굿간에 대해 next_i 가 주어진다.

출력

입출력 예

입력

4
1
3
2
3

출력

1
2
2
3

입력 설명

4개의 마굿간이 있다.
마굿간 1 다음에는 마굿간 1 을 가야한다.
마굿간 2 다음에는 마굿간 3 을 가야한다.
마굿간 3 다음에는 마굿간 2 을 가야한다.
마굿간 4 다음에는 마굿간 3 을 가야한다.

출력 설명

소 1: 1->1 (1개)
소 2: 2->3->2 (2개)
소 3: 3->2->3 (2개)
소 4: 4->3->2->3 (3개)

출처: usaco 2008 DEC gold
번역: KangJ