题目描述

小明和小红有一些糖果，现在他们决定分配这些糖果。他们共有 $N$ 个糖果，每个糖果的重量在 $1$ 到 $100$ 克之间（包括 $1$ 克和 $100$ 克）。

小明和小红任何一人都不能接受对方分配到的糖果的重量更大，所以两人各分配到的糖果的重量必须相同，如果有剩下的，则送给其他人。在两人各分配到的糖果重量相同的前提下，他们还想要分配到的糖果重量尽可能的大。

要求这么多，他们已经想不出来怎么分了，找到了天才程序员菜哭武。当然菜哭武觉得这个问题太简单了，不值得他浪费时间，还是你来算吧。

现在给你 $N$ 个糖果的重量，请你计算他们必须送给别人多少克的糖果，以此来满足他们自己分配糖果的要求。

友情提示：糖果不能切开来分！并且可能存在两人都分不到糖果的情况哦。

输入格式

输入包含多组测试数据。

每组输入的第一行是一个整数 $N$（$0 \leq N \leq 20$），表示糖果的个数，当 $N=0$ 时，输入结束。

接下来 $N$ 行，每行输入一个整数，表示一个糖果的重量。

输出格式

对于每组输入，输出一个整数，表示必须送给别人的糖果的重量，以此来满足他们自己的分配要求。

样例输入

5
1
2
3
2
1
0

样例输出

1