AT_arc159_d [ARC159D] LIS 2
Description
[problemUrl]: https://atcoder.jp/contests/arc159/tasks/arc159_d
数列 $ X $ があります。初め、$ X $ は空です。
高橋君は $ i=1,2,\ldots,N $ の順に次の操作をしました。
- $ X $ の末尾に $ l_i,l_i+1,\ldots,r_i $ をこの順番で追加する。
操作後の $ X $ の狭義単調増加部分列の長さの最大値を求めてください。
Input Format
N/A
Output Format
N/A
Explanation/Hint
### 制約
- $ 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) $ です。