There are N monsters, numbered 1, 2, ..., N.
Initially, the health of Monster i is A_i.
Below, a monster with at least 1 health is called alive.
Until there is only one alive monster, the following is repeated:
 - A random alive monster attacks another random alive monster.
 - As a result, the health of the monster attacked is reduced by the amount equal to the current health of the monster attacking.
Find the minimum possible final health of the last monster alive.

-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 10^5
 - 1 \leq A_i \leq 10^9

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 A_2 ... A_N

-----Output-----
Print the minimum possible final health of the last monster alive.

-----Sample Input-----
4
2 10 8 40

-----Sample Output-----
2

When only the first monster keeps on attacking, the final health of the last monster will be 2, which is minimum.

Difficulty: introductory

Starter code:

Solutions:
N = int(input())
A = list(map(int,input().split()))
A_list = [float('inf')] * N

ans = min(A)
while max(A_list) > 0:
    mi = ans
    for i,a in enumerate(A):
        amari = a % mi
        A_list[i] = amari
        if amari != 0:
            ans = min(ans,amari)

print(ans)

import functools
import math
N=int(input())
A=list(map(int,input().split()))
print(functools.reduce(math.gcd,A))

import heapq

n = int(input())
A = [int(a) for a in input().split()]

heapq.heapify(A)

while True:
    temp = heapq.heappop(A)
    A = [a%temp for a in A if a % temp != 0] + [temp]
    if len(A) == 1:
        break

print(A[0])

N=int(input())
A=list(map(int, input().split()))

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


ans=0
for a in A:
	ans=gcd(ans, a)
print(ans)

import functools
def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)

def gcd(nums):
    return functools.reduce(euclid, nums)



n=int(input())
a=[int(i) for i in input().split()]

print((gcd(a)))


from math import gcd
from functools import reduce

n = int(input())
a = list(map(int, input().split()))
print((reduce(gcd, a)))


from fractions import gcd
from functools import reduce
N = input()

List = list(map(int, input().split()))

print((reduce(gcd, List)))


import math
N=int(input())
A=list(map(int,input().split()))
x=A[0]
for a in A:
    x=math.gcd(x,a)
print(x)


import math
N = int(input())
A = list(map(int, input().split()))

g = A[0]
for i in range(1, N):
  g = math.gcd(g, A[i])

print(g)

from math import gcd

N = int(input())
A = list(map(int, input().split()))
min_ = 0
gcd_ = A[0]
for i in range(1, N):
    gcd_ = gcd(A[i], gcd_)
print(gcd_)

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


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

x = a[0]
for i in range(1,n):
    y = a[i]
    x,y = max(x,y),min(x,y)
    while y!= 0:
        x,y = y,x%y
print(x)

import sys
import heapq

input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    heapq.heapify(A)
    while True:
        m1 = heapq.heappop(A)
        try:
            m2 = heapq.heappop(A)
        except IndexError:
            print(m1)
            break
        m2 %= m1
        heapq.heappush(A, m1)
        if m2 > 0:
            heapq.heappush(A, m2)


def __starting_point():
    main()

__starting_point()

import sys
import math


inint = lambda: int(sys.stdin.readline())
inintm = lambda: list(map(int, sys.stdin.readline().split()))
inintl = lambda: list(inintm())
instrm = lambda: list(map(str, sys.stdin.readline().split()))
instrl = lambda: list(instrm())

n = inint()
A = inintl()

m = min(A)

mod_min = 10**9

for a in A:
    if a % m == 0:
        continue
    mod_min = min(mod_min, a % m)

if mod_min == 10**9:
    print(m)
else:
    print((math.gcd(m, mod_min)))


# 62 C - Monsters Battle Royale
import math
import functools
N = int(input())
A = list(map(int,input().split()))

# すべての要素の GCD
ans = functools.reduce(math.gcd,A)
print(ans)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    before = A
    after = []
    for _ in range(pow(10, 9)):
        x = before[0]
        if len(before) == 1:
            print(x)
            return
        after.append(x)
        for i in range(1, len(before)):
            y = before[i]%x
            if y != 0:
                after.append(y)
        after.sort()
        before = after
        after = []

def __starting_point():
    main()

__starting_point()

from math import gcd
from functools import reduce

n = int(input())
print(reduce(gcd, list(map(int, input().split()))))

import sys
input = sys.stdin.readline
from math import gcd
from functools import reduce


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A):
    return reduce(gcd, A)


def __starting_point():
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print(("%s" % str(outputs)))

__starting_point()

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

n = int(input())
print(gcd_list(list(map(int,input().split()))))

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

import math
g = math.gcd(a[0], a[1])
for i in range(2, n):
    g = math.gcd(g, a[i])

print(g)

import math
from functools import reduce
n=int(input())
a=list(map(int,input().split()))

def gcd(numbers):
    return reduce(math.gcd, numbers)

print(gcd(a))

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

from math import gcd
from functools import reduce

ans = reduce(gcd,L)
print(ans)

import math
n = int(input())
a = list(map(int,input().split()))
ans = a[0]
for v in a[1:]:
  ans = math.gcd(ans,v)
print(ans)

from math import gcd

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in a:
    ans = gcd(ans, i)
print(ans)


n = int(input())

al = list(map(int, input().split())) 

import math

temp = al[0]

for i in range(1,n):
    temp = math.gcd(temp,al[i])
    
print(temp)

N=int(input())
mns=list(map(int,input().split()))
atk=min(mns)
while 1:
    mns=list(filter(lambda x: x!=0, map(lambda x: x%atk, mns)))
    if not mns:
        break
    mns+=[atk]
    atk=min(mns)
print(atk)

from math import gcd
from functools import reduce

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

print((reduce(gcd, a)))


import math
N = int(input())
A = list(map(int,input().split()))
gcd = A[0]
for i in range(1,N):
    gcd = math.gcd(gcd,A[i])
print(gcd)

n = int(input())
*A, = list(map(int, input().split()))
import math
ans = A[0]
for a in A:  ans = math.gcd(ans, a)
print(ans)


from math import *
n = int(input())
a = sorted(map(int, input().split()))
g = a[0]
for i in range(1,n):
  g = gcd(g, a[i])
print(g)

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

while len(num_list) >= 2:
    x = min(num_list)
    num_list = [i % x for i in num_list if (i % x != 0)]
    num_list.append(x)
 
print(num_list[0])

import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    L = sorted(LI())
    past = L[0]
    
    for i in L:
        past = math.gcd(i, past)
    print(past)

def __starting_point():
    main()
__starting_point()

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

import math

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

ans = math.gcd(al[0], al[1])

for i in range(2, n):
    ans = math.gcd(ans, al[i])

print(ans)


import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(gcd, numbers)

n = int(input())
s = list(map(int,input().split()))
print(gcd_list(s))

import math

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

ans = 10**10
for i in range(1, n):
    ans = min(ans, math.gcd(a[0], a[i]))
print(ans)

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

def gcd(p, q):
    if q == 0:
        return p
    else:
        return gcd(q, p % q)

g = gcd(a[0], a[1])
for i in range(2, n):
    g = gcd(g, a[i])

print(g)

import math
N = int(input())
A = list(map(int, input().split()))
g = math.gcd(A[0],A[1])
for i in range(2,N):
    g = math.gcd(g,A[i])
print(g)    

import math
n=int(input())
a=[*map(int,input().split())]
ans=0
for i in a:
    ans=math.gcd(ans,i)
print(ans)

import math
n = int(input())
a = list(map(int, input().split()))
ans = a[0]
for i in range(1,n):
    ans = math.gcd(ans,a[i])
print(ans)


import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

n = int(input())
a = list(map(int, input().split()))
ans = gcd_list(a)
print(ans)

import functools
import math


N = int(input())
A = list(map(int, input().split()))

print((functools.reduce(math.gcd, A)))


from math import *
N=int(input())
A=list(map(int,input().split()))
c=A[0]
for i in range(N):
    c=gcd(A[i],c)
print(c)

import math
N=int(input())
a=list(map(int,input().split()))
b=math.gcd(a[0],a[1])
for i in range(N-1):
    b=math.gcd(a[i+1], b)
print(b)


N = int(input())
A = list(map(int,input().split()))
m = min(A)
n = 0
while m != n:
    m = min(A)
    a = [m]
    for i in A:
        i %= m
        if i != 0:
            a.append(i)
    A = a
    n = min(A)
print(n)

import math

n = int(input())
a = list(map(int, input().split()))
ans = a[0]
for i in range(n):
    ans = math.gcd(a[i], ans)
print(ans)


from math import gcd
from functools import reduce
n = int(input())
A = list(map(int, input().split()))
def GCD(*numbers):
    return reduce(gcd, numbers)
g = GCD(*A)
print(g)


from math import gcd
def readinput():
    n=int(input())
    a=list(map(int,input().split()))
    return n,a

def main(n,a):
    ans=gcd(a[0],a[1])
    for i in range(2,n):
        ans=gcd(ans,a[i])
    return ans

def __starting_point():
    n,a=readinput()
    ans=main(n,a)
    print(ans)

__starting_point()

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

a.sort()

def mod():
    for i in range(1, len(a)):
        # print("--------")
        # print(a[i])
        # print(a[i] % a[0])
        # print("--------")
        if(a[i] % a[0] != 0):
            a[i] = a[i] % a[0]
        else:
            a[i] = a[0]
        # print(a[i])
    a.sort()
    return a

# for i in range(4):
#     a = mod()
#     print(a)

while(a.count(a[0]) != len(a)):
    a = mod()
    # print(a)

print(a[0])

import math
from functools import reduce

def gcd(*n):
    return reduce(math.gcd, n)

n = int(input())
*a, = map(int, input().split())
print(gcd(*a))

# author:  Taichicchi
# created: 14.09.2020 22:18:44

import sys
from math import gcd

N = int(input())

A = list(map(int, input().split()))

ans = gcd(A[0], A[1])
for i in range(2, N):
    ans = gcd(ans, A[i])

print(ans)


from math import gcd


def lgcd(l):
    res = l[0]
    for i in range(1, len(l)):
        res = gcd(res, l[i])

    return res


n = int(input())
print((lgcd(list(map(int, input().split())))))


import bisect,collections,copy,itertools,math,string
import sys
from functools import reduce
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    from functools import reduce
    def gcd(*numbers):
        return reduce(math.gcd, numbers)
    n = I()
    lst = LI()
    ans = gcd(*lst)
    print(ans)
main()            


import math
from functools import reduce
N = int(input())
A = list(map(int, input().split()))

print(reduce(math.gcd, A))

from math import gcd
from functools import reduce

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

print(reduce(gcd, A))

N = int(input())
A = list(map(int,input().split()))

import math

def gcd_list(nums):
  gcd = nums[0]
  for i in range(1,len(nums)):
    gcd = math.gcd(gcd,nums[i])
  return gcd

print(gcd_list(A))

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

def gcd(x,y):
    if y > x:
        x,y = y,x
    if x%y == 0:
        return y
    else:
        return gcd(y,x%y)
        
from functools import reduce
ans = reduce(gcd,L)
print(ans)

from math import *

N=int(input())
A=list(map(int,input().split()))

ans=A[0]

for i in range(1,N):
  ans=gcd(ans,A[i])

print(ans)


import numpy as np

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

gcd = np.frompyfunc(np.gcd,2,1)

print(gcd.reduce(a))

from math import gcd
N = int(input())
A = list(map(int,input().split()))
num = gcd(A[0],A[1])
for i in range(2,N):
    num = gcd(num,A[i])
print(num)

n = int(input())
a = list(map(int, input().split()))
if max(a) != min(a):
    while a.count(0) != len(a)-1:
        a.sort()
        b = [a[0]]
        for i in a[1:]:
            if i%a[0] != 0:
                b.append(i%a[0])
        a = b
    print(max(a))
else:
    print(a[0])

N=int(input())
A=list(map(int,input().strip().split()))
A.sort()

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

ans=A[0]
for n in range(N):
    ans=gcd(ans,A[n])

print(ans)

from math import gcd
n = int(input())
a = list(map(int, input().split()))
res = 0
for i in range(n):
    res = gcd(res, a[i])
print(res) 

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

import math
ans = a[0]
for i in range(1, n):
    ans = math.gcd(ans, a[i])
print(ans)

def gcd(x, y):
    if(y > x):
        tmp = y
        y = x
        x = tmp

    while(int(x%y)>0):
        r = x%y
        x = y
        y = r

    return y
        


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

ans = gcd(a[0], a[1])
for i in range(1, n-1):
    ans = min(ans, gcd(a[i], a[i+1]))

print(ans)

import numpy as np
from functools import reduce
_ = input()
print(reduce(np.gcd, map(int,input().split())))

import numpy as np

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

ans = a[0]

for i in range(1,len(a)):
    ans = np.gcd(a[i],ans)

print(ans)

from math import gcd

N = int(input())
A = list(map(int,input().split()))

res = 0

for i in range(N):
   res = gcd(res,A[i])

print(res)

import math
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N):
    ans = math.gcd(ans, A[i])

print(ans)

import math
N = int(input())
lsA = list(map(int,input().split()))
gcd = lsA[0]
for i in range(1,N):
    gcd = math.gcd(gcd,lsA[i])
print(gcd)

#https://note.nkmk.me/python-gcd-lcm/
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

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

print(gcd_list(a))

# -*- coding: utf-8 -*-
"""
Created on Mon Sep 14 17:37:26 2020

@author: liang
"""
N = int(input())
A = [int(x) for x in input().split()]

from math import gcd

A.sort()
g = A[0]
for i in range(1,N):
    g = gcd(g,A[i]) 
    #print(g)
print(g)

import math
n= int(input())
a_list = list(map(int, input().split()))
gcd = a_list[0]
for i in range(1,n):
    gcd = math.gcd(gcd,a_list[i])
    
    
print(gcd)

from heapq import heappop,heappush
N = int(input())
A = list(map(lambda x: -1*int(x),input().split()))

now = -1 * heappop(A)
while(A):
    next = -1 * heappop(A)
    if now % next != 0:
        heappush(A,-1*(now%next))
    now = next
print(now)

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


n = int(input())
l = list(map(int,input().split()))
l.sort()

tmp = gcd(l[0],l[1])
for i in range(2,len(l)):
    tmp = gcd(tmp,l[i])

print(tmp)

import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

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

print((gcd_list(l)))


def get_gcd(a, b):
    if a<b:a,b=b,a
    if b == 0 :return a
    else:return get_gcd(b,a%b)

n = int(input().rstrip())
a = list(map(int,input().rstrip().split()))

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

from math import gcd
n = int(input())
a = list(map(int, input().split()))

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

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

x = a[0]
for i in range(1,n):
    x,y = max(x,a[i]),min(x,a[i])
    while y!=0:x,y=y,x%y
print(x)

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

import math
N = int(input())
A = list(map(int, input().split()))

# 攻撃：最大公約数を求める操作
g = A[0]
for i in range(1, N):
  g = math.gcd(g, A[i])

print(g)

N = int(input())
A = list(map(int, input().split()))

l = 0
while True:
  A = sorted(A)
  m = A[l]
  for i in range(l+1, N): A[i] %= m
  l = A.count(0)
  if l == N-1: break

A = sorted(A)
print(A[-1])

import math 
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

n = int(input())
a = [int(i) for i in input().split()]
if 1 in a:
    ans = 1
else:
    ans = gcd_list(a)
print(ans)

import math
N = int(input())
A = list(map(int,input().split()))
now = A[0]
for i in range(1,N):
    now = math.gcd(A[i],now)
print(now)


from math import gcd

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


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

from functools import reduce
from math import gcd
n = int(input())
xlist = list(map(int,input().split()))
print(reduce(gcd, xlist))

import math
from functools import reduce

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

def gcd(*numbers):
    return reduce(math.gcd, numbers)

print(gcd(*a))

from math import gcd

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

ans = 0
for a in A:
    ans = gcd(ans, a)
print(ans)

from functools import reduce
from math import gcd

n = int(input())
a = list(map(int,input().split()))
g = reduce(gcd,a)
print(g)

N = int(input())
A = list(map(int, input().split()))

g = A[0]
import math
for i in range(1, N):
    g = math.gcd(g, A[i])

print(g)

import math

N = int(input())
A_list = list(map(int, input().split()))

ans = A_list[0]
for i in range(N-1):
    ans = math.gcd(A_list[i+1], ans)

print(ans)

import sys
import math

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inl = lambda: [int(x) for x in sys.stdin.readline().split()]
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))


def solve():
    n = ini()
    A = inl()
    g = A[0]
    for i in range(1, n):
        g = math.gcd(g, A[i])
    return g


print(solve())


from math import gcd
n = int(input())
a = list(map(int,input().split()))
ans = a[0]
for i in a[1:]:
    ans = gcd(ans,i)
print(ans)

N=int(input())
A=map(int,input().split())
import math
from functools import reduce

print(reduce(math.gcd, A))

import sys
from math import gcd
from functools import reduce

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = list(map(int, read().split()))

    print((reduce(gcd, A)))
    return


def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python3

#import
#import math
#import numpy as np
N = int(input())
A = list(map(int, input().split()))

def gcd(x, y):
    if x < y:
        t = x
        x = y
        y = t

    if y == 0:
        return x

    else:
        return gcd(y, x % y)

a = gcd(A[0], A[1])

for i in range(2, N):
    a = gcd(a, A[i])

print(a)


import math
from functools import reduce

N = int(input())
A = list(map(int,input().split()))

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  
print(gcd_list(A))

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