Поликарп учится в Берляндском государственном университете. Совсем скоро ему предстоит сдать сессию. Он должен сдать \(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
4000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач