题目内容

给定一个包含 $n$ 个区间的集合 $intervals$，其中第 $i$ 个区间表示为 $[start_i,end_i]$。

请删除其中尽可能少的区间，使得剩余的所有区间之间互不重叠，并输出需要删除的最少区间数量。

需要注意的是，仅在端点处接触的两个区间不视为重叠。

例如，区间 $[1,2]$ 和区间 $[2,3]$ 互不重叠。

输入描述

第一行输入一个整数 $n$，表示区间的数量。

接下来 $n$ 行，每行输入两个整数 $start_i$ 和 $end_i$，表示第 $i$ 个区间的起点和终点。

约束

$1 \le n \le 10^5$

$-5 \times 10^4 \le start_i < end_i \le 5 \times 10^4$

输出描述

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

样例1

输入

4
1 2
2 3
3 4
1 3

输出

1

说明

删除区间 $[1,3]$ 后，剩余区间为 $[1,2]$、$[2,3]$ 和 $[3,4]$。

这些区间只在端点处接触，因此互不重叠。

所以最少需要删除 $1$ 个区间。

样例2

输入

3
1 2
1 2
1 2

输出

2

说明

三个区间完全相同，因此最多只能保留其中一个区间。

需要删除另外 $2$ 个区间，才能使剩余区间互不重叠。

样例3

输入

2
1 2
2 3

输出

0

说明

区间 $[1,2]$ 和 $[2,3]$ 只在端点 $2$ 处接触，不视为重叠。

因此不需要删除任何区间，输出 $0$。