수축하는 다각형

다각형의 모든 꼭짓점이 한 원 위에 놓여 있을 때, 그 다각형을 원에 내접하는 다각형이라고 한다. 원에 내접하는 다각형이 주어질 때, 이 다각형을 정다각형으로 만들기 위해 지워야 하는 꼭짓점의 최소 개수를 구하여라. 정다각형이란 모든 변의 길이가 같고 모든 내각의 크기가 같은 다각형을 말한다.

다각형에서 꼭짓점 $v$를 지우려면, 먼저 $v$와 이웃한 두 꼭짓점 $w_1$, $w_2$를 찾는다. 그런 다음 $w_1$과 $w_2$를 새로운 변으로 이으면 된다. 이렇게 하면 $v$를 사이에 두고 있던 두 호가 하나로 합쳐진다.

예를 들어 꼭짓점이 $10$개인 내접 다각형에서 알맞은 꼭짓점 $5$개를 지우면 정오각형을 만들 수 있다.

다각형의 변의 개수는 항상 $3$ 이상이다.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫째 줄에는 내접 다각형의 꼭짓점 개수 $N$이 주어진다. ($3 \le N \le 10^4$) 둘째 줄에는 $N$개의 정수 $X_i$가 주어진다. ($1 \le X_i \le 10^3$)

$X_i$는 $i$번 꼭짓점과 $(i+1) \bmod N$번 꼭짓점 사이의 호의 길이이며, 시계 방향 순서로 주어진다. 여기서 호는 현이 아니라 원둘레를 따라 잰 길이임에 유의하라.

입력의 마지막 줄에는 $0$이 하나 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 정다각형을 만들기 위해 지워야 하는 꼭짓점의 최소 개수를 한 줄에 출력한다. 정다각형을 만들 수 없으면 $-1$을 출력한다.