Поликарп учится в Берляндском государственном университете. Совсем скоро ему предстоит сдать сессию. Он должен сдать $$$n$$$ экзаменов.
Для каждого экзамена $$$i$$$ известны два дня: $$$a_i$$$ — день основной сдачи экзамена, $$$b_i$$$ — день пересдачи ($$$a_i < b_i$$$). В один день Поликарп может сдавать не более одного экзамена. Для каждого экзамена Поликарп самостоятельно выбирает, в какой из двух дней его сдать. Необходимо сдать все $$$n$$$ экзаменов.
Поликарп хочет сдать сессию как можно быстрее. Выведите минимальный номер дня, в который Поликарп сможет сдать все $$$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$$$-го экзамена.
Если Поликарп не сможет сдать все $$$n$$$ экзаменов, выведите -1. В противном случае выведите минимальный номер дня, когда Поликарп сможет это сделать.
2
1 5
1 7
5
3
5 13
1 5
1 7
7
3
10 40
40 80
10 80
80
3
99 100
99 100
99 100
-1
Название |
---|