Fox Ciel is playing a game with numbers now. 

Ciel has n positive integers: x_1, x_2, ..., x_{n}. She can do the following operation as many times as needed: select two different indexes i and j such that x_{i} > x_{j} hold, and then apply assignment x_{i} = x_{i} - x_{j}. The goal is to make the sum of all numbers as small as possible.

Please help Ciel to find this minimal sum.


-----Input-----

The first line contains an integer n (2 ≤ n ≤ 100). Then the second line contains n integers: x_1, x_2, ..., x_{n} (1 ≤ x_{i} ≤ 100).


-----Output-----

Output a single integer — the required minimal sum.


-----Examples-----
Input
2
1 2

Output
2

Input
3
2 4 6

Output
6

Input
2
12 18

Output
12

Input
5
45 12 27 30 18

Output
15



-----Note-----

In the first example the optimal way is to do the assignment: x_2 = x_2 - x_1.

In the second example the optimal sequence of operations is: x_3 = x_3 - x_2, x_2 = x_2 - x_1.

Difficulty: interview

Starter code:

Solutions:
from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
no=a[0]
for i in range(1,n):
    no=gcd(no,a[i])
print(no*n)

def GCD(x,y):
    while (x!=y):
        if x<y: x,y = y,x
        x-=y
    return x

n = int(input())
ar = list(map(int,input().split(' ')))
r = ar[0]
for i in range(n-1):
    r = GCD(r, ar[i+1])
print(r*n)


#!/usr/bin/env python3

def gcd(x, y):
    if y == 0 or x == 0:
        return max(x, y)
    t = x % y
    while t != 0:
        x = y
        y = t;
        t = x % y
    return y

def main():
    readData = lambda : list(map(int, input().split()))
    n = int(input())
    X = list(readData())
    d = 0
    for x in X:
        d = gcd(d, x)
    print(d * len(X))

def __starting_point():
    main()

__starting_point()

def nod(a,b):
    while max(a,b) % min(a,b) != 0:
        if a>= b:
            a=a %b
        else:
            b=b%a
    return min(a,b)

n = int(input())
arr = list(map(int,input().split()))
x = arr[0]
for i in range(1,n):
    x = nod(arr[i],x)
print(x*n)

from fractions import gcd
from functools import reduce
n = int(input())
a = list(map(int, input().split()))
print(n * reduce(gcd, a))


n = int(input())
v = list(map(int, input().split()))

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

g = v[0]
for each_v in v:
    g = gcd(g, each_v)

print(g * n)


input().split()
xs = list(map(int, input().split()))
def gdc(a,b):
  while b > 0:
    a, b = b, a%b
  return a
  
ret = 0
for x in xs:
  ret = gdc(x,ret)

print(ret*len(xs))

def nod(x,y):
    while x*y:
        if x>y:
            x%=y
        else:
            y%=x
    return x+y


n=int(input())
a=list(map(int,input().split()))
m=a[0]
for i in range(1,n):
    m=nod(m,a[i])
print(n*m)

from fractions import gcd
from functools import reduce

n = int(input())
nums = map(int, input().split())
print(reduce(lambda x, y: gcd(x, y), nums) * n)

n=int(input())
a=list(map(int,input().split()))
for i in range(n*2):
    a=sorted(a,reverse=True)
    for j in range(1,n):
        while a[j] and a[0]>a[j]:
            a[0]-=a[j]
print(sum(a))


from functools import *; from fractions import*
print(int(input()) * reduce(gcd,list(map(int,input().split()))))



def gcd(a, b):
    c = a % b
    return gcd(b, c) if c else b
n, t = int(input()), list(map(int, input().split()))
j = t[0]
for i in t[1: ]: j = gcd(i, j)
print(n * j)

from fractions import gcd
from functools import reduce
print(int(input()) * reduce(gcd, map(int, input().split())))

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

n = int(input())
a = list(map(int, input().split()))
m = a[0]

for i in range(1, n):
    m = (gcd(a[i], m))
print(n * m)
        


n = int(input())
a = list(map(int, input().split()))
while(1):
    T = True
    for i in range(n):
        for j in range(n):
            if a[i] > a[j]:
                a[i] = a[i] - a[j]
                T = False
            elif a[i] < a[j]:
                a[j] = a[j] - a[i]
                T = False
    if T:
        break
print(sum(a))

from fractions import gcd
a = int(input())
nums = list(map(int, input().split(' ')))
gcdx = nums[0]
for i in range(len(nums)):
    gcdx = gcd(gcdx, nums[i])
print(gcdx*a)



from fractions import gcd
n = int(input())
arr = list(map(int, input().split()))
ans = arr[0]
for i in range(1,len(arr)):
	ans = gcd(ans, arr[i])
print(ans * len(arr))

from fractions import gcd
n, val = int(input()), 0
for a in (int(x) for x in input().split()):
    val = a if val == 0 else gcd(val, a)
print(val * n)

k = int(input())
l = list(map(int, input().split()))

l.sort(reverse=True)
for i in range(1000):
    for i in range(k-1):
        if (l[i+1] < l[i]):
            l[i] -= l[i+1]
            l.sort(reverse=True)
print(sum(l))


def pairGCD(a, b):
	while a:
		a, b = b % a, a
	return b

def gcd(l):
	res = l[0]
	for x in l[1:]:
		res = pairGCD(res, x)
	return res

n = int(input())
l = [int(x) for x in input().split()]
print(gcd(l) * n)


from sys import stdin


def main():
    n = int(stdin.readline())
    l = list(map(int, stdin.readline().split()))
    while True:
        l.sort()
        i = max(list(range(1, n)), key=lambda _: l[_] - l[_ - 1])
        if l[i] == l[i - 1]:
            return sum(l)
        l[i] -= l[i - 1]


print(main())



import sys
import math

def gcd(a, b):
    if(b == 0):
        return a
    r = a % b
    return gcd(b, r)

n = int(sys.stdin.readline())
an = [int(x) for x in (sys.stdin.readline()).split()]

vmin = min(an)
kmin = 101
for i in range(n):
    t = gcd(vmin, an[i])
    if(t < vmin):
        vmin = t
        
print(n * t)

def g(x):
    if len(x)==1:return x[0]
    if x[0]==0:return g(x[1:])
    return g([x[-1]%x[0]]+x[:-1])
input()
a=list(map(int,input().split()))
print(g(a)*len(a))



def log(*args): 
    #print(*args)
    pass

N = int(input())
L = [int(n) for n in input().split()]
assert N == len(L)
L.sort()

changed = True

while changed:
    log('begin, L=', L)
    blah = L[:]
    changed = False
    for i in range(N):
        for j in range(i):
            num = L[i] + L[j]
            if num not in blah:
                blah.append(num)

    log('blah', blah)

    for i in range(N):
        num = L[i]
        for n in range(num-1, -1, -1):
            if n in blah:
                log('pos', i, 'subtracting', n, 'from', L[i])
                L[i] = num - n
                changed = True
                break
    
    log(sum(L))

log('fin')
print(sum(L))


# coding: utf-8
n = int(input())
x = [int(i) for i in input().split()]
while True:
    tmp = min(x)
    for i in range(n):
        if x[i]%tmp == 0:
            x[i] = tmp
        else:
            x[i] %= tmp
    if sum(x) == tmp*n:
        break
print(sum(x))