## MOG Training #2## Ended |

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 = P_0, P_1, \ldots, P_k = B$ for some $k \geq 1$ such that for each $i$ ($0 \leq i < k$), $P_i$ has higher rating than $P_{i + 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 \leq n \leq 100\,000$). The following $n$ lines contain information about ratings. The $i$-th of them contains two integers $CC_i$ and $TF_i$ — ratings of the $i$-th citizen at CodeCoder and TopForces ($1 \leq CC_i, TF_i \leq 10^6$). All the ratings at each site are distinct.

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

Input

4
2 3
3 2
1 1
4 5

Output

2
2
0
3