您被要求组织一次非常重要的艺术会议。第一步是选择日期。
会议必须持续一定的连续天数。每天必须有一位讲师表演,同一位讲师不能表演多次。
您询问 $$$n$$$ 潜在讲师是否可以参加会议。讲师$$$i$$$表示他们可以在$$$l_i$$$到$$$r_i$$$期间的任何一天进行表演。
如果有一种方法可以将某一天的某一天指定为会议日期,则可以为该天的每一天分配一位可用的讲师,为每位讲师分配不超过一天。
对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$k$$$,找出有多少种方法来选择 $$$k$$$ 连续天的一段作为会议日期。
输入
输入的第一行包含一个整数 $$$n$$$ — 潜在讲师的数量 ($$$1 \le n \le 2 \cdot 10^5$$$)。
接下来的 $$$n$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ - 第 $$$i$$$ 位讲师的可用天数 ($$$1 \le l_i \le r_i \le 2 \cdot 10^5$$$)。
输出
打印 $$$n$$$ 整数,其中第 $$$k$$$ 个数字表示选择 $$$k$$$ 连续天的时间段作为会议日期的方式数。
示例
输入 #1
3 1 2 3 4 5 6
输出 #1
6 2 0
输入 #2
5 1 3 1 3 1 3 1 3 1 3
输出 #2
3 2 1 0 0
注意
在第一个测试用例中,可以在 $$$1$$$ 到 $$$6$$$ 之间的任何一天组织为期一天的会议。为期两天的会议可以从$$$2$$$天到$$$3$$$天,以及从$$$4$$$天到$$$5$$$天组织。
在第二个测试用例中,五名讲师只能从$$$1$$$天到$$$3$$$天进行表演,因此不可能组织超过三天的会议。