A meeting room is booked with reservations, each a half-open interval [start, end). At some moments many reservations are active at once. Determine the peak concurrency: the largest number of reservations that are simultaneously active at any single instant.
Intervals are half-open, so a reservation that ends exactly when another begins does not count as overlapping at that shared endpoint.
Input format
Line 1: an integer n — the number of reservations.
Next n lines: two integers start end describing one reservation [start, end).
Output format
A single integer: the maximum number of reservations active at the same instant.
Constraints
- 1 <= n <= 100000
- -1000000000 <= start < end <= 1000000000
- Reservations may overlap, nest, or be disjoint.