Minimum Days to Ping Servers

You are given n servers, each of which can be pinged only during its available time interval. The i-th server can only be pinged on a day within the interval \( [a_i, b_i] \). When pinging servers, you must choose exactly one day for each server. However, there is a twist: you are only allowed to ping a server on the end day of its allowed interval after sorting all intervals in increasing order by their end day. In other words, if you sort the intervals by \( b_i \) then the only possible candidate ping day for each server is its corresponding \( b_i \). A valid schedule exists only if the end days, taken in sorted order, form a strictly increasing sequence. Your task is to determine the minimum last day used in the schedule (which is simply the \( b_i \) of the last interval after sorting) if a valid assignment exists. Otherwise, output -1.

Note: Although other interpretations are possible, for this problem you must use the following rule: sort the \( n \) intervals by their ending day \( b_i \); if for any two consecutive intervals the later one has an end day that is not strictly greater than the previous one (i.e. \( b_{i} \le b_{i-1} \)), then it is impossible to assign distinct ping days following the rule, and you should output -1. Otherwise, output \( b_n \) where \( b_n \) is the end day of the last interval in sorted order.

inputFormat

The input is given from standard input (stdin). The first line contains an integer n (\(1 \le n \le 10^5\)), representing the number of servers. Each of the following n lines contains two space‐separated integers a and b (\(1 \le a \le b \le 10^9\)), where the interval \( [a, b] \) represents the days on which that server can be pinged.

outputFormat

Output a single integer to standard output (stdout): the minimum last day used in the schedule if a valid assignment exists following the rule described above; otherwise, output -1.

2
2 8
3 6

8