Inviting Friends

Interview

Time limit8sMemory limit512 MB

Summary

Each friend accepts a group size in [ai, bi]; the group includes me, so find the size s maximizing how many intervals contain s, then subtract one.

Level: Medium5 of 10
Topics: Intervals, Sorting, Prefix sum, Greedy
Solved: No attempts yet

Problem

Tomorrow the long-awaited summer vacation begins. So I decided to invite my friends and go to the beach.

But many of my friends are shy. Those people will surely dislike it if they find out that too many people are coming along.

Also, many of my friends like to stand out. Those people will surely dislike it if they find out that too few people are coming along.

And among my friends there are also people who usually like to stand out but are actually shy. Those people will surely dislike it if too many people come along, and also if too few do.

Things like this are more fun with a big group. So I want to invite as many friends as possible. But it is not good to drag along a friend who dislikes it.

How many friends can I invite at most?

I am very bad at this kind of brainy problem. So I have a favor to ask you. If it is all right, could you solve this problem in my place? No, I am not saying you have to. But if you do solve it, I would be very happy.

Input

N
a1 b1
a2 b2
.
.
.
aN bN

The first line of the input contains the integer N (1 ≤ N ≤ 100,000). This represents the number of friends.

The following N lines each contain the integer ai and the integer bi (2 ≤ ai ≤ bi ≤ 100,001), separated by a space. The integers ai and bi on line 1 + i mean that the i-th friend dislikes it unless the number of people going to the beach is at least ai and at most bi. Note that the number of people going to the beach includes "me".

Output

Print the maximum number of friends that can be invited to the beach so that no friend dislikes it.

Examples3

Example 1
Input
```
4
2 5
4 7
2 4
3 6
```
Expected output
```
3
```

Example 2

Input

Expected output

Example 3
Input
```
6
2 9
4 8
6 7
6 6
5 7
2 100001
```
Expected output
```
5
```