Финансовая реформа (ред. 21.12.2006)
Автор задачи: Илья Гребнов, Никита Рыбак, Дмитрий Ковалёв
Первоисточник: Timus Top Coders: Third Challenge
URL первоисточника: http://acm.timus.ru/problem.aspx?space=1&num=1515&locale=ru
Задачу добавил: Spirt96
Успешно сдано решений: 99
http://contest.samara.ru/ru/contests/53/Ограничение времени: 1.0 секунды
Ограничение памяти: 16 МБ
Вступление
Однажды бывший мелкий госслужащий, а ныне министр финансов Советской Федерации Виктор Воровский понял, что за первую половину своей жизни украл столько, что на оставшуюся половину ему хватит сполна (более подробно эта история рассказана в задаче «Преступление и наказание»). В связи с этим Виктор задумал посвятить остаток дней делу увековечивания собственного честного имени в глазах народа.
Будучи министром финансов, г-н Воровский как никто другой знал, что наиболее приятным человеческому глазу предметом является денежная купюра. Поэтому он решил напечатать свой портрет на банкнотах, выпускаемых подконтрольным ему Министерством.
Но даже Виктор сообразил, что печатать свой портрет на уже выпускаемых банкнотах нехорошо. Следовательно, есть повод провести очередную финансовую реформу – начать выпуск денежных купюр нового номинала с собственным портретом на обеих сторонах.
Задача
Теперь осталось лишь определиться с достоинством новой банкноты, проще говоря, с натуральным (т.е. целым положительным) числом, которое будет на ней написано. Виктор начал с того, что разложил перед собой в порядке возрастания номинала по одному экземпляру всех купюр, находящихся в обращении на данный момент. Оказалось, что таких купюр в точности N штук, причём номинал каждой из них составляет Di рублей. Казалось бы, нужно просто взять любой из неиспользуемых номиналов. Но честолюбивому г-ну Воровскому очень не хотелось, чтобы номиналы каких-либо из лежащих перед ним банкнот давали в сумме номинал новой банкноты...
И тут Виктор понял, что чуть не упустил одну очень важную вещь. Дело в том, что планируемая эмиссия (т.е. выпуск новой партии денег) неизбежно повлечёт за собой рост инфляции, что в свою очередь может привести к обесцениванию с таким трудом наворованного капитала г-на Воровского. Поэтому искомый номинал должен быть наименьшим из возможных.
Исходные данные
Первая строка содержит целое число N (1 ≤ N ≤ 100). Вторая строка содержит N целых чисел Di (1 ≤ Di ≤ 1000000, 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 в виде такой суммы не представим.