311286: CF1965F. Conference

F. Conferencetime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

You have been asked to organize a very important art conference. The first step is to choose the dates.

The conference must last for a certain number of consecutive days. Each day, one lecturer must perform, and the same lecturer cannot perform more than once.

You asked $n$ potential lecturers if they could participate in the conference. Lecturer $i$ indicated that they could perform on any day from $l_i$ to $r_i$ inclusive.

A certain segment of days can be chosen as the conference dates if there is a way to assign an available lecturer to each day of the segment, assigning each lecturer to no more than one day.

For each $k$ from $1$ to $n$, find how many ways there are to choose a segment of $k$ consecutive days as the conference dates.

Input

The first line of input contains one integer $n$ — the number of potential lecturers ($1 \le n \le 2 \cdot 10^5$).

Each of the next $n$ lines contains two integers $l_i$ and $r_i$ — the segment of available days for the $i$th lecturer ($1 \le l_i \le r_i \le 2 \cdot 10^5$).

Output

Print $n$ integers, where the $k$th number denotes the number of ways to select a segment of $k$ consecutive days as conference dates.

ExamplesInput

3
1 2
3 4
5 6

Output

6
2
0

Input

5
1 3
1 3
1 3
1 3
1 3

Output

3
2
1
0
0

Note

In the first testcase, a one-day conference can be organized on any of the days from $1$ to $6$. A two-day conference can be organized from day $2$ to day $3$, as well as from day $4$ to day $5$.

In the second testcase, five lecturers can perform only from day $1$ to day $3$, so it will not be possible to organize a conference longer than three days.

题目大意：
您被要求组织一场非常重要的艺术会议。第一步是选择日期。会议必须持续一定数量的连续日子。每天必须有一位讲师进行演讲，且同一位讲师不能多次演讲。您询问了 n 位可能的讲师，他们是否可以参加会议。第 i 位讲师表示他们可以在从 l_i 到 r_i 的任何一天进行演讲。如果能够为某段连续日子中的每一天分配一位可用的讲师，并且每位讲师至多分配一天，则该段日子可以作为会议日期。对于每个 k 从 1 到 n，求出选择 k 连续天作为会议日期的方法数。

输入输出数据格式：
输入：
第一行包含一个整数 n —— 可能的讲师数量 (1 ≤ n ≤ 2 × 10^5)。
接下来 n 行，每行包含两个整数 l_i 和 r_i —— 第 i 位讲师可用的日子段 (1 ≤ l_i ≤ r_i ≤ 2 × 10^5)。

输出：
打印 n 个整数，其中第 k 个数字表示选择 k 连续天作为会议日期的方法数。

示例：
输入：
3
1 2
3 4
5 6

输出：
6
2
0

解释：
- 一天的会议可以在从 1 到 6 的任何一天组织。
- 两天的会议可以从第 2 天到第 3 天组织，也可以从第 4 天到第 5 天组织。

输入：
5
1 3
1 3
1 3
1 3
1 3

输出：
3
2
1
0
0

解释：
- 五位讲师只能在从第 1 天到第 3 天进行演讲，因此不可能组织超过三天的会议。题目大意： 您被要求组织一场非常重要的艺术会议。第一步是选择日期。会议必须持续一定数量的连续日子。每天必须有一位讲师进行演讲，且同一位讲师不能多次演讲。您询问了 n 位可能的讲师，他们是否可以参加会议。第 i 位讲师表示他们可以在从 l_i 到 r_i 的任何一天进行演讲。如果能够为某段连续日子中的每一天分配一位可用的讲师，并且每位讲师至多分配一天，则该段日子可以作为会议日期。对于每个 k 从 1 到 n，求出选择 k 连续天作为会议日期的方法数。 输入输出数据格式： 输入： 第一行包含一个整数 n —— 可能的讲师数量 (1 ≤ n ≤ 2 × 10^5)。 接下来 n 行，每行包含两个整数 l_i 和 r_i —— 第 i 位讲师可用的日子段 (1 ≤ l_i ≤ r_i ≤ 2 × 10^5)。 输出： 打印 n 个整数，其中第 k 个数字表示选择 k 连续天作为会议日期的方法数。 示例： 输入： 3 1 2 3 4 5 6 输出： 6 2 0 解释： - 一天的会议可以在从 1 到 6 的任何一天组织。 - 两天的会议可以从第 2 天到第 3 天组织，也可以从第 4 天到第 5 天组织。 输入： 5 1 3 1 3 1 3 1 3 1 3 输出： 3 2 1 0 0 解释： - 五位讲师只能在从第 1 天到第 3 天进行演讲，因此不可能组织超过三天的会议。