CodeCoder vs TopForces
CodeCoder vs TopForces
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.
Input
The first line contains an integer n (1 ≤ n ≤ 100 000) - the number of citizens. The following n lines contain information about ratings. The i-th of them contains two integers CCi
and TFi
- ratings of the i-th citizen at CodeCoder and TopForces (1 ≤ CCi
, TFi
≤ 106
). All the ratings at each site are distinct.
Output
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