Minimum Meeting Rooms

Problem: Minimum Number of Meeting Rooms

Given n meeting intervals in intervals, with every interval written as [start, end], determine room usage. Each pair indicates that a meeting begins at start and finishes at end.

Treat every interval as half-open. Therefore, when one meeting finishes exactly at time t and another begins at t, they may be assigned to the same room because they do not overlap.

Find the smallest number of rooms needed to accommodate every meeting.

Input Format

• Line one contains the integer n, which is the count of meetings.
• Each of the following n lines provides two integers, start end, for one meeting's start and finish times.

Output Format

• Output a single integer representing the fewest meeting rooms necessary.

Constraints

• 0 <= n <= 100000
• 0 <= start <= end <= 10^9
• The intervals may appear in any order.

Example

Input:

3
2 14
4 7
9 16

Output:

2

Explanation: The meeting [2,14] intersects with both of the other meetings, so two rooms are required.

Example

Input:
3
1 8
3 5
8 12

Output: 2

Explanation: [1,8] and [3,5] run concurrently, while the meeting starting at 8 can reuse the first room.