题目描述

给定一个集合，其中包含若干个区间。每个区间由一对整数对 $(l, r)$ 表示，其中 $l$ 表示区间的开始，$r$ 表示区间的结束，并且 $l < r$。

你的任务是移除最少数量的区间，使得剩余的区间之间没有重叠。

输入格式

第一行一个整数 $N$，表示区间的数量。

接下来 $N$ 行，每行两个整数 $l$ 和 $r$，表示一个区间的开始和结束。

输出格式

输出一个整数，表示为了使剩余的区间没有重叠，需要移除的最少区间数量。

样例

4
1 3
2 4
3 5
6 8

1

解释

我们可以移除区间 $[2, 4]$，这样剩下的区间 $[1, 3]$、$[3, 5]$ 和 $[6, 8]$ 就没有重叠。

数据范围

• $1 ≤ N ≤ 100000$
• $-10^4 ≤ l < r ≤ 10^4$