Problem Description
Rar the cat wants to hold a party for N people on a certain day. However, each person can only attend the party on certain periods of time. Therefore, Rar the cat has requested 2 integers from all it's attendees, A and B, meaning that this particular attendee can attend the party if it is held between Day A to Day B inclusive. Today will be counted as Day 0 and tomorrow would be Day 1, so on and so forth. (Eg. If today is Monday and A = 1, B = 3. It means that this attendee can attend the party from Tuesday to Thursday)
Rar the cat wants to hold the party on the day where the most number of people can attend, and he wants it as early as possible! As the number of people he has invited is too large for him to manually sort through and devise a suitable day to hold the party. He wants you to code a scheduler, that will tell him when is the earliest possible day where he can hold the party such that the maximum number of people could attend.
However, although a year has only about 365 days and a century has about 36525 days, he wants the scheduler to be able to handle infinitely large numbers of A and B, to avoid the end-of-the-world confusion that when A and B exceeds the integer limit (231), similar to the Mayan calendar.
Input
You are to input from standard input.
The first line of input consists of a single integer, N.
Subsequent N lines will consist of 2 integers each A and B, separated by a single space.
Output
You are to output to standard output.
Output a single integer, the earliest possible day where Rar the cat can hold the party where the most number of people can attend.
Limits
Subtask 1 (4%): N = 2, 0 ≤ A ≤ B ≤ 3000.
Subtask 2 (12%): N ≤ 3000, 0 ≤ A ≤ B ≤ 3000.
Subtask 3 (21%): N ≤ 100000, 0 ≤ A ≤ B ≤ 100000.
Subtask 4 (29%): N ≤ 100000, 0 ≤ A ≤ B ≤ 2000000000.
Subtask 5 (34%): N ≤ 100000, 0 ≤ A ≤ B ≤ 10100.
Subtask 6 (0%): As per sample testcases.
Implementation Details
You are strongly advised to use scanf and printf for this problem due to the large amounts of input. However, you are still allowed to use cin/cout. Invigilators will consider accepting your solution if the maximum execution time borders around the time limit(+10~20%) and has an accepted answer/solution.
Sample Testcase 1
This testcase adheres to the limits of subtask 2 to 5 only.
Input:
5
2 9
9 13
10 13
13 15
11 15
Output:
13
Holding the party on Day 13 will allow 4 people to attend the party, the maximum possible number of people attending.
Sample Testcase 2
This testcase adheres to the limits of subtask 2 to 5 only.
Input:
5
2 9
7 10
8 9
10 13
10 12
Output:
8
Holding the party on Day 8 will have the maximum of 3 people attending. Although holding the party on Day 10 will also result in 3 people attending, Rar the cat wants to hold the party as fast as possible, thus the scheduler should output 8 instead.
Sample Testcase 3
This testcase adheres to the limits of subtask 5 only.
Input:
5
2000000000000000000000000 9000000000000000000000000
7000000000000000000000000 10000000000000000000000000
8000000000000000000000000 9000000000000000000000000
10000000000000000000000000 13000000000000000000000000
10000000000000000000000000 12000000000000000000000000
Output:
8000000000000000000000000
Same reason as Sample Testcase 2, just that A and B in the input are very very large.