Description

给定一个区间的集合 $\mathit{intervals}$ ，其中 $\mathit{intervals}[i] = [\mathit{start}_i, \mathit{end}_i]$ 。输出需要移除区间的最小数量，使剩余区间互不重叠。

注意：如果前一个区间的结束时间和后一个区间的开始时间相等，则它们不算重合。

Format

Input

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

接下来第 $i+1$ 行表示第 $i$ 个区间的开始时间与结束时间。

Output

输出一个整数，表示需要移除区间的最小数量。

Samples

4
1 2
2 3
3 4
1 3

1

移除 $[1,3]$ 后，剩下的区间没有重叠。

3
1 2
1 2
1 2

2

你需要移除两个 [1,2] 来使剩下的区间没有重叠。

2
1 2
2 3

0

你不需要移除任何区间，因为它们已经是无重叠的了。

Limitation

对于前 $10\%$ 的数据，$n\le 10$

对于前 $20\%$，$n\le30$；

对于前 $40\%$，$n\le 100$

对于前 $50\%$，$n\le1000$

对于前 $60\%$，$n\le10000$

对于前 $80\%$，$n\le100000$

对于 $100\%$ 的数据，$1\le n\le 1000000$，$1\le \mathit{start}_i\le\mathit{end}_i\le 2\times10^9$。

1s, 128MiB for each test case.