시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 117 14 10 19.608%

문제

연종이는 성공한 벤쳐회사 "봉씨"의 사장이다. 가장 처음에 연종이는 이 회사의 유일한 직원이었다. 하지만, 점점 사업이 성공하면서 연종이는 직원을 뽑게 되었고, 이제 연종이를 제외하고 N명의 직원이 일하는 회사가 되었다.

봉씨에서는 직원의 이름을 부르지 않는 문화가 있다. 모든 직원은 서로를 숫자로 불러야 한다. 숫자는 자신이 들어온 순서대로 1번부터 N번까지 번호매겨진다. 연종이의 번호는 0이다.

새로운 직원이 고용될 때, 그 직원은 기존 직원의 부하로 배정된다. 그리고, 그 직원의 첫 월급은 연종이가 능력을 테스트해 본 후에 정해준다. 

만약, 신입 사원의 월급이 그의 상사보다 많다면, 그 상사의 월급은 신입 사원의 월급 만큼 인상된다. 만약, 월급 인상으로 인해 신입 사원의 상사의 월급이 그의 상사 월급보다 많아진다면, 그 상사의 월급도 신입 사원의 월급 만큼 인상된다. 즉, 상사의 월급과 신입 사원의 월급이 같아지는 것이다. 이 작업은 모든 직원이 자신의 상사보다 월급이 작거나 같을 때 까지 반복된다. 

신입 사원이 채용된 순서와 첫 월급, 그리고 상사의 번호가 주어졌을 때, 새로운 직원이 뽑힐 때 마다, 월급 인상을 받는 직원의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 직원의 수 N이 주어진다. (1 ≤ N ≤ 300,000)

둘째 줄에는 연종이의 첫 월급이 주어진다.

다음 N개의 줄에는 직원이 고용된 순서대로 I와 B가 주어진다. I는 첫 월급이고, B는 상사의 번호이다.

모든 월급은 1보다 크거나 같고, 109보다 작거나 같다.

출력

각 직원이 고용됬을 때, 월급 인상 받는 직원의 수를 한 줄에 하나씩 N개의 숫자를 출력한다. 

예제 입력

7
5000
4500 0
6000 0
4000 1
5500 3
7000 4
6300 2
6300 2

예제 출력

0
1
0
2
4
1
0

힌트