The streets of Barcelona P56164

The members of the Council of Barcelona have realized that some streets are longer than others. To solve this “critical problem”, they are planning to add some signs to indicate that street names change from some point on, so that they are (formally) split into smaller streets. For instance, if there are just two streets, one 20 units long, the other 30 units long, then by adding one sign in the middle of the first street, and two signs uniformly distributed in the second street, the result would be five streets with exactly the same length: 10 units. Great!

Mmmm… But what happens if there are, say, three streets with lengths 12, 15 and 40? In that case, as many as 11 + 14 + 39 = 64 new signs would be necessary to get all the streets with the same length, namely 1. This would be too much waste!

Mmmm (again)… The Mayor found a magnificent solution! Exactly one of the streets will be “removed”, and reconverted into a walk… or a boulevard? No, even better, a ski slope! Brilliant!

Indeed, consider the above example, with lengths 12, 15 and 40. Removing the street with length 40, it is possible to add just 7 signs to make the rest of streets 3 units long. Removing the street with length 12 or the street with length 15 would be worse solutions, with 9 new signs or 11 new signs, respectively.

Input

Input consists of several cases, each with the number of streets n, followed by n integer numbers between 1 and 10⁹ that indicate the length of every street. Assume 1 ≤ n ≤ 10⁶.

Output

For every test case, print the minimum number of signs that must be added so that all the streets have the same length after “removing” exactly one of the streets.