题目描述

一条展览长廊中依次安装了编号为 $0,1,\cdots,2n$ 的灯光单元。用序列 $a_0,a_1,\cdots,a_{2n}$ 表示各单元当前显示的主题编号，初始时所有单元均处于默认状态，即 $a_i=0$。

策展团队准备了 $n$ 套灯光覆盖方案。第 $i$ 套方案由两个参数 $l_i,r_i\ (1\le l_i<r_i\le 2n)$ 描述：执行该方案时，会将编号为 $l_i,l_i+1,\cdots,r_i-1$ 的所有灯光单元统一切换为主题 $i$。保证 $l_1,l_2,\cdots,l_n,r_1,r_2,\cdots,r_n$ 这 $2n$ 个端点两两不同。

所有方案都必须执行恰好一次，但你可以自行决定它们的执行顺序。由于后执行的方案会覆盖先前的显示效果，最终长廊会形成若干主题区域。

若相邻两个灯光单元显示的主题不同，即 $a_i\neq a_{i+1}$，则称位置 $i$ 形成了一处分界。请安排方案的执行顺序，使最终分界的数量尽可能多，并求出这个最大值。

输入格式

第一行一个整数 $n$ 。

接下来 $n$ 行，每行两个整数 $l_i,r_i$ 。

输出格式

输出一个整数答案。

样例

样例1

样例输入

5
2 3
6 7
1 9
5 10
4 8

样例输出

9

数据范围与提示

子任务 $1$ （ $9$ 分）： $n\leq 10$ ；
子任务 $2$ （ $21$ 分）： $n\leq 50$ ；
子任务 $3$ （ $33$ 分）： $n\leq 500$ ；
子任务 $4$ （ $37$ 分）： $n\leq 5000$ 。

所有数据： $1\leq n\leq 5\times 10^3$ ， $1\leq l_i < r_i \leq 2n$ ，保证 $l_1,l_2,\cdots,l_n,r_1,r_2,\cdots,r_n$ 互不相同。