A festival must host n recitals. Recital i runs during the half-open interval [s, e) with s < e. Two recitals can share a room only if they do not overlap in time; a recital that ends exactly when another begins may reuse the same room (touching at an endpoint is fine). Every recital must be assigned to some room.
Find the minimum number of rooms needed so that all recitals can take place.
Input format
Line 1: an integer n.
Next n lines: two integers s and e describing one recital's half-open interval [s, e).
Output format
A single integer: the minimum number of rooms required.
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ s < e ≤ 1000000000