Maximum Overlapping Intervals

Given n intervals, each represented by a start time and an end time, determine the maximum number of overlapping intervals at any moment.

Formally, for each time t, consider the number of intervals \( [s_i, e_i) \) such that \( s_i \le t < e_i \). Your task is to find the maximum value among these counts, i.e., $$ \max_{t} \#\{i: s_i \le t < e_i\} $$

Note: The intervals are considered half-open, which means that if one interval ends exactly when another begins, they do not overlap.

inputFormat

The input is given via stdin in the following format:

n
s1 e1
s2 e2
... 
sn en

Here, n (1 ≤ n ≤ 10⁵) is the number of intervals. Each of the next n lines contains two space-separated integers s and e (0 ≤ s < e ≤ 10⁹), representing the start and end times of an interval.

outputFormat

Output via stdout a single integer representing the maximum number of overlapping intervals.

5
1 5
2 6
8 10
3 7
5 9

3