Contest.uni-smr.ac.ru :: Programming contests in Samara
Русская версия || English version
Login:
Password:
Forget password?
 example: Bill Gates
 






Cashmaster

Автор задачи: Илья Гребнов, Никита Рыбак, Дмитрий Ковалёв

Первоисточник: Timus Top Coders: Third Challenge

URL первоисточника: http://acm.timus.ru/problem.aspx?space=1&num=1515&locale=ru

Задачу добавил: Spirt96

Успешно сдано решений: 97

http://contest.samara.ru/ru/contests/53/

Time Limit: 1.0 second
Memory Limit: 16 MB

Background

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.

Problem

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.

Input

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).

Output

You should output the desired denomination of the new banknote.

Sample Input

5
1 2 4 9 100

Sample Output

8

Hint

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.

Submit

Задать вопрос жюри по этой задаче