시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 8 6 5 83.333%

문제

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

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

입력

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

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

출력

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

예제 입력 1

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

예제 출력 1

3000

4

1
W3sicHJvYmxlbV9pZCI6IjE2NTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzNWNcdWNlZjlcdWIzNWNcdWNlZjkiLCJkZXNjcmlwdGlvbiI6IjxwPjRcdWFjMWNcdWM3NTggXHViMmU0XHViOWFjXHViOTdjIFx1YWMwMFx1YzljNCBcdWQwYzFcdWM3OTBcdWIyOTQgXHViMmU0XHViOWFjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWJhYThcdWI0NTAgXHVhYzE5XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NCBcdWIzNWNcdWNlZjlcdWFjNzBcdWI5YjBcdWIyZTQuIFx1YjM1Y1x1Y2VmOVx1YWM3MFx1YjlhY1x1YjI5NCBcdWFjODNcdWM3NzQgXHVjZGU4XHVkNWE1XHVjNzc0IFx1YzU0NFx1YjJjOFx1Yjc3Y1x1YmE3NCBcdWQwYzFcdWM3OTBcdWFjMDAgXHVhZGUwXHVkNjE1XHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjNjNFx1Yjg1ZCBcdWM4MDFcdWIyZjlcdWQ1NWMgXHViMmU0XHViOWFjXHViOTdjIFx1YWNlOFx1Yjc3YyBcdWM4MDFcdWIyZjlcdWQ3ODggXHVjNzkwXHViOTc0XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViOTdjIFx1Yzc3Y1x1YmMxOFx1ZDY1NFx1YzJkY1x1Y2YxYyB0XHVhYzFjXHVjNzU4IFx1YjJlNFx1YjlhY1x1YWMwMCBcdWFkZTBcdWI0ZjFcdWQ1NWMgXHVhYzcwXHViOWFjXHViOWNjXHVkMDdjIFx1YjVhOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyOTQgXHVjNmQwXHVkNjE1IFx1ZDBjMVx1Yzc5MFx1Yjk3YyBcdWMwZGRcdWFjMDFcdWQ1NzRcdWJjZjRcdWM3OTAuIFx1Yzc3NFx1YjU0YywgXHVkMGMxXHVjNzkwXHVhYzAwIFx1YjM1Y1x1Y2VmOVx1YWM3MFx1YjlhY1x1YzljMCBcdWM1NGFcdWFjOGMgXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQwYzFcdWM3OTBcdWM3NTggXHViMmU0XHViOWFjXHViOTdjIFx1Yzc5MFx1Yjk3YyBcdWI1NGMsIFx1Yzc5MFx1Yjk3NFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU1Y1x1YjJlNC4gKFx1YmIzNFx1YWM4Y1x1YzkxMVx1YzJlY1x1Yzc0NCBcdWMwZGRcdWFjMDFcdWQ1NThcdWJhNzQgXHVhZjJkIFx1YmFhOFx1YjRlMCBcdWIyZTRcdWI5YWNcdWFjMDAgXHViNTQ1XHVjNWQwIFx1YjJmZlx1YzljMCBcdWM1NGFcdWM1NDRcdWIzYzQgXHVkMGMxXHVjNzkwXHViMjk0IFx1YjM1Y1x1Y2VmOVx1YWM3MFx1YjlhY1x1YzljMCBcdWM1NGFcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4pPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgdCgzXHUyMjY0dFx1MjI2NDUwKSwgXHVhZGY4IFx1YjJlNFx1Yzc0YyB0XHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWM2ZDBcdWQwYzFcdWM3NTggXHViMmU0XHViOWFjXHViNGU0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWM2ZDBcdWM4ZmNcdWMwYzFcdWM3NTggXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YjJlNFx1YjlhY1x1YjI5NCBcdWQwYzFcdWM3OTBcdWQzMTBcdWM1ZDAgXHVjMjE4XHVjOWMxXHVjNzc0XHViMmU0LjxcL3A+PHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjA1ZFx1Yzc0MCAwXHVjNzNjXHViODVjIFx1ZDQ1Y1x1YzJkY1x1ZDU1Y1x1YjJlNC48XC9wPiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YjJlNFx1YjlhY1x1Yjk3YyBcdWNkNWNcdWMxOGNcdWQ1NWMgXHVjNWJjXHViOWM4XHViMDk4IFx1Yzc5OFx1Yjc3Y1x1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHViZTQ4IFx1YzkwNFx1Yzc3NCBcdWQ1NThcdWIwOTggXHViMDdjXHVjNWI0XHVjNzg4XHVjNTdjXHVkNTVjXHViMmU0LjxcL3A+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTY1NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRhYmxlIExlZ3MiLCJkZXNjcmlwdGlvbiI6IjxwPkEgdGFibGUgd2l0aCBmb3VyIGxlZ3MgbWF5IHJvY2ssIGV2ZW4gb24gYSBmbGF0IHN1cmZhY2UsIGlmIGl0cyBsZWdzIGFyZSBub3QgYWxsIHRoZSBzYW1lIGxlbmd0aC4gSW50ZXJlc3RpbmdseSwgcmVnYXJkbGVzcyBvZiBob3cgbWFueSBsZWdzIGhhdmUgZGlmZmVyaW5nIGxlbmd0aHMsIGl0IGlzIGFsd2F5cyBwb3NzaWJsZSB0byBzYXcgYW4gYW1vdW50IGZyb20gc29tZSBsZWdzIHNvIGFzIHRvIG1ha2UgdGhlIHRhYmxlIHNpdCBsZXZlbCBvbiBhIGZsYXQgc3VyZmFjZSB3aXRob3V0IHJvY2tpbmcuPFwvcD5cclxuXHJcbjxwPllvdXIgam9iIGlzIHRvIGdlbmVyYWxpemUgdGhpcyBhcHByb2FjaCB0byBhIHRhYmxlIHdpdGggbWFueSBsZWdzIGVxdWFsbHkgc3BhY2VkIGFyb3VuZCB0aGUgcGVyaW1ldGVyIG9mIGEgcm91bmQgdGFibGUuIFlvdSBhcmUgdG8gZGV0ZXJtaW5lIHRoZSB0b3RhbCBsZW5ndGggb2YgbGVncyB0byBjdXQgc28gYXMgdG8gaGF2ZSB0aGUgdGFibGUgc2l0IGxldmVsIHdpdGhvdXQgcm9ja2luZyBvbiBhIGZsYXQgc3VyZmFjZSB3aXRoIG5vdCBuZWNlc3NhcmlseSBldmVyeSBsZWcgdG91Y2hpbmcgdGhlIGdyb3VuZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IGNvbnNpc3RzIG9mIGRhdGEgZm9yIGEgbnVtYmVyIG9mIHRhYmxlcy4gRm9yIGVhY2ggdGFibGUsIGEgbGluZSB3aWxsIGdpdmUgYW4gaW50ZWdlciB0LCBiZXR3ZWVuIDMgYW5kIDUwLCBpbmRpY2F0aW5nIHRoZSBudW1iZXIgb2YgbGVncyBvbiB0aGUgdGFibGUuIHQgc3Vic2VxdWVudCBsaW5lcyB3aWxsIGdpdmUsIGluIG9yZGVyIGFyb3VuZCB0aGUgdGFibGUmIzM5O3MgY2lyY3VtZmVyZW5jZSwgdGhlIGxlbmd0aHMgb2YgdGhlIGxlZ3MgaW4gbWlsbGltZXRyZXMuIEVhY2ggbGVnIGlzIHBlcnBlbmRpY3VsYXIgdG8gdGhlIHRhYmxlIHRvcC4gQSBsaW5lIGNvbnRhaW5pbmcgMCBmb2xsb3dzIHRoZSBkYXRhIGZvciB0aGUgbGFzdCB0YWJsZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QaWNrIGEgc3RyYXRlZ3kgdGhhdCBjdXRzIHRoZSBsZWFzdCB0b3RhbCBsZW5ndGggZnJvbSBhbGwgbGVncyBhbmQgcHJpbnQgdGhpcyBhbW91bnQgYXMgYW4gaW50ZWdlciBudW1iZXIuIFByaW50IGEgYmxhbmsgbGluZSBiZXR3ZWVuIHRhYmxlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=