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 Pi (1 ≤ Pi ≤ 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).
|Line 1:||The integer N|
|The next N lines:||Line i+1 contains the integer Pi|
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 "
4 500 300 900 100
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
Point Value: 30 (partial)
Time Limit: 5.00s
Memory Limit: 16M
Added: Jan 05, 2009
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3