You are given n intervals, each written as [start, end) — half-open, including start but excluding end. Two intervals overlap when they share any point that lies strictly inside both; intervals that merely touch at an endpoint (one ends exactly where another begins) do not overlap and may both be chosen.
Select as many intervals as possible so that no two selected intervals overlap, and print the size of the largest such selection.
Input format
Line 1: an integer n, the number of intervals.
Next n lines: two space-separated integers start end describing one interval [start, end) with start < end.
When n = 0, no interval lines follow.
Output format
A single integer: the maximum number of pairwise non-overlapping intervals that can be chosen.
Constraints
- 0 <= n <= 100000
- -1000000000 <= start < end <= 1000000000