#P18278. The Best Wife

The Best Wife

The Best Wife

Sofia 想参加一些活动。第 ii 个活动在第 lil_i 天开始、第 rir_i 天结束;如果选择参加,就必须在闭区间 [li,ri][l_i,r_i] 的每一天都参加。

她每天至多参加一个活动。因此,即使一个活动的结束日期恰好等于另一个活动的开始日期,这两个活动也不能同时选择。

活动按顺序逐个出现。对每个 i=1,2,ldots,ni=1,2,ldots,n,请输出只考虑前 ii 个活动时,最多能参加多少个活动。每个前缀可以重新选择最优方案;此前输出不会限制后来的选择。

输入格式

第一行包含一个整数 nn,表示活动数。

接下来 nn 行,每行包含两个整数 li,ril_i,r_i,表示第 ii 个活动的开始、结束日期。

输出格式

输出 nn 行。第 ii 行包含一个整数,表示前 ii 个活动中最多能参加的活动数。

数据范围

  • 1≤n≤3⋅1051\le n\le 3\cdot10^5;
  • 1≤li≤ri≤6⋅1051\le l_i\le r_i\le 6\cdot10^5。

活动可以具有相同的开始、结束日期,也可以完全重复。输入只有一组数据。

样例

5
1 3
3 5
1 2
5 6
4 4
1
1
2
2
3

前两个活动在第 33 天冲突。前三个活动中,可以选择 [1,2][1,2] 和 [3,5][3,5]。全部五个活动中,可以选择 [1,2][1,2]、[4,4][4,4]、[5,6][5,6]。