시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 6 2 2 50.000%

문제

Competitive programming is very popular in Byteland. In fact, every Bytelandian citizen is registered at two programming sites — CodeCoder and TopForces. Each site maintains its own proprietary rating system. Each citizen has a unique integer rating at each site that approximates their skill. Greater rating corresponds to better skill.

People of Byteland are naturally optimistic. Citizen A thinks that he has a chance to beat citizen B in a programming competition if there exists a sequence of Bytelandian citizens A = P0, P1, . . . , Pk = B for some k ≥ 1 such that for each i (0 ≤ i < k), Pi has higher rating than Pi+1 at one or both sites.

Each Bytelandian citizen wants to know how many other citizens they can possibly beat in a programming competition.

입력

The first line of the input contains an integer n — the number of citizens (1 ≤ n ≤ 100 000). The following n lines contain information about ratings. The i-th of them contains two integers CCi and T Fi — ratings of the i-th citizen at CodeCoder and TopForces (1 ≤ CCi, T Fi ≤ 106). All the ratings at each site are distinct.

출력

For each citizen i output an integer bi — how many other citizens they can possibly beat in a programming competition. Each bi should be printed in a separate line, in the order the citizens are given in the input.

예제 입력

4
2 3
3 2
1 1
4 5

예제 출력

2
2
0
3

힌트