题目描述

在二维平面上有 $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$ 坐标的城市。

从城市 $k$ 能够到达多少个城市（包括城市 $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

Rng 可以从城市 $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