ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Timus Top Coders: Third Challenge

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Cashmaster

Time limit: 1.0 second
Memory limit: 64 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 positive integer, 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 ≤ 106; Di < Di+1).


You should output the desired denomination of the new banknote.


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.
Problem Author: Ilya Grebnov, Nikita Rybak, Dmitry Kovalioff
Problem Source: Timus Top Coders: Third Challenge
To submit the solution for this problem go to the Problem set: 1515. Cashmaster