348A.md (1488B)
1 Source: https://codeforces.com/problemset/problem/348/A 2 3 A. Mafia 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 One day *n* friends gathered together to play "Mafia". During each round of the game some player must be the supervisor and other *n* - 1 people take part in the game. For each person we know in how many rounds he wants to be a player, not the supervisor: the *i*-th person wants to play *a**i* rounds. What is the minimum number of rounds of the "Mafia" game they need to play to let each person play at least as many rounds as they want? 22 23 Input 24 25 The first line contains integer *n* (3 ≤ *n* ≤ 105). The second line contains *n* space-separated integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 109) — the *i*-th number in the list is the number of rounds the *i*-th person wants to play. 26 27 Output 28 29 In a single line print a single integer — the minimum number of game rounds the friends need to let the *i*-th person play at least *a**i* rounds. 30 31 Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier. 32 33 Examples 34 35 Input 36 37 ``` 38 3 39 3 2 2 40 ``` 41 42 Output 43 44 ``` 45 4 46 ``` 47 48 Input 49 50 ``` 51 4 52 2 2 2 2 53 ``` 54 55 Output 56 57 ``` 58 3 59 ``` 60 61 Note 62 63 You don't need to know the rules of "Mafia" to solve this problem. If you're curious, it's a game Russia got from the Soviet times: http://en.wikipedia.org/wiki/Mafia_(party_game).