Студент Валера учится на первом курсе университета. Скоро у него сессия, и ему предстоит сдать ровно n экзаменов. Валера — умный парень, поэтому он сможет сдать любой экзамен с первого раза. Кроме того, он может сдавать несколько экзаменов в один день и в любом порядке.
Согласно расписанию, экзамен по i-му предмету нужно сдать в день с номером ai. Однако Валера договорился с каждым преподавателем, и преподаватель i-го предмета разрешил организовать досрочную сдачу своего экзамена в день bi (bi < ai). Таким образом, Валера может сдать экзамен по i-му предмету либо в день ai, либо в день bi. Все преподаватели ставят запись о сдаче экзамена в зачетную книжку в день фактической сдачи экзамена и датируют эту запись числом ai.
Валера считает, что будет достаточно странно, если записи в зачетной книжке будут идти не в порядке неубывания даты. Поэтому Валера просит вас помочь ему. Найдите минимально возможный номер дня, когда Валера сможет сдать последний экзамен, если он будет сдавать экзамены так, чтобы все записи в его зачетной книжке шли в порядке неубывания даты.
Выходные данные
Выведите единственное целое число — минимально возможный номер дня, когда Валера сможет сдать последний экзамен, если он будет сдавать экзамены так, чтобы все записи в его зачетной книжке шли в порядке неубывания даты.
Примечание
В первом примере Валера сначала сдаст экзамен по второму предмету в первый день (в зачетную книжку заносится дата сдачи по расписанию, то есть 3). На следующий день сначала он сдаст экзамен по третьему предмету (будет добавлена запись, датированная днем 4), а после него в тот же день сдаст экзамен по первому предмету (в зачетную книжку отметка будет проставлена с днем 5). Таким образом, последний экзамен Валера сдаст во второй день, и даты в зачетной книжке будут идти в порядке неубывания: 3, 4, 5.
Во втором примере Валера сначала сдаст экзамен по третьему предмету в четвертый день, после него экзамен по второму предмету в пятый день. После этого в шестой день Валера сдаст экзамен по первому предмету.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 2
3 1
4 2
|
2
|
|
2
|
3
6 1
5 2
4 3
|
6
|