26164번 - 싱싱미역

문제

원주 위에 서로 다른 2ドルN$개의 점 $P_1, P_2, \ldots, P_{2N}$이 있다. 단, $N$은 짝수인 양의 정수, 다각형 $P_1P_2\cdots P_{2N}$은 정다각형이다.

리프는 싱싱한 미역 $\frac{N}{2}$개를 펼쳐서 원 위에 놓았다. 모든 미역은 현 $P_{2i}P_{2j}$와 같은 형태로 생각할 수 있다. ($i, j$는 $N$ 이하의 양의 정수, $i \neq j$) 어떤 서로 다른 두 미역을 골라도 끝점을 공유하지 않는다.

리프는 미역국을 만들어 먹으려고 한다. 어떤 미역의 집합 $S$에 대해, $S$의 임의의 두 원소의 교점이 항상 존재한다면 집합 $S$를 맛있는 미역국 집합이라고 하자.

리프는 원래 원 위에 있던 $\frac{N}{2}$개의 미역 중 몇 개를 골라 미역국을 만들어 먹으려고 했지만, 리프의 친구인 트온이 최고급 싱싱미역 1개를 선물해줬다. 리프는 최고급 싱싱미역을 현 $P_1P_{2x+1}$ 형태로 원 위에 올려둔 다음, 최고급 싱싱미역을 원소로 가지면서 원소의 개수가 최대인 맛있는 미역국 집합 $S_x$를 만들려고 한다. ($x$는 $N-1$ 이하의 양의 정수) 맛있는 미역국을 최대한 많이 먹고 싶은 리프는 최고급 싱싱미역을 어디에 두어야 할지 궁금해졌다. 리프를 위해 $S_1, S_2, \ldots, S_{N-1}$의 크기를 전부 구해주자.

입력

첫 번째 줄에 정수 $N$이 주어진다.

두 번째 줄에 $N$개의 서로 다른 정수 $A_1, A_2, \ldots, A_N$이 주어진다. $A_i = j$라면 현 $P_{2i}P_{2j}$와 일치하는 미역이 존재한다는 뜻이다.

출력

첫 번째 줄에 $N-1$개의 정수 $|S_1|, |S_2|, \ldots, |S_{N-1}|$을 공백으로 구분하여 출력한다.

제한

• 2ドル \le N \le 10^5$
• 1ドル \le A_i \le N$
• $N$은 짝수
• $A_i \neq A_j$ (1ドル \le i < j \le N$)
• $A_i = j$이면 $A_j = i$ (1ドル \le i, j \le N$)
• $A_i \neq i$ (1ドル \le i \le N$)

힌트