Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

F. Сессия в БГУ
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп учится в Берляндском государственном университете. Совсем скоро ему предстоит сдать сессию. Он должен сдать $$$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