問題文

$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$ を含めて) 何種類あるか？

制約

• $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)$ の並び替え
• 入力される数は全て整数である．

入力

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

出力

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

入力例 1

4
1 4
2 3
3 1
4 2

出力例 1

1
1
2
2

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

入力例 2

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

出力例 2

3
3
1
1
2
3
2