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₁ fishes. So he did that: threw away a₁ 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₂ 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 a₁, …, a_n (0 ≤ a_i ≤ n − 1), where a_i is the number of fishes thrown away by the i-th fisherman.

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