Arkady와 아무것도 아닌 사람들

Arkady는 대기업에서 근무한다. 엄격한 계층 구조의 체계에서 n명의 직원이 근무하고 있다. 즉, CEO을 제외한 각 직원에게는 정확히 한 명의 직속 관리자가 있다. The CEO은 모든 직원의 관리자이다(직속 관리자들의 연쇄를 통해).

각 직원에게는 정수 직급이 있다. The CEO의 직급은 1이고, 다른 각 직원의 직급은 자신의 직속 관리자의 직급에 1을 더한 값이다.

Arkady는 회사에서 좋은 직책을 맡고 있지만, 회사 구조에서 자신이 아무것도 아닌 사람이라고 느끼며 자신을 대체할 수 있는 사람이 많다고 생각한다. 그는 대체 가능성이라는 값을 도입했다. 직원 a와 a의 관리자(직속 관리자일 필요는 없음)인 직원 b를 생각하자. 그러면 b에 대한 a의 대체 가능성 r(a, b)는 관리자 b의 부하 직원(직속 부하일 필요는 없음) 중 직급이 a의 직급보다 크지 않은 직원의 수이다. 대체 가능성 외에도 Arkady는 무시 가능성이라는 값을 도입했다. 직원 a의 무시 가능성 za는 자신의 모든 관리자에 대한 대체 가능성의 합, 즉 이며, 여기서 합은 자신의 모든 관리자 b에 대해 구한다.

Arkady는 자신의 무시 가능성뿐만 아니라 회사의 모든 직원의 무시 가능성에도 관심이 있다. Arkady를 위해 각 직원의 무시 가능성을 구한다.

첫 번째 줄에는 회사의 직원 수를 나타내는 정수 하나 n (1 ≤ n ≤ 5·105)이 주어진다.

두 번째 줄에는 n개의 정수 p1, p2, ..., pn (0 ≤ pi ≤ n)이 주어진다. i-th 직원이 CEO이면 pi = 0이고, 그렇지 않으면 pi는 id가 i인 직원의 직속 관리자의 id와 같다. 직원들은 1부터 n까지 번호가 매겨진다. 이 값들 중 정확히 하나만 0이며, 또한 CEO이 다른 모든 직원의 관리자(직속 관리자일 필요는 없음)임이 보장된다.

모든 직원의 무시 가능성을 id 순서대로 나타내는 n개의 정수 z1, z2, ..., zn을 출력한다.

첫 번째 예제를 살펴보자.

• The CEO에게는 관리자가 없으므로 z1 = 0이다.
• r(2, 1) = 2이다(직원 2와 4는 조건을 만족하지만 직원 3의 직급은 너무 높다). 따라서 z2 = r(2, 1) = 2이다.
• 마찬가지로 z4 = r(4, 1) = 2이다.
• r(3, 2) = 1이다(직원 3은 2의 부하 직원이며 직급이 조건에 맞는다). r(3, 1) = 3이다(직원 2, 3, 4가 조건을 만족한다). 따라서 z3 = r(3, 2) + r(3, 1) = 4이다.