ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1818. Fair Fishermen

Time limit: 1.0 second
Memory limit: 64 MB
Fishermen caught a lot of fishes and, of course, they drank. In the morning it was the time to divide fishes. The first who woke up counted the fishes and it happened that in order to divide fishes equally he should throw away a1 fishes. So he did that: threw away a1 fishes and took his part. The second who woke up didn't know that the first fisherman took his part. He behaved the same as the first one: threw away a2 excess fishes and took his part. The same story happened with the rest of the fishermen.
Given the amount of fishes thrown away by each fisherman, find the minimal possible number of fishes they caught. It is known that they caught at least one fish.

Input

The first line contains an integer n (2 ≤ n ≤ 2000). The second line contains integers a1, …, an (0 ≤ ain − 1), where ai is the number of fishes thrown away by the i-th fisherman.

Output

Output the minimal number of fishes the fishermen had to catch.

Samples

inputoutput
2
1 1
3
3
1 0 2
19
Problem Source: Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010