You are scheduling n meetings, each described by a half-open time interval [start, end) (a meeting occupies a room at every instant t with start ≤ t < end). Two meetings that only touch at an endpoint — one ending exactly when another begins — can reuse the same room and do not conflict.
Compute the minimum number of rooms required so that every meeting has a room for its entire duration.
Input format
Line 1: an integer n — the number of meetings.
Next n lines: each contains two integers start end with start < end.
Output format
A single integer: the minimum number of rooms needed.
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ start < end ≤ 1000000000