Автор задачи: Илья Гребнов, Никита Рыбак, Дмитрий Ковалёв
Первоисточник: Timus Top Coders: Third Challenge
URL первоисточника: http://acm.timus.ru/problem.aspx?space=1&num=1515&locale=ru
Задачу добавил: Spirt96
Успешно сдано решений: 97http://contest.samara.ru/ru/contests/53/
Time Limit: 1.0 second
Memory Limit: 16 MB
Once upon a time former petty bureaucrat, nowadays the Minister of Finance of the Soviet Federation, Victor Thiefton considered, that he had stolen so much money during the first half of his life, that it will be enough for the last half also (this story is fully described in the problem "Crime and punishment"). As a result of this conclusion Victor intended to devote himself to immortalizing of his good name in national opinion.
Being the Minister of Finance, Mr. Thiefton knew perfectly, that the most gratifying thing to the human eye was a banknote. So he decided to print his noble face on the banknotes issued by his Ministry.
But even Victor grasped, that it would be wrong to print his face on the banknotes, which had been already issued. Therefore a propitious occasion was given to Mr. Thiefton to carry out a financial reform - to issue a banknote of some new denomination with his face on the both sides of it.
The time came to define a denomination of the new banknote, i.e. a natural (positive integer) number, which should be printed on it. For a start, Victor took all the banknotes of different denominations, which had been already issued till that moment, and put them in ascending order. It appeared, that there were exactly N such banknotes, and a denomination of each of them was Di dollars. It seemed he might take any of still unused denomination. But ambitious Mr. Thiefton did not want the new banknote's denomination to be presented as a sum of the denominations of the banknotes, which are already issued...
And here Victor realized, that he had nearly failed to bear one extremely important thing in mind. The point was that the planned emission (i.e. an issue of a new batch of money) would inevitably cause inflation growth, which, in its turn, might lead to a devaluation of Mr. Thiefton capital, that was plundered with such a great effort. Therefore the desired denomination should be minimized.
The first line contains the integer number N (1 ≤ N ≤ 100). The second line contains N integer numbers Di (1 ≤ Di ≤ 1000000, Di < Di+1).
You should output the desired denomination of the new banknote.
5 1 2 4 9 100
In the sample, the denominations 3, 5, 6 and 7 may be presented as sums of the denominations of the banknotes, which are already issued (3 = 1 + 2, 5 = 1 + 4, 6 = 2 + 4, 7 = 1 + 2 + 4), whereas the denomination 8 can not be present as such sum.