Yan Hao 有 $n$ 把剑,编号从 $1$ 到 $n$。第 $i$ 把剑的攻击力为 $a[i]$,防御力为 $b[i]$。
Yan Hao 认为,如果存在另一把剑 $j$ ($j \neq i$),使得 $a[i] \leq a[j]$ 且 $b[i] \leq b[j]$,那么剑 $i$ 就是“无用”的。也就是说,如果另一把剑 $j$ 的攻击力和防御力都至少不弱于剑 $i$,则剑 $i$ 是无用的。如果一把剑不是无用的,我们称它是“有用”的。
如果两把剑的攻击力和防御力完全相同,则认为它们是等价的。题目保证没有任何两把剑是等价的。
请帮助 Yan Hao 找出他收藏中“有用”剑的数量。
输入格式
程序必须从标准输入读取数据。
第一行包含一个整数 $n$。
接下来的 $n$ 行,每行包含两个空格分隔的整数。第 $i$ 行输入包含 $a[i]$ 和 $b[i]$,分别表示第 $i$ 把剑的攻击力和防御力。
输出格式
程序必须输出到标准输出。
输出应包含一个整数,即“有用”剑的数量。
输出仅包含一个整数。不要打印任何额外文本,例如 “Enter a number” 或 “The answer is”。
数据范围
对于所有测试用例,输入满足以下限制:
- $1 \leq n \leq 100\,000$
- $1 \leq a[i], b[i] \leq 10^9$
- 对于所有 $1 \leq i < j \leq n$,$a[i] \neq a[j]$ 或 $b[i] \neq b[j]$
你的程序将在满足以下限制的输入实例上进行测试:
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 11 | $n \leq 500$ |
| 2 | 21 | $a[i], b[i] \leq 500$ |
| 3 | 34 | $a[i] = i$ |
| 4 | 25 | 对于每个 $1 \leq i < j \leq n$,$a[i] \neq a[j]$ |
| 5 | 9 | 无附加限制 |
样例
样例输入 1
3 2 3 1 3 5 3
样例输出 1
1
说明 1
比较剑 1 和剑 3,我们有 $a[1] = 2 \leq 5 = a[3]$ 且 $b[1] = 3 \leq 3 = b[3]$,所以剑 1 是无用的。
比较剑 2 和剑 1,我们有 $a[2] = 1 \leq 2 = a[1]$ 且 $b[2] = 3 \leq 3 = b[1]$,所以剑 2 是无用的。
剑 3 是唯一有用的剑。
样例输入 2
4 5 6 2 5 6 9 1 3
样例输出 2
1