在字节兰（Byteland），程序设计竞赛非常流行。事实上，每位字节兰公民都在两个编程网站注册了账号——CodeCoder 和 TopForces。每个网站都维护着自己专有的评分系统。每位公民在每个网站都有一个唯一的整数评分，用以近似衡量他们的技术水平。评分越高，代表技术水平越好。

字节兰的人民天生乐观。公民 $A$ 认为，如果存在一个字节兰公民序列 $A = P_0, P_1, \dots, P_k = B$（其中 $k \ge 1$），且对于每个 $i$（$0 \le i < k$），$P_i$ 在至少一个网站上的评分高于 $P_{i+1}$，那么公民 $A$ 就有机会在程序设计竞赛中击败公民 $B$。

每位字节兰公民都想知道，在程序设计竞赛中，他们可能击败的其他公民人数是多少。

输入格式

输入的第一行包含一个整数 $n$ —— 公民人数（$1 \le n \le 100\,000$）。接下来的 $n$ 行包含评分信息。第 $i$ 行包含两个整数 $CC_i$ 和 $TF_i$ —— 第 $i$ 位公民在 CodeCoder 和 TopForces 上的评分（$1 \le CC_i, TF_i \le 10^6$）。每个网站上的所有评分均不相同。

输出格式

对于每位公民 $i$，输出一个整数 $b_i$ —— 他们可能击败的其他公民人数。每个 $b_i$ 应按输入中给出的公民顺序，在单独的一行中打印。

样例

输入 1

4
2 3
3 2
1 1
4 5

输出 1

2
2
0
3