网络脆弱性是指在各种中断情况下（如自然灾害、元件故障或敌对攻击）网络性能下降的程度。网络通常被表示为一个图，其中顶点和边分别对应节点和链路。因此，在这里“网络”和“图”这两个术语可以互换使用。连通度被定义为导致图不连通或成为单顶点图所需删除的最小顶点数，它是评估网络脆弱性最重要的指标。

然而，连通度只能部分反映图对删除顶点的抵抗力。因此，已有许多研究提出了其他指标来衡量网络脆弱性，其中韧性（toughness）和散射数（scattering number）最为流行。韧性和散射数的潜在概念是从图中删除 $k$ 个顶点后产生的最大连通分量数。令 $c_k(G)$ 表示从图 $G$ 中删除恰好 $k$ 个顶点后所能获得的最大连通分量数。遗憾的是，对于给定的图 $G$ 和正整数 $k$，确定 $c_k(G)$ 的问题在计算上是困难的。

然而，对于区间图等某些图类，可以在多项式时间内计算 $c_k(G)$。区间图是实轴上一族（闭）区间的交集图，其中两个顶点当且仅当它们对应的区间相交时才有一条边相连。该区间族通常被称为该图的区间表示。参见图 E.1，了解区间图及其区间表示的示例。

图 E.1：一个区间图及其区间表示。

给定一个具有 $n$ 个顶点的区间图 $G$ 的区间表示，你的任务是编写一个高效的程序，计算所有 $k \in \{0, 1, \dots, n-1\}$ 的 $c_k(G)$。例如，如果给定图 E.1(b) 所示的区间表示，则 $c_0(G), c_1(G), c_2(G), c_3(G), c_4(G), c_5(G), c_6(G), c_7(G)$ 分别为 1, 1, 1, 2, 2, 3, 2, 1。

输入格式

程序应从标准输入读取数据。第一行包含一个正整数 $n$，表示区间的数量，其中 $n \le 2,000$。接下来的 $n$ 行，每行包含一对区间的左端点和右端点。你可以假设区间的左或右端点均为 $-100,000,000$ 到 $100,000,000$ 之间的整数（包含边界）。

输出格式

程序应输出到标准输出。输出一行，包含由 $n$ 个数字组成的序列 $c_0(G), c_1(G), \dots, c_{n-1}(G)$，数字之间用单个空格分隔。

样例

样例输入 1

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

样例输出 1

1 1 1 2 2 3 2 1

样例输入 2

3
-2 -2
-2 7
-2 7

样例输出 2

1 1 1

样例输入 3

4
-1 -1
3 4
5 6
7 8

样例输出 3

4 3 2 1

样例输入 4

5
1 2
2 3
3 4
6 7
7 8

样例输出 4

2 3 3 2 1