题目描述

警告：不寻常的内存限制！

给定一个序列 $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, \ldots, r_n$ 都是不同的。

你需要以任意顺序执行每个操作恰好一次。

你想要最大化满足 $a_i \neq a_{i+1}$ 的 $i$ 的数量（$0 \leq i < 2n$）在所有 $n$ 个操作之后。输出最大数量。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 5 \times 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, \ldots, r_n$ 都是不同的。

输出格式

输出一个整数，表示答案。

5
2 3
6 7
1 9
5 10
4 8

9

提示

题面翻译由 ChatGPT-4o 提供。