Longest Leg of the Relay

A regional relay race uses a single electronic baton that beeps and logs a timestamp every time it changes hands. Officials kept a log of exactly n handoffs, each entry recording the runner id who finished a leg and the exact time (in seconds since the starting gun) at which they handed the baton to the next runner. The very first leg begins at time 0, and every later leg begins exactly when the previous leg ended. The same runner id can appear in more than one entry, since a runner may run several legs over the course of the race. Determine the id of the runner who held the baton for the single longest leg; if two or more runners tie for the longest leg, report the smallest such id.

Input format

• Line 1: a single integer n, the number of logged handoffs.
• Each of the next n lines contains two integers id and t, meaning the runner with id id finished a leg at time t. The lines are given in strictly increasing order of t.

Output format

A single integer: the id of the runner with the longest single leg, breaking any tie by reporting the smallest id.

Constraints

• 1 <= n <= 1000
• 0 <= id <= n - 1
• 1 <= t <= 1000
• The values of t strictly increase from line to line.

4
0 3
2 5
0 9
1 15

1

3
0 5
1 10
2 15

0