A - Reachable Towns 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

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

入力例 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

Score : 300 points

Problem Statement

There are N cities on a 2D plane. The coordinate of the i-th city is (x_i, y_i). Here (x_1, x_2, \dots, x_N) and (y_1, y_2, \dots, y_N) are both permuations of (1, 2, \dots, N).

For each k = 1,2,\dots,N, find the answer to the following question:

Rng is in City k. Rng can perform the following move arbitrarily many times:

  • move to another city that has a smaller x-coordinate and a smaller y-coordinate, or a larger x-coordinate and a larger y-coordinate, than the city he is currently in.

How many cities (including City k) are reachable from City k?

Constraints

  • 1 \leq N \leq 200,000
  • (x_1, x_2, \dots, x_N) is a permutation of (1, 2, \dots, N).
  • (y_1, y_2, \dots, y_N) is a permutation of (1, 2, \dots, N).
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

Print N lines. In i-th line print the answer to the question when k = i.

Sample Input 1

4
1 4
2 3
3 1
4 2

Sample Output 1

1
1
2
2

Rng can reach City 4 from City 3, or conversely City 3 from City 4.

Sample Input 2

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

Sample Output 2

3
3
1
1
2
3
2