题目描述

有一个数列 $X$，初始时 $X$ 为空。
高桥君依次进行了 $i=1,2,\ldots,N$ 的如下操作：

• 将 $l_i,l_i+1,\ldots,r_i$ 按顺序依次添加到 $X$ 的末尾。

请你求出操作结束后，$X$ 的严格单调递增子序列的最大长度。

输入格式

输入以如下格式从标准输入给出。

$N$
$l_1$ $r_1$
$\vdots$
$l_N$ $r_N$

输出格式

请输出答案。

样例 1

输入

4
1 1
2 4
10 11
7 10

输出

8

样例 2

输入

4
1 1
1 1
1 1
1 1

输出

1

样例 3

输入

1
1 1000000000

输出

1000000000

说明/提示

限制条件

• $1\leq N\leq 2\times 10^5$
• $1\leq l_i\leq r_i\leq 10^9$
• 输入均为整数。

样例解释 1

操作结束后 $X$ 为 $(1,2,3,4,10,11,7,8,9,10)$。该数列中由第 $1,2,3,4,7,8,9,10$ 项组成的子序列是狭义单调递增的，并且这是长度最大的。

样例解释 2

操作结束后 $X$ 为 $(1,1,1,1)$。

由 ChatGPT 4.1 翻译