Description

南充高中的同学们来到了幼儿园，给幼儿园的小朋友们准备了一些糖果！
糖果一共有n块，每一块糖果都有一个可口度ai。你要把这些糖果分成两份，一份给男生，一份给女生。如果两份糖果的总可口度相差太大，那么会招来小朋友们的不满。所以，你要使这两份糖果的总可口度相差尽量小。

Input

第一行一个整数n，
接下来一行n个整数，表示第i块糖果的可口度。

Output

一行一个整数，表示两份糖果总可口度的最小差值。

Sample Input

5
5 2 4 3 1

Sample Output

1

Hint

将糖果分成两份：{1,2,4}和{3,5}，总可口度分别为7，8，差值为1。
对于30%的数据，n<=100;
对于100%的数据，n<=2000, ai<=10000。