CF1027F.Session in BSU

Polycarp studies in Berland State University. Soon he will have to take his exam. He has to pass exactly $n$ exams.

For the each exam $i$ there are known two days: $a_i$ — day of the first opportunity to pass the exam, $b_i$ — day of the second opportunity to pass the exam ($a_i \lt b_i$). Polycarp can pass at most one exam during each day. For each exam Polycarp chooses by himself which day he will pass this exam. He has to pass all the $n$ exams.

Polycarp wants to pass all the exams as soon as possible. Print the minimum index of day by which Polycarp can pass all the $n$ exams, or print -1 if he cannot pass all the exams at all.

波利卡普在贝尔兰国立大学学习。很快他将参加考试，他必须恰好通过 $n$ 门考试。

对于第 $i$ 门考试，已知两个日期：$a_i$ —— 首次可参加该考试的日期，$b_i$ —— 第二次可参加该考试的日期（满足 $a_i \lt b_i$）。波利卡普每天最多只能参加一门考试。对于每门考试，波利卡普自行决定选择哪一天参加。他必须通过全部 $n$ 门考试。

波利卡普希望尽可能早地通过所有考试。请输出波利卡普能通过全部 $n$ 门考试的最早日期的最小索引；若他根本无法通过全部考试，则输出 -1。

The first line of the input contains one integer $n$ ($1 \le n \le 10^6$) — the number of exams.

The next $n$ lines contain two integers each: $a_i$ and $b_i$ ($1 \le a_i \lt b_i \le 10^9$), where $a_i$ is the number of day of the first passing the $i$-th exam and $b_i$ is the number of day of the second passing the $i$-th exam.

输入的第一行包含一个整数 $n$（$1 \le n \le 10^6$）—— 表示考试的场数。

接下来的 $n$ 行每行包含两个整数：$a_i$ 和 $b_i$（$1 \le a_i \lt b_i \le 10^9$），其中 $a_i$ 表示第 $i$ 场考试第一次通过的日期，$b_i$ 表示第 $i$ 场考试第二次通过的日期。

If Polycarp cannot pass all the $n$ exams, print -1. Otherwise print the minimum index of day by which Polycarp can do that.

如果波利卡普无法通过全部 $n$ 场考试，则输出 -1。否则，输出波利卡普能够做到这一点的最早日期的最小索引。