## The Codefather

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

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 Grade 12 Enriched CompSci. Since only the person with the most points can get 99% in this course, the Codefather wants to ensure 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:

- None of the transfers will involve his future son-in-law.
- For each pair of people, he will only perform up to one point transfer, though each transfer can involve any number of points.
- After all the transfers are completed, no students can have a negative amount of points.

There are `N` (1 ≤ `N` ≤ 5,000) students in this course, each with a unique student number from 1 to `N`, inclusive. Student `i` starts off with `P _{i}` (1 ≤

`P`≤ 1,000,000) points. The Codefather's son-in-law is student 1.

_{i}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 largest transfers he makes, while still ensuring that his future son-in-law will get 99% (though with some blackmail, this'll go up to 100% anyway).

### Input

Line 1: | The integer N |

The next N lines: |
Line i+1 contains the integer P_{i} |

### 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 largest point transfer he must make and output it.

Otherwise, output "`impossible`

".

### Sample Input

4 500 300 900 100

### Sample Output

202

### Explanation

The 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

All Submissions

Best Solutions

**Point Value:** 30 (partial)

**Time Limit:** 5.00s

**Memory Limit:** 16M

**Added:** Jan 05, 2009

**Author:** SourSpinach

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

Jim42069on May 04, 2017 - 6:15:29 pm UTC And in university...An initialization the compiler can't refuse...

SourSpinachon May 13, 2013 - 12:36:17 pm UTC CorrectionSourSpinachon Oct 27, 2011 - 4:36:10 pm UTC ClarificationA student is still allowed to receive points from multiple students, OR gain students from multiple students, but not both.

dAedaLon May 09, 2012 - 4:30:00 pm UTC Re: ClarificationSourSpinachon Feb 09, 2009 - 2:58:15 am UTC HintHowever, figuring out how to determine whether or not a value of X is valid is up to you =)