ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Timus Top Coders: Third Challenge

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

E. Финансовая реформа

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Вступление

Однажды бывший мелкий госслужащий, а ныне министр финансов Советской Федерации Виктор Воровский понял, что за первую половину своей жизни украл столько, что на оставшуюся половину ему хватит сполна (более подробно эта история рассказана в задаче «Преступление и наказание»). В связи с этим Виктор задумал посвятить остаток дней делу увековечивания собственного честного имени в глазах народа.
Будучи министром финансов, г-н Воровский как никто другой знал, что наиболее приятным человеческому глазу предметом является денежная купюра. Поэтому он решил напечатать свой портрет на банкнотах, выпускаемых подконтрольным ему Министерством.
Но даже Виктор сообразил, что печатать свой портрет на уже выпускаемых банкнотах нехорошо. Следовательно, есть повод провести очередную финансовую реформу – начать выпуск денежных купюр нового номинала с собственным портретом на обеих сторонах.

Задача

Теперь осталось лишь определиться с достоинством новой банкноты, проще говоря, с целым положительным числом, которое будет на ней написано. Виктор начал с того, что разложил перед собой в порядке возрастания номинала по одному экземпляру всех купюр, находящихся в обращении на данный момент. Оказалось, что таких купюр в точности N штук, причём номинал каждой из них составляет Di рублей. Казалось бы, нужно просто взять любой из неиспользуемых номиналов. Но честолюбивому г-ну Воровскому очень не хотелось, чтобы номиналы каких-либо из лежащих перед ним банкнот давали в сумме номинал новой банкноты...
И тут Виктор понял, что чуть не упустил одну очень важную вещь. Дело в том, что планируемая эмиссия (т.е. выпуск новой партии денег) неизбежно повлечёт за собой рост инфляции, что в свою очередь может привести к обесцениванию с таким трудом наворованного капитала г-на Воровского. Поэтому искомый номинал должен быть наименьшим из возможных.

Исходные данные

Первая строка содержит целое число N (1 ≤ N ≤ 100). Вторая строка содержит N целых чисел Di (1 ≤ Di ≤ 106; Di < Di+1).

Результат

Вывести искомый номинал новой банкноты.

Пример

исходные данныерезультат
5
1 2 4 9 100
8

Замечания

В примере номиналы 3, 5, 6 и 7 могут быть представлены в виде сумм номиналов уже выпускающихся банкнот (3 = 1 + 2, 5 = 1 + 4, 6 = 2 + 4, 7 = 1 + 2 + 4), в то время как номинал 8 в виде такой суммы не представим.
Автор задачи: Илья Гребнов, Никита Рыбак, Дмитрий Ковалёв
Источник задачи: Timus Top Coders: Third Challenge
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1515. Финансовая реформа