60014 상자 보관 Platinum IV

문제

정올이가 N개의 상자(1부터 N까지 번호)를 창고에 보관하려고 한다. 각 상자 i는 크기 s_i와 보관 용량 c_i를 가지며, c_i < s_i를 만족한다.

상자를 다른 상자 안에 넣을 때의 규칙:

• 보관 용량 이하 크기의 상자를 넣을 수 있음
• 이미 상자를 포함한 상자도 다른 상자에 포함 가능
• 한 상자에 직접 포함되는 상자는 최대 하나 (체인 구조만 가능)

비용은 다른 상자에 포함되지 않은 상자의 개수이다.

i번째 줄에 1번부터 i번 상자까지 보관하는 최소 비용을 출력하시오.

입력

첫째 줄에 N (2 ≤ N ≤ 200,000)이 주어진다.

다음 N줄에 s_i, c_i가 주어진다. (1 ≤ c_i < s_i ≤ 10^9)

출력

N개의 줄에 각각 1~i번 상자의 최소 비용을 출력한다.

4
6 4
5 1
9 8
2 1

1
2
2
2

6
3 2
5 4
3 2
4 3
4 3
3 2

1
1
2
2
2
3