题目描述

Warning: Unusual memory limit!

You are given a sequence $a_0,\ldots,a_{2n}$. Initially, all numbers are zero.

There are $n$ operations. The $i$-th operation is represented by two integers $l_i, r_i$ ($1\le l_i < r_i\le 2n, 1\le i\le n$), which assigns $i$ to $a_{l_i},\ldots,a_{r_i-1}$. It is guaranteed that all the $2n$ integers, $l_1,l_2,\ldots, l_n, r_1, r_2, \ldots, r_n$, are distinct.

You need to perform each operation exactly once, in arbitrary order.

You want to maximize the number of $i$ $(0\leq i< 2n)$ such that $a_i\neq a_{i+1}$ after all $n$ operations. Output the maximum number.

输入格式

The first line contains an integer $n$ ($1\le n\le 5\times 10^3$).

The $i$-th line of the next $n$ lines contains a pair of integers $l_i, r_i$ ($1\le l_i < r_i\le 2n$). It is guaranteed that all the $2n$ integers, $l_1,l_2,\ldots, l_n, r_1, r_2, \ldots, r_n$, are distinct.

输出格式

Output one integer representing the answer in one line.

题目大意

• 你有一个序列 $a_0,a_1,a_2\dots a_{2n}$，初始全为 $0$。
• 给定 $n$ 个区间赋值操作，第 $i$ 个操作 $(l_i,r_i)(1\le l_i,r_i\le 2n)$ 表示把区间 $[l_i,r_i)$ 全部赋值为 $i$，保证所有 $l_i,r_i$ 互不相同。
• 你可以指定一个执行操作的顺序，最大化 $\sum_{i=0}^{2n-1}[a_i\ne a_{i+1}]$，输出这个最大值。
• $1\le n\le 5\times 10^3$，注意空间限制。

5
2 3
6 7
1 9
5 10
4 8

9