Exams

Interview

Time limit1sMemory limit1024 MB

Summary

Given N exams, each occupying minutes a_i up to but excluding b_i, find the largest number of exams that overlap at any single minute.

Level: Easy3 of 10
Topics: Sorting, Intervals
Solved: No attempts yet

Problem

Bitė, a student at Bitlandia University, chose to take many courses this semester. As the semester nears its end, Bitė has to write a large number of exams, so many that some of them overlap in time.

Each exam has a set time when it is written. Bitė types her exams on a computer and wants to know the maximum number of exams she must write at the same time.

Count the maximum number of exams Bitė must write at the same time.

Input

The first line contains the number of exams $N$ . Each of the next $N$ lines contains two integers: the start minute $a_i$ and the end minute $b_i$ of an exam. The last minute of an exam is used to upload the work, and writing is not allowed during that minute.

Output

Print one integer: the maximum number of exams Bitė must write at the same time.

Constraints

$1 \le N \le 100\,000$
$1 \le a_i < b_i \le 1\,000\,000\,000$

Examples1

Example 1
Input
```
4
10 12
10 11
9 10
14 15
```
Expected output
```
2
```