Shrinking Inscribed Polygon

Time limit1sMemory limit128 MB

Summary

Given arc lengths around an inscribed polygon, find the minimum number of vertices to delete so the remaining vertices form a regular polygon, or report -1.

Level: Medium7 of 10
Topics: Number theory, Math, Array, Prefix sum
Solved: No attempts yet

Problem

A polygon is said to be inscribed in a circle when all of its vertices lie on that circle. Given a polygon inscribed in a circle, determine the minimum number of vertices that must be removed so that the remaining polygon becomes a regular polygon. A regular polygon is a polygon in which every side has the same length and every interior angle has the same measure.

To remove a vertex $v$ from the polygon, first find its two neighboring vertices $w_1$ and $w_2$ , then connect $w_1$ and $w_2$ with a new edge. Doing so merges the two arcs that had $v$ between them into a single arc.

For example, from an inscribed polygon with $10$ vertices you can remove a suitable set of $5$ vertices to form a regular pentagon.

The polygon always has at least $3$ sides.

Input

The input consists of several test cases.

The first line of each test case contains the number of vertices $N$ of the inscribed polygon. ( $3 \le N \le 10^4$ ) The second line contains $N$ integers $X_i$ . ( $1 \le X_i \le 10^3$ )

$X_i$ is the arc length between vertex $i$ and vertex $(i+1) \bmod N$ , given in clockwise order. Note that an arc is measured along the circle's circumference, not as a chord.

The last line of the input contains a single $0$ , which is not processed.

Output

For each test case, print on one line the minimum number of vertices that must be removed to form a regular polygon. If no regular polygon can be formed, print $-1$ .

Examples1

Example 1

Input

3
1000 1000 1000
6
1 2 3 1 2 3
3
1 1 2
10
10 40 20 30 30 10 10 50 24 26
0

Expected output