시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3 2 2 66.667%

문제

4개의 다리를 가진 탁자는 다리의 길이가 모두 같지 않으면 덜컹거린다. 덜컹거리는 것이 취향이 아니라면 탁자가 균형을 이루도록 적당한 다리를 골라 적당히 자르면 된다.

이를 일반화시켜 t개의 다리가 균등한 거리만큼 떨어져 있는 원형 탁자를 생각해보자. 이 때, 탁자가 덜컹거리지 않게 하기 위해 탁자의 다리를 자를 때, 자르는 양의 최솟값을 계산한다. (무게중심을 생각하면 꼭 모든 다리가 땅에 닿지 않아도 탁자는 덜컹거리지 않을 수 있다.)

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스마다 첫번째 줄에 t(3≤t≤50), 그 다음 t개의 줄에 원탁의 다리들의 길이가 원주상의 순서대로 주어진다. 모든 다리는 탁자판에 수직이다.

입력의 끝은 0으로 표시한다.

출력

각 테스트 케이스마다 다리를 최소한 얼마나 잘라야 하는지 출력한다. 각 테스트 케이스 사이에는 빈 줄이 하나 끼어있야한다.

예제 입력

3
2000
3000
4000
4
2000
2000
1999
2001
5
2000
2000
1999
2001
1999
0

예제 출력

3000

4

1

힌트