The children were picking the mushrooms in the forest. Petya did not find any mushroom and burst into tears (because he was the smallest among all the children). The children were polite and decided that everyone would give Petya the same amount of mushrooms. But no one wanted to give mushrooms without a definite plan. Then it was decided that each of the children would give the same minimum amount of mushrooms so that in total Petya got more mushrooms than any child would have left. Find out if it is possible, and how many mushrooms Petya will get from each of the children.

Input

The first line contains a number n (1 ≤ n ≤ 105) - the number of friends picking the mushrooms. The second line contains n - 1 numbers ai (1 ≤ ai ≤ 109) - the number of mushrooms found by each of the children.

Output

Print the number of mushrooms that Petya will get from each of the children, or -1 if this is impossible.