CodeCoder vs TopForces#9435
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 thinks that he has a chance to beat citizen in a programming competition if there exists a sequence of Bytelandian citizens A = P_0, P_1, \ldots, P_k = B for some k \ge 1 such that for each (0 \le 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 contains an integer (1 \le n \le 100\,000) - the number of citizens. The following lines contain information about ratings. The -th of them contains two integers CC_i and TF_i - ratings of the -th citizen at CodeCoder and TopForces (1 \le CC_i, TF_i \le 10^6). All the ratings at each site are distinct.
For each citizen 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.
Example 1