题目描述

数列 $X$ があります。初め、$X$ は空です。
高橋君は $i=1,2,\ldots,N$ の順に次の操作をしました。

• $X$ の末尾に $l_i,l_i+1,\ldots,r_i$ をこの順番で追加する。

操作後の $X$ の狭義単調増加部分列の長さの最大値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $l_1$ $r_1$ $\vdots$ $l_{N}$ $r_{N}$

输出格式

答えを出力せよ。

题目大意

给定 $n$ 个操作，每次操作给出 $l,r$，并在 $a$ 序列里依次添加 $i\in[l,r]$。

求最后 $a$ 的最长上升子序列。

4
1 1
2 4
10 11
7 10

8

4
1 1
1 1
1 1
1 1

1

1
1 1000000000

1000000000

提示

制約

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ l_i\ \leq\ r_i\ \leq\ 10^9$
• 入力はすべて整数

Sample Explanation 1

操作後の $X$ は $(1,2,3,4,10,11,7,8,9,10)$ です。 この数列の $1,2,3,4,7,8,9,10$ 項目からなる部分列は狭義単調増加であり、かつこれが長さが最大のものです。

Sample Explanation 2

操作後の $X$ は $(1,1,1,1)$ です。