‹ 上一题下一题 ›

j00910. 射爆气球未做

1000 ms 256 MB 测试点 10 通过率 100% J-25·排序 J·算法自拟题排序算法

文件读写输入j00910.in输出j00910.out

题目描述

数轴上有 $n$ 个气球，第 $i$ 个覆盖区间 $[l_{i}, r_{i}]$ （含端点）。一支箭射中坐标 $x$ 会引爆所有满足 $l_{i} \leq x \leq r_{i}$ 的气球。求引爆全部气球的最少箭数。

输入格式

第一行一个整数 $n$ ；接下来 $n$ 行每行两个整数 $l_{i}, r_{i}$ 。

输出格式

一个整数，为最少箭数。

样例

输入

输出

数据范围

$1 \leq n \leq 1 0^{5}$
$0 \leq l_{i} \leq r_{i} \leq 1 0^{9}$

输入

输出

答案