The computer science mafia, headed of course by the Codefather, have control of the computer science course points spreadsheet. The Codefather has the power to transfer points from one person to another.

The Codefather’s daughter is getting married, and he wants to give a gift to his future son-in-law, who happens to be taking this computer science course. Since only the person with the most points can get a mark of 100% in this course, the Codefather wants to insure that his future son-in-law will have strictly more points than anyone else by performing a number of point transfers. However, he’s a cautious man (in his business, you have to be), so he follows the following rules:

   1. None of the transfers will involve his future son-in-law.

   2. For each pair of people, he will only perform up to one point transfer, though this transfer can involve any number of points.

   3. No person can be involved in both transfers in which they lose and gain points - only one or the other (or neither).

   4. After all the transfers are completed, no student can have a negative amount of points.

There are $N$ ($1 \leq N \leq 5000$) students in this course, each with a unique student number from $1$ to $N$, inclusive. Student $i$ starts off with $P_i$ ($1 \leq P_i \leq 10^6$) points. The Codefather’s future son-in-law is student $1$.

Though the Codefather is a powerful man, he’s still wary of the authorities, and wants to remain as inconspicuous as possible. Therefore, he wants to minimize the number of points in the largest transfer he makes, while still insuring that his future son-in-law will get 100%.

Input

Line $1$: 1 integer, $N$

Next $N$ lines: 1 integer, $P_i$, for $i=1..N$

Output

If it’s possible for the Codefather to observe the rules and give his future son-in-law more points than anyone else, minimize the number of points in the largest transfer he must make and output this value.

Otherwise, output “impossible”.

Example

Input:

4
500
300
900
100
Output:

202

Explanation of Sample:

The future son-in-law only has 500 points, so the Codefather must make student 3 lose at least 401. However, the other students must also stay strictly below 500. His best strategy is to transfer 199 points from student 3 to student 2, and 202 points from student 3 to student 4. This will result in the following point distribution:

Student 1: 500

Student 2: 499

Student 3: 499

Student 4: 302