题目描述

$2$ 次元平面上に $N$ 個の街があります。$i$ 個目の街の座標は $(x_i,\ y_i)$ です。ここで、$(x_1,\ x_2,\ \dots,\ x_N)$ と $(y_1,\ y_2,\ \dots,\ y_N)$ は、ともに $(1,\ 2,\ \dots,\ N)$ の順列となっています。

各 $k\ =\ 1,2,\dots,N$ について、以下の問題の答えを求めてください。

rngさんが街 $k$ にいる。 rngさんは、今いる街よりも「$x,\ y$ 座標がともに小さい街」か「$x,\ y$ 座標がともに大きい街」に移動することを好きな回数繰り返すことができる。 rngさんが到達可能な街は、(街 $k$ を含めて) 何種類あるか？

输入格式

$N$ $x_1$ $y_1$ $x_2$ $y_2$ $:$ $x_N$ $y_N$

输出格式

$N$ 行出力する。$i$ 行目には、$k\ =\ i$ のときの答えを出力すること。

题目大意

$2$ 次元维平面上有 $N$ 个点。第 $i$ 个点的坐标是$(x_i,\ y_i)$ 。$(x_1,\ x_2,\ \dots,\ x_N)$ 和 $(y_1，\ y_2，\dots，\ y_N)$ 都是 $(1,\ 2,\ \dots,\ N)$的排列。

对于每个 $k\ =\ 1,2,\dots,N$，到比现在 $(x,\ y)$ 每一个坐标都小或者更大的点的次数，能到达的点有几种（包括点 $k$）？

4
1 4
2 3
3 1
4 2

1
1
2
2

7
6 4
4 3
3 5
7 1
2 7
5 2
1 6

3
3
1
1
2
3
2

提示

制約

• $1\ \leq\ N\ \leq\ 200,000$
• $(x_1,\ x_2,\ \dots,\ x_N)$ は $(1,\ 2,\ \dots,\ N)$ の並び替え
• $(y_1,\ y_2,\ \dots,\ y_N)$ は $(1,\ 2,\ \dots,\ N)$ の並び替え
• 入力される数は全て整数である．

Sample Explanation 1

街 $3$ からは街 $4$ に、また逆に街 $4$ からは街 $3$ へ移動できます。