CF1965F Conference

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.

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 $ ).

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

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.