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 a_{1} fishes. So he did that: threw away a_{1} 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 a_{2} 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 a_{1}, …, a_{n} (0 ≤ a_{i} ≤ n − 1), where a_{i} is the number of fishes thrown away by the ith fisherman.
Output
Output the minimal number of fishes the fishermen had to catch.
Samples
input  output 

2
1 1
 3

3
1 0 2
 19

Problem Source: Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010