ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Contest is over

## I. 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
To submit the solution for this problem go to the Problem set: 1818. Fair Fishermen