# [EC Final 2022] Magic

## 题意翻译

- 你有一个序列 $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$，**注意空间限制**。

## 题目描述

**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.

## 输入输出样例

### 输入样例 #1

5
2 3
6 7
1 9
5 10
4 8


### 输出样例 #1

9