[EC 2022年决赛]魔术

题目描述

警告：内存限制异常

您将得到一个序列$a_0，\ldots，a_｛2n｝$。最初，所有数字都为零。

有$n$操作。第$i$个运算由两个整数$l_i，r_i$（$1\le l_i<r_i\le 2n，1\le i\le n$）表示，它将$i$分配给$a_｛l_i｝，\ldots，a_｛r _i-1｝$。保证所有的$2n$整数$l_1，l_2，\ldots，l_n，r_1，r_2，\lots，r_n$是不同的。

每个操作需要按任意顺序执行一次。

您希望最大化i$$（0\leq i<2n）的数量，以便在所有$n$操作之后$a_i\neq a_｛i+1｝$。输出最大数字。

输入格式

第一行包含一个整数$n$（$1\le n\le 5\乘以10^3$）。

接下来$n$行的第$i$行包含一对整数$l_i，r_i$（$1\le l_i<r_i\le 2n$）。保证所有的$2n$整数$l_1，l_2，\ldots，l_n，r_1，r_2，\lots，r_n$是不同的。

输出格式

在一行中输出一个表示答案的整数。