配点 : $300$ 点

問題文

$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$ のときの答えを出力すること。

4
1 4
2 3
3 1
4 2

1
1
2
2

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

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

3
3
1
1
2
3
2