题目描述

小壮是一名工人，他每天的工作就是把石头敲碎。现在工地上有n块石头，每块石头的重量为a$_i$​。小壮需要每次从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

1、如果 x == y，那么两块石头都会被完全粉碎；

2、如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。

输入

第一行一个数 $n$ ；

第二行$n$个数，表示石头的重量a$_i$​；

输出

输出一行，最后一块石头最小的可能重量 。如果没有石头剩下，就输出 0。

样例

6
2 7 4 1 8 1

1

5
31 26 33 21 40

5

提示

数据范围与提示：

对于全部数据，$0 < n ≤30,0 < a$_i$​≤100$ 。