A single shared lab bench receives n reservation requests. Request i asks to use the bench during the half-open time interval [s, e) with s < e. Two requests conflict if their intervals overlap; a request that ends exactly when another begins does NOT conflict (touching at an endpoint is allowed). You may accept any subset of requests as long as no two accepted requests conflict.
Determine the maximum number of requests that can be accepted.
Input format
Line 1: an integer n.
Next n lines: two integers s and e describing one request's half-open interval [s, e).
Output format
A single integer: the maximum number of mutually non-conflicting requests that can be accepted.
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ s < e ≤ 1000000000