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:

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 each transfer can involve any number of points.
3. 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_i ≤ 1,000,000) points. The Codefather's 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 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

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)

The son in law will then fail his last year of university...
An initialization the compiler can't refuse...

N is no larger than 5000.

A student is not allowed to both receive and gain points from various students - only one or the other. This is to avoid a transfer situation A->B->C, which would act like transfer A->C, which could then be duplicated.
A student is still allowed to receive points from multiple students, OR gain students from multiple students, but not both.

Typo?

Binary-search for the largest possible value of X, where X is the maximum number of points you can transfer. Once you find this value of X, this is what you should output.

However, figuring out how to determine whether or not a value of X is valid is up to you =)