题目描述

有 $n$ 个空白方格从左到右排成一行，编号以此为$1..n$。小爱可以给每个格子填上一个数字，其中对于编号为 $i$ 的格子，可以填入的数字的范围为给定的 $[l_i,r_i]$。

现在，小爱想知道，如何选择合适的填法，才能使填入后这 $n$ 个数字组成的序列 $a_1,a_2,...,a_n$ 的最长上升子序列上度最长。

输入格式

输入第一行，一个正整数 $n$ 接下来 $n$ 行，每行两个正整数，第$i+1$行表示第$i$个格子填入数字的限制范围 $l_i,r_i$

输出格式

输入一个正整数，表示所能取到的最长上升子序列长度。

6
4 6
3 7
2 3
4 6
1 4
5 9

4

样例解释 1

第一个数字选4，第二个数字选5，第四个数字选6，第六个数字选9，此时构成的上升子序列最长，长度为4

数据范围

• 对于 $30\%$ 的数据 $1\leq n \leq 10$
• 对于 $60\%$ 的数据 $1\leq n\leq 10^3$
• 对于 $100\%$ 的数据 $1\leq n\leq 10^{5}, 1 \leq l_i \leq r_i \leq 10^9$