← 返回题目列表

Codeforces · 389/A

A. 狐狸和数字游戏

中文机器翻译题面 查看原题

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。