问题描述

一张四条腿的桌子可能会摇晃，即使放在平坦的表面上，只要其腿长不一致。有趣的是，无论有多少条腿长度不同，总能通过锯掉某些腿的一部分，使桌子平稳地放置在平面上而不摇晃。

现在需要将此问题推广到圆桌周围等距分布的多条腿的情况。请确定需要锯掉的腿的总长度，使得桌子能平稳放置在平面上（不必每条腿都触地）。

输入格式

输入包含多个桌子的数据。对于每个桌子：

1. 第一行是整数 $t$$（3 ≤ t ≤ 50）$，表示桌子的腿数。
2. 接下来 $t$ 行按圆桌周长顺序给出每条腿的长度（单位：毫米），每条腿均垂直于桌面。
3. 最后一个桌子的数据后接一行 $0$，表示输入结束。

输出格式

选择锯掉总长度最小的策略，并输出该总长度（整数）。每个桌子的输出之间用空行分隔。

输入样例 1

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

输出样例 1

3000  

4  

1  

题目来源

The UofA Local 1999.10.16