Polycarp 在 Berland 州立大学学习。很快他就要参加考试了。他必须准确地通过 $$$n$$$ 考试。
对于每项考试 $$$i$$$,已知有两天: $$$a_i$$$ — 第一次有机会通过考试的日期,$$$b_i$$$ — 第二次有机会通过考试的日期 ($$$a_i < b_i$$$)。波利卡普每天最多可以通过一场考试。对于每次考试,波利卡普都会自行选择通过考试的日期。他必须通过所有 $$$n$$$ 考试。
坡旅甲希望尽快通过所有考试。打印 Polycarp 可以通过所有 $$$n$$$ 考试的最小日期索引,或者如果他根本无法通过所有考试,则打印 -1。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 考试数量。
接下来的 $$$n$$$ 行每行包含两个整数:$$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i < b_i \le 10^9$$$),其中 $$$a_i$$$ 是第一个通过第 $$$i$$$ 考试的天数,$$$b_i$$$ 是天数第二次通过第 $$$i$$$ 考试的时间。
输出
如果 Polycarp 无法通过所有 $$$n$$$ 考试,则打印 -1。否则打印 Polycarp 可以做到这一点的最小日期索引。
示例
输入 #1
2 1 5 1 7
输出 #1
5
输入 #2
3 5 13 1 5 1 7
输出 #2
7
输入 #3
3 10 40 40 80 10 80
输出 #3
80
输入#4
3 99 100 99 100 99 100
输出#4
-1