There are n balloons, each covering a closed interval [l, r] on a number line. An arrow shot at coordinate x pops every balloon whose interval contains x (that is, l <= x <= r). Arrows are vertical and travel infinitely, so a single arrow at x pops all balloons spanning x.
Return the minimum number of arrows needed so that every balloon is popped.
Input format
Line 1: an integer n, the number of balloons.
Next n lines: two integers l and r (with l <= r), one balloon per line.
Output format
A single integer: the minimum number of arrows that pops all balloons.
Constraints
- 1 <= n <= 100000
- 0 <= l <= r <= 1000000000