题目描述

有一堆石头，每块石头的重量都是正整数。 每一回合，从中选出两块最重的石头，然后将它们对撞。假设石头的重量分别为 x 和 y,且x <= y。 那么对撞的可能结果如下: 1、如果 x == y,那么两块石头都会被完全粉碎; 2、如果x != y,那么重量为x的石头将会完全粉碎,而重量为y 的石头只剩下重量为 y-x的部分。剩余部分放回石头堆。 如此反复选石头对撞，直到最后只剩下一块石头，输出此石头的重量。如果没有石头剩下，就输出0。

输入格式

两行，第一行是一个整数n（1≤ n ≤ 30000），表示石头数量。 第二行包含n个整数，表示n块石头的重量。输入数据保证每块石头重量小于2^31 。

输出格式

如果没有石头剩下,就输出0。否则输出最后一块石头的重量。

样例

输入样例 1

6
2 7 4 1 8 1

输出样例 1

1

输入样例 2

1
1

输出样例 2

1

输入样例 3

1
2147483647

输出样例 3

2147483647