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.
The first line contains an integer n (2 ≤ n ≤ 2000).
The second line contains integers a1, …, an (0 ≤ ai ≤ n − 1), where ai is the number of fishes thrown away by the i-th fisherman.
Output the minimal number of fishes the fishermen had to catch.
1 0 2
Problem Source: Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010