坐标线上有 $$$n$$$ 段;每个线段的每个端点都有整数坐标。有些段可以退化为点。线段可以相互交叉、相互嵌套甚至重合。
您的任务如下:对于 [1..n]$$$ 中的每个 $$$k \,计算具有整数坐标的点的数量,使得覆盖这些点的线段数量等于 $$$k$$$。当且仅当 $$$l_i \le x \le r_i$$$ 时,具有端点 $$$l_i$$$ 和 $$$r_i$$$ 的线段覆盖点 $$$x$$$。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 段数。
接下来的 $$$n$$$ 行包含段。第 $$$i$$$ 行包含一对整数 $$$l_i, r_i$$$ ($$$0 \le l_i \le r_i \le 10^{18}$$$) — 第 $$$i$$$ 段的端点。
输出
打印 $$$n$$$ 空格分隔的整数 $$$cnt_1, cnt_2, \dots, cnt_n$$$,其中 $$$cnt_i$$$ 等于点的数量,使得覆盖这些点的线段数量等于 $$$i$$$。
示例
输入 #1
3 0 3 1 3 3 8
输出 #1
6 2 1
输入 #2
3 1 3 2 4 5 7
输出 #2
5 2 0
注意
描述第一个示例的图片:
坐标为 $$$[0, 4, 5, 6, 7, 8]$$$ 的点被一段覆盖,点 $$$[1, 2]$$$ 被两段覆盖,点 $$$[3]$$$ 被三段覆盖。
描述第二个示例的图片:
点 $$$[1, 4, 5, 6, 7]$$$ 被一段覆盖,点 $$$[2, 3]$$$ 被两段覆盖,没有点被三段覆盖。