Escape Room Longest Lever Pull

A team is racing through an escape room full of numbered levers. A wall clock silently logs every lever pull as the pair (lever id, elapsed seconds since the room started), and the log is given to you already sorted by elapsed time in strictly increasing order.

The "pull duration" credited to a logged pull is the time elapsed since the previous pull anywhere in the room (or, for the very first logged pull, the time elapsed since the room started at second 0). Formally, if the log entries in order are (id_1, t_1), (id_2, t_2), ..., (id_n, t_n), the pull duration for entry i is t_i - t_{i-1} (using t_0 = 0).

Determine the id of the lever that is credited with the single longest pull duration anywhere in the log. If two or more pulls tie for the longest duration, report the smallest lever id among those tied pulls.

Input format

The first line contains an integer n, the number of logged pulls. Each of the next n lines (or, equivalently, the next 2n whitespace-separated integers) contains two integers id_i and t_i -- the lever pulled and the elapsed time of that pull.

Output format

Print a single integer: the lever id credited with the longest pull duration (smallest id among ties).

Constraints

• 1 <= n <= 100000
• 0 <= id_i <= 100000
• 1 <= t_1 < t_2 < ... < t_n <= 1000000000 (strictly increasing)

3
1 3
2 7
3 8

2

4
2 1
1 2
3 3
2 4

1