Fox Ciel现在正在玩数字游戏。
Ciel 有 n 个正整数:x1, x2, ..., xn。她可以根据需要多次执行以下操作:选择两个不同的索引 i 和 j,使得 xi > xj 成立,然后应用赋值 xi = xi - xj。目标是使所有数字的总和尽可能小。
请帮助 Ciel 找到这个最小金额。
输入
第一行包含一个整数 n (2 ≤ n ≤ 100)。那么第二行包含 n 个整数:x1, x2, ..., xn (1 ≤ xi ≤ 100)。
输出
输出一个整数——所需的最小总和。
示例
输入 #1
2 1 2
输出 #1
2
输入 #2
3 2 4 6
输出 #2
6
输入 #3
2 12 18
输出 #3
12
输入#4
5 45 12 27 30 18
输出#4
15
注意
在第一个示例中,最佳方法是进行赋值:x2 = x2 - x1。
在第二个示例中,最佳操作顺序是:x3 = x3 - x2, x2 = x2 - x1。