勇者ポン太とその親友同じく勇者ゴン太は、これから壮大な冒険へと出発するために、それぞれ仲間を求めてルイーダの酒場へやって来ました。酒場には、冒険に出たくてうずうずしている武闘家や僧侶、魔法使いがたくさん居ます。
心やさしいゴン太はポン太を気遣い、「先に仲間を選んでいいよ。」と言いました。
一方、ポン太もゴン太が心配でなりません。「いや、君が先に選んでいいよ。」と言い返しました。
お互い譲り合いが続き、ついにルイーダがこう提案しました。「じゃあ、ここにいる n 人の登録者をそれぞれのパーティの合計戦闘力がなるべく均等になるように、この"パーティ分けマシン"で分けてあげるわ。」
あなたに与えられた仕事は、パーティ分けマシンに組み込まれているプログラムを作成することです。
このプログラムは n 個の整数を入力し、それらを２つのグループ A, B に分けたときの、A に含まれる整数の合計値と B に含まれる整数の合計値の差の最小値を出力しなければなりません。
このマシンのおかげで、ポン太とゴン太は仲良く仲間を見つけ、壮大な冒険へと出かけて行きました・・。
入力として複数のデータセットが与えられます。各データセットは以下の形式で与えられます：
n (登録者の数： 整数)
a1 a2 ... an （各登録者の戦闘力： 空白区切りの整数）
n は 20 以下であり、各登録者の戦闘力は 100 万を越えません。
n が 0 のとき入力の終わりとします。
各データセットに対して、最小値を1行に出力して下さい。
5 1 2 3 4 5 4 2 3 5 7 0
1 1