Description

萝卜头在圣诞节收到了N件礼物，礼物由一些面积相同厚度不同的盒子包装着。萝卜头很是开心，不断摆弄着手里的礼物盒，突然间他想到了一个游戏，就是不断把礼物盒叠在另一个礼物盒上，堆成两堆，两堆的高度要相同。他想知道利用这些礼物盒堆成两堆的最大高度是多少，可以只取部分礼物盒，但是每堆最少要有一个。

Input

输入包含多组测试数据。 每组测试数据包括两行。 第一行包括一个整数N（2<=N<=100）,表示礼物份数。 第二行包括N个整数H（1<=H<=100），表示N个包装礼物的礼物盒的厚度。

Output

针对每组测试数据输出一行，这一行里包含一个整数，表示能堆成的最大高度，如果不能堆成高度相同的两堆，则输出-1。

Sample

Input

4
4  1  3  10
3
1  2  5

Output

4
-1

Source: z_y