Problem:
 Score : 300 points    Problem Statement There are N integers, A_1, A_2, ..., A_N , written on the blackboard.  You will choose one of them and replace it with an integer of your choice between 1 and 10^9 (inclusive), possibly the same as the integer originally written.  Find the maximum possible greatest common divisor of the N integers on the blackboard after your move.      Constraints  All values in input are integers.  2 \leq N \leq 10^5  1 \leq A_i \leq 10^9       Output Input is given from Standard Input in the following format:  N  A_1  A_2  ...  A_N       Output Print the maximum possible greatest common divisor of the N integers on the blackboard after your move.       Sample Input 1 3
7 6 8      Sample Output 1 2  If we replace 7 with 4 , the greatest common divisor of the three integers on the blackboard will be 2 , which is the maximum possible value.       Sample Input 2 3
12 15 18      Sample Output 2 6       Sample Input 3 2
1000000000 1000000000      Sample Output 3 1000000000  We can replace an integer with itself.

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

from fractions import gcd

L=[0]*(n+1)
R=[0]*(n+1)
M=[0]*n

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

for i in range(n,1,-1):
    R[i-1]=gcd(R[i],A[i-1])

max_M=0
for i in range(n):
    M[i]=gcd(L[i],R[i+1])
    if max_M < M[i]: max_M=M[i]
print(max_M)

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

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

s1 = [0]*(n + 1)
s2 = [0]*(n + 1)
for i in range(1, n):
    s1[i] = gcd(s1[i-1], a[i-1])
    s2[n-i] = gcd(s2[n-i+1], a[n-i])

ans = 0
for i in range(n):
    ans = max(ans, (gcd(s1[i], s2[i+1])))

print(ans)

Solution (Python):

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

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

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

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

ans = 0
for i in range(n):
    ans = max(ans, gcd(left[i], right[i + 1]))
print(ans)

Solution (Python):
import sys
from fractions import gcd

N=input()
A=map(int, sys.stdin.readline().split())

L=[]
R=[]

for i,a in enumerate(A):
    if i==0:
        L.append(a)
    else:
        L.append( gcd(L[-1],a) )

for i,a in enumerate(A[::-1]):
    if i==0:
        R.append(a)
    else:
        R.append( gcd(R[-1],a) )
R=R[::-1]

ans=float("-inf")
for i in range(N):
    if i==0:
        ans=max(ans,R[i+1])
    elif i==N-1:
        ans=max(ans,L[i-1])
    else:
        ans=max( ans,gcd(L[i-1],R[i+1]) )

print ans

Solution (Python):
import fractions

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

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

    left = [0] * (n + 1)
    right = [0] * (n + 1)
    for i in range(n):
        left[i + 1] = (fractions.gcd(left[i],num_list[i]))
        right[n - i - 1] = (fractions.gcd(right[n - i],num_list[n - 1 - i]))
    
    ans = 0
    for i in range(n):
        ans = max(ans,fractions.gcd(left[i],right[i + 1]))

    print(ans)

if __name__ == '__main__':
    main()

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


ide_ele = 0


num=2**(n-1).bit_length()
seg=[ide_ele]*2*num

from fractions import gcd

def segfunc(x,y):
    return gcd(x,y) 

def init(init_val):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

init(A)
ans=-1
for i in range(n):
    ans=max(ans, gcd(query(0,i),query(i+1,n)))
print(ans)

Solution (Python):
from fractions import gcd

n = int(input())
*A, = map(int, input().split())
L, R = [0]*(n+1), [0]*(n+1)
for i, (a, b) in enumerate(zip(A, A[::-1])):
    L[i+1] = gcd(L[i], a)
    R[i+1] = gcd(R[i], b)
L, R = L[:n], R[:n][::-1]
print(max(gcd(l, r) for l, r in zip(L, R)))

Solution (Python):
from fractions import gcd

n = int(input())
*A, = map(int, input().split())
B = A[::-1]
L, R = [0]*(n+1), [0]*(n+1)
for i in range(n):
    L[i+1] = gcd(L[i], A[i])
    R[i+1] = gcd(R[i], B[i])
L, R = L[:n], R[:n][::-1]
print(max(gcd(l, r) for l, r in zip(L, R)))

Solution (Python):
from fractions import gcd

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

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

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

ans = 0
for i in range(n):
    ans = max(ans, gcd(left[i], right[i+1]))
print(ans)

Solution (Python):
from fractions import gcd


class SegmentTree():
    _data = []
    _offset = 0
    _size = 0

    def __init__(self, size):
        _size = size
        t = 1
        while t <= size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

    def update_all(self, iterable):
        self._data[self._offset:self._offset+self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            self._data[i] = gcd(self._data[i * 2 + 1], self._data[i * 2 + 2])

    def update(self, index, value):
        i = self._offset + index
        self._data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            self._data[i] = gcd(self._data[i * 2 + 1], self._data[i * 2 + 2])

    def query(self, start, stop):
        result = 0
        l = start + self._offset
        r = stop + self._offset
        while l < r:
            if l & 1 == 0:
                result = gcd(result, self._data[l])
            if r & 1 == 0:
                result = gcd(result, self._data[r - 1])
            l = l // 2
            r = (r - 1) // 2
        return result

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

st = SegmentTree(N)
st.update_all(A)

result = st.query(1, N)
for i in range(1, N - 1):
    result = max(result, gcd(st.query(0, i), st.query(i + 1, N)))
result = max(result, st.query(0, N - 1))
print(result)

Solution (Python):
def main():
  from fractions import gcd
  n=int(input())
  num=list(map(int,input().split()))
      
  gcdl=[0]*n
  gcdr=[0]*n
  gcdl[0],gcdr[0]=num[0],num[-1]
  for i in range(n-1):
    gcdl[i+1]=gcd(num[i+1],gcdl[i])
    gcdr[i+1]=gcd(num[-i-2],gcdr[i])

  ans=0
  for i in range(n):
    if i!=0 and i!=n-1:
      test=gcd(gcdl[i-1],gcdr[-i-2])
    elif i==0:
      test=gcdr[-2]
    else:
      test=gcdl[-2]

    if test>ans:
      ans=test
  print(ans)
 
if __name__=='__main__':
  main()

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

a = []
i = 1
while True:
  if A[0] % i == 0:
    a += [i, A[0]//i]
  i += 1
  if i**2 > A[0]:
    break
    
b = []
i = 1
while True:
  if A[1] % i == 0:
    a += [i, A[1]//i]
  i += 1
  if i**2 > A[1]:
    break

ans = 1
for i in a:
  counter = 0
  for p in A:
    if p % i == 0:
      counter += 1
  if counter >= N-1:
    ans = max(ans, i)
for i in b:
  counter = 0
  for p in A:
    if p % i == 0:
      counter += 1
  if counter >= N-1:
    ans = max(ans, i)
      
print(ans)

Solution (Python):
from fractions import gcd

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

L = [0] * (N+1)
R = [0] * (N+1)

for i in range(N):
  L[i+1] = gcd(L[i], A[i])
  
for i in range(N,0,-1):
  R[i-1] = gcd(R[i], A[i-1])
  
ans = 1
for i in range(N):
  ans = max(ans, gcd(L[i], R[i+1]))

print(ans)

Solution (Python):
import fractions
from functools import reduce
n=int(input())
a=list(map(int,input().split()))


l=[0]
r=[0]
for i in range(0,n):
    l.append(fractions.gcd(l[i],a[i]))
    r.append(fractions.gcd(r[i],a[n-i-1]))


r=r[::-1]
ans=[]
for i in range(n):
    ans.append(fractions.gcd(l[i],r[i+1]))
print(max(ans))

Solution (Python):
from fractions import gcd


class SegmentTree():
    _data = []
    _offset = 0

    def __init__(self, size):
        t = 1
        while t <= size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

    def update_all(self, iterable):
        for i, v in enumerate(iterable):
            self._data[i + self._offset] = v
        for i in range(self._offset - 1, -1, -1):
            self._data[i] = gcd(self._data[i * 2 + 1], self._data[i * 2 + 2])

    def update(self, index, value):
        i = self._offset + index
        self._data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            self._data[i] = gcd(self._data[i * 2 + 1], self._data[i * 2 + 2])

    def _query(self, start, stop, index, left, right):
        if right <= start or stop <= left:
            return 0
        if start <= left and right <= stop:
            return self._data[index]
        a = self._query(start, stop, index * 2 + 1, left, (left + right) // 2)
        b = self._query(start, stop, index * 2 + 2, (left + right) // 2, right)
        return gcd(a, b)

    def query(self, start, stop):
        return self._query(start, stop, 0, 0, self._offset + 1)


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

st = SegmentTree(N)
st.update_all(A)

result = st.query(1, N)
for i in range(1, N - 1):
    result = max(result, gcd(st.query(0, i), st.query(i + 1, N)))
result = max(result, st.query(0, N - 1))
print(result)

Solution (Python):
from fractions import gcd


class SegmentTree():
    _data = []
    _offset = 0

    def __init__(self, size):
        t = 1
        while t <= size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

    def update(self, index, value):
        i = self._offset + index
        self._data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            self._data[i] = gcd(self._data[i * 2 + 1], self._data[i * 2 + 2])

    def _query(self, start, stop, index, left, right):
        if right <= start or stop <= left:
            return 0
        if start <= left and right <= stop:
            return self._data[index]
        a = self._query(start, stop, index * 2 + 1, left, (left + right) // 2)
        b = self._query(start, stop, index * 2 + 2, (left + right) // 2, right)
        return gcd(a, b)

    def query(self, start, stop):
        return self._query(start, stop, 0, 0, self._offset + 1)


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

st = SegmentTree(N)
for i in range(N):
    st.update(i, A[i])

result = st.query(1, N)
for i in range(1, N - 1):
    result = max(result, gcd(st.query(0, i), st.query(i + 1, N)))
result = max(result, gcd(st.query(0, i), st.query(0, N - 1)))
print(result)

Solution (Python):
n = int(input())
l = list(map(int, input().split()))

l2 = list(reversed(l))




from fractions import gcd
L, R = [0], [0]
for i in range(n):
    L.append(gcd(L[i],l[i]))
    R.append(gcd(R[i],l2[i]))

R = list(reversed(R))

g = []
for j in range(n):
    g.append(gcd(L[j],R[j+1]))
print(max(g))

Solution (Python):
import fractions

N=int(input())

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

M=[2]
while M[-1]<N:
    M.append(M[-1]*2)

A=A+[0]*(M[-1]-len(A))
A=A[::-1]

for i in range(len(A)-1):
    A.append(fractions.gcd(A[2*i],A[2*i+1]))

A=A[::-1]



ans=0
for index in range(len(A)-M[-1],len(A)-M[-1]+N):
    temp=A[index+1] if index%2==1 else A[index-1]
    index=((index-1) if index%2==1 else (index-2))//2
    
    while index!=0:
        if index%2==1:
            temp=fractions.gcd(temp,A[index+1])
            index=(index-1)//2
        else:
            temp=fractions.gcd(A[index-1],temp)
            index=(index-2)//2
        
    ans=max(temp,ans)
    
print(ans)

Solution (Python):
from fractions import gcd
N = int(input())
A=list(map(int,input().split()))
L=[0]*N
R=[0]*N
M=[0]*N
L[0]=A[0]
R[-1]=A[-1]
for i in range(1,N):
  L[i]=gcd(L[i-1],A[i])
  R[-i-1]=gcd(R[-i],A[-i-1])
for i in range(N):
  if i == 0:
    M[i]=R[i+1]
  elif i == N-1:
    M[i]=L[i-1]
  else:
    M[i]=gcd(L[i-1],R[i+1])
print(max(M))

Solution (Python):
import fractions as f

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

left = [0] * (n+1)
left[0] = 0
for i in range(1, n+1):
    left[i] = f.gcd(left[i-1], a[i-1])

right = [0] * (n+1)
right[n] = 0
for i in range(1, n+1):
    right[n-i] = f.gcd(right[n-i+1], a[n-i])

ans = 0
for i in range(n):
    ans = max(ans, f.gcd(left[i], right[i+1]))
print(ans)

Solution (Python):

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


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

L = [0 for _ in range(n)]
R = [0 for _ in range(n)]
L[0] = A[0]
R[-1] = A[-1]

for i in range(1, n):
    L[i] = gcd(L[i-1], A[i])
    R[n - i - 1] = gcd(R[n - i], A[n - i - 1])
ans = 1
for i in range(n):
    if i == 0:
        ans = R[i + 1]
    elif i == n-1:
        ans = max(ans, L[i-1])
    else:
        ans = max(ans, gcd(L[i - 1], R[i+1]))

print(ans)

Solution (Python):
import fractions
n = int(input())
a = list(map(int,input().split()))
ans = 0
l = [0]*(n+1)
r = [0]*(n+1)
for i in range(n):
    l[i+1] =  fractions.gcd(l[i],a[i])
for i in range(n-1,0,-1):
    r[i] =  fractions.gcd(r[i+1],a[i])
for i in range(n):
    L = l[i]
    R = r[i+1]
    ans = max(ans,fractions.gcd(L,R))
print(ans)

Solution (Python):
from subprocess import*
call(('pypy3','-c',"""

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

l=make_divisors(a[0])
l2=make_divisors(a[1])
le=len(l)
le2=len(l2)         
an=[0]*le
an2=[0]*le2
for i in range(n):
    for j in range(le):
        if a[i]%l[j]==0:
            an[j]+=1
    for j in range(le2):
        if a[i]%l2[j]==0:
            an2[j]+=1
ans=1
ans2=1
for i in range(le):
    if an[i]>=n-1:
        ans=max(ans,l[i])
for i in range(le2):
    if an2[i]>=n-1:
        ans2=max(ans2,l2[i])

print(max(ans,ans2))


"""))

Solution (Python):


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

from fractions import gcd
def lcm(x, y):
    return x * y // gcd(x, y)

gcds = [0] * N
gcds[0] = A[0]
rev_gcds = [0] * N
rev_gcds[-1] = A[-1]

for i in range(1, N):
    gcds[i] = gcd(A[i], gcds[i-1])
    rev_gcds[N-1-i] = gcd(A[N-1-i],  rev_gcds[N-i])

ans = 1
for i in range(N):
    if i == 0:
        tmp = rev_gcds[i+1]
    elif i == N-1:
        tmp = gcds[i-1]
    else:
        tmp = gcd(gcds[i-1], rev_gcds[i+1])
    ans = max(ans, tmp)

print(ans)

Solution (Python):
import fractions
import itertools
from functools import reduce

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

l = [0]*(n+1)
r = [0]*(n+1)

for i in range(n):
    l[i+1] = fractions.gcd(l[i], a[i])
    r[n-i-1]= fractions.gcd(r[n-i], a[n-i-1])

ans = 0
for i in range(n):
    ans = max(fractions.gcd(l[i], r[i+1]), ans)

print(ans)

Solution (Python):
from collections import OrderedDict
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
def factorize(m):
    d = []
    for i in range(1, int(m**0.5)+1):
        if m % i == 0:
            d.append(i)
            if i != m // i:
                d.append(m//i)
    return d
def main():
    N = int(input())
    A = list(map(int, input().split()))
    l = list(set(factorize(A[0]) + factorize(A[1])))
    l.sort(reverse=True)
    d = OrderedDict()
    for i in l:
    	d[i] = 0
    for i in A:
        for j in d:
            if i % j == 0:
                d[j] += 1
    m = 1
    for k in d:
        if d[k] >= N-1:
            print(k)
            return
    print(1)
main()

Solution (Python):
from fractions import gcd
from itertools import accumulate

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

    def pleaceAC():
        left = list(accumulate([0]+A, gcd))
        right = list(accumulate(reversed(A+[0]), gcd))
        for i in range(N):
            yield gcd(left[i], right[~(i+1)])

    print(max(pleaceAC()))


main()

Solution (Python):
from fractions import gcd
N = int(input())
*A, = map(int, input().split())

left = [0] * (N + 1)
right = [0] * (N + 1)


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


for i in reversed(range(N)):
    right[i] = gcd(right[i+1], A[i])

ans = 0
for i in range(N):
    ans = max(ans, gcd(left[i], right[i+1]))
print(ans)

Solution (Python):
import fractions

N,*a=map(int,open(0).read().split())
L=[]
L_base=a[0]
b=a[:]
b.reverse()
R=[]
R_base=b[0]
for i in range(N-1):
    L_base=fractions.gcd(L_base,a[i])
    L.append(L_base)
    R_base=fractions.gcd(R_base,b[i])
    R.append(R_base)
LR=[R[-1]]
for i in range(N-2):
    LR.append(fractions.gcd(L[i],R[-2-i]))
LR.append(L[-1])
print(max(LR))

Solution (Python):
from fractions import gcd

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

class SegmentTree:
    def __init__(self, n, func=lambda x, y: min(x, y), ide=float("inf")):
        self.n = 2 ** (n-1).bit_length()
        self.data = [ide] * (self.n*2)
        self.ide, self.func = ide, func
    
    def build(self, data):
        for i, x in enumerate(data):
            self.data[self.n+i] = x
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def update(self, i, x):
        i += self.n
        self.data[i] = x
        while i > 1:
            i //= 2
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def query(self, l, r):
        l += self.n; r += self.n 
        res = self.ide
        while l < r:
            if l & 1:
                res = self.func(res, self.data[l])
                l += 1
            if r & 1:
                res = self.func(res, self.data[r-1])
            l >>= 1; r >>= 1
        return res
    
    def get(self, i):
        return self.data[self.n + i]

s = SegmentTree(n, lambda x, y: gcd(x, y), 0)
s.build(a)
ans = 0
for i in range(n):
    ans = max(ans, gcd(s.query(0, i), s.query(i+1, n)))
print(ans)

Solution (Python):
from fractions import gcd
from functools import reduce

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

left = [0] * (n + 1)
right = [0] * (n + 1)
for i in range(n):
   left[i+1] = gcd(left[i], a[i])
   right[n-i-1] = gcd(right[n-i], a[n-1-i])

ans = 0
for i in range(n):
   ans = max(ans, gcd(left[i], right[i+1]))
print(ans)

Solution (Python):
import sys
from fractions import gcd
sys.setrecursionlimit(1000000)

def main():

    def cul(n,x):
        l=len(x)
        b=[x[i] for i in range(l)]
        b.pop(n)
        tmp=b[0]
        for i in range(1,l-1):
            tmp=gcd(tmp,b[i])
        return tmp

    ans=0
    for i in range(p):
        s=cul(i,a[:p])
        if s>ans: ans=s
    print(ans)

if __name__=='__main__':
    N, *a = map(int, sys.stdin.read().split())
    p=50
    if p>N: p=N
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

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

    def cul(n,x):
        l=len(x)
        b=[x[i] for i in range(l)]
        b.pop(n)
        tmp=b[0]
        for i in range(1,l-1):
            tmp=gcd(tmp,b[i])
        return tmp

    ans=0
    for i in range(p):
        s=cul(i,a[:p])
        if s>ans: ans=s
    print(ans)

if __name__=='__main__':
    N, *a = map(int, sys.stdin.read().split())
    p=50
    if p>N: p=N
    main()

Solution (Python):
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)

def main():
    @lru_cache(maxsize=None)
    def gcd(a, b):
        if a % b == 0:
            return b
        else:
            return gcd(b, a % b)

    def cul(n,x):
        l=len(x)
        b=[x[i] for i in range(l)]
        b.pop(n)
        tmp=b[0]
        for i in range(1,l-1):
            tmp=gcd(tmp,b[i])
        return tmp

    ans=0
    for i in range(p):
        s=cul(i,a[:p])
        if s>ans: ans=s
    print(ans)

if __name__=='__main__':
    N, *a = map(int, sys.stdin.read().split())
    p=50
    if p>N: p=N
    main()

Solution (Python):
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)

@lru_cache(maxsize=None)
def main():

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

    def cul(n,x):
        l=len(x)
        b=[x[i] for i in range(l)]
        b.pop(n)
        tmp=b[0]
        for i in range(1,l-1):
            tmp=gcd(tmp,b[i])
        return tmp

    N, *a = map(int, sys.stdin.read().split())
    p=50
    if p>N: p=N

    ans=0
    for i in range(p):
        s=cul(i,a[:p])
        if s>ans: ans=s
    print(ans)

if __name__=='__main__':
  main()

Solution (Python):
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)

@lru_cache(maxsize=None)
def main():

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

    def cul(n,x):
        l=len(x)
        b=[x[i] for i in range(l)]
        b.pop(n)
        tmp=b[0]
        for i in range(1,l-1):
            tmp=gcd(tmp,b[i])
        return tmp

    N, *a = map(int, sys.stdin.read().split())
    p=50
    if p>N: p=N

    ans=0
    for i in range(p):
        s=cul(i,a[:p])
        if s>ans: ans=s
    print(ans)

if __name__=='__main__':
  main()

Solution (Python):
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)

@lru_cache(maxsize=None)
def main():

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

    N, *A = map(int, sys.stdin.read().split())
    L = [0] * (N + 2)
    R = [0] * (N + 2)
    for i in range(N):
        L[i + 2] = gcd(L[i + 1], A[i])
        R[-i - 2] = gcd(R[-i - 1], A[-i - 1])

    print(max(gcd(L[i], R[i + 1]) for i in range(1, N + 1)))

if __name__=='__main__':
  main()

Solution (Python):
import sys
from functools import lru_cache

@lru_cache(maxsize=None)
def gcd(a, b):
    if b == 0:
        return a
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)


N, *A = map(int, sys.stdin.read().split())
L = [0] * (N + 2)
R = [0] * (N + 2)
for i in range(N):
    L[i + 2] = gcd(L[i + 1], A[i])
    R[-i - 2] = gcd(R[-i - 1], A[-i - 1])

print(max(gcd(L[i], R[i + 1]) for i in range(1, N + 1)))

Solution (Python):
from fractions import gcd

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

left = [0] * (n + 1)
right = [0] * (n + 1)

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

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

ans = 0
for i in range(n):
    ans = max(ans, gcd(left[i], right[i + 1]))

print(ans)

Solution (Python):
def gcdf(a):
    a.sort()
    a0=a[0]
    a=[int(x%a0) for x in a if x%a0 != 0]
    if len(a)==0:
        return a0
    else:
        a.append(a0)
        a0=min(a)
        return gcdf(a) 

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

if n==2:
    print(max(a))
elif n<2**8:
    gcdv=0
    for i in range(n):
        acpy=list(a)
        del acpy[i]
        gcdx=gcdf(acpy)
        if gcdx>gcdv:
            gcdv=gcdx
    print(gcdv)
else:
    m=int(n/100)
    ns=int(n/m)
    rgcd=[]
    for mi in range(m):
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
        gcdm=gcdf(am)
        rgcd.append(gcdm)
    gcdv=0

    for mi in range(m):
        rgcd1=list(rgcd)
        del rgcd1[mi]
        gcdrg1=gcdf(rgcd1)
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]

        for i in range(len(am)):
            acpy=list(am)


            acpy[i]=gcdrg1
            gcdx=gcdf(acpy)
            if gcdx>gcdv:
                gcdv=gcdx
    print(gcdv)

Solution (Python):
def gcdf(a):
    a.sort()
    a0=a[0]
    a=[int(x%a0) for x in a if x%a0 != 0]
    if len(a)==0:
        return a0
    else:
        a.append(a0)
        a0=min(a)
        return gcdf(a) 

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

if n==2:
    print(max(a))
elif n<2**8:
    gcdv=0
    for i in range(n):
        acpy=list(a)
        del acpy[i]
        gcdx=gcdf(acpy)
        if gcdx>gcdv:
            gcdv=gcdx
    print(gcdv)
else:
    m=int(n**(2/3))
    ns=int(n/m)
    rgcd=[]
    for mi in range(m):
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
        gcdm=gcdf(am)
        rgcd.append(gcdm)
    gcdv=0

    for mi in range(m):
        rgcd1=list(rgcd)
        del rgcd1[mi]
        gcdrg1=gcdf(rgcd1)
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]

        for i in range(len(am)):
            acpy=list(am)


            acpy[i]=gcdrg1
            gcdx=gcdf(acpy)
            if gcdx>gcdv:
                gcdv=gcdx
    print(gcdv)

Solution (Python):
def gcdf(a):
    a.sort()

    a0=a[0]
    a=[int(x%a0) for x in a if x%a0 != 0]

    if len(a)==0:
        return a0
    else:
        a.append(a0)
        a0=min(a)
        return gcdf(a) 










n=int(input())
a=[]
for i in map(int,input().split()):
    a.append(i)
if n==2:
    print(max(a))
elif n<2**10:
    gcdv=0
    for i in range(n):
        acpy=list(a)
        del acpy[i]
        gcdx=gcdf(acpy)
        if gcdx>gcdv:
            gcdv=gcdx
    print(gcdv)
else:
    m=int(n**(1/2))
    ns=int(n/m)
    rgcd=[]
    for mi in range(m):
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
        gcdm=gcdf(am)
        rgcd.append(gcdm)
    gcdv=0

    for mi in range(m):
        rgcd1=list(rgcd)
        del rgcd1[mi]
        gcdrg1=gcdf(rgcd1)
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]

        for i in range(len(am)):
            acpy=list(am)


            acpy[i]=gcdrg1
            gcdx=gcdf(acpy)
            if gcdx>gcdv:
                gcdv=gcdx
    print(gcdv)

Solution (Python):
from itertools import *
import fractions
 
N = int(input())
A = list(map(int, input().split()))
 
L = list(accumulate([0]+A, fractions.gcd))
R = list(accumulate([0]+A[::-1], fractions.gcd))
 
print(max(fractions.gcd(s, t) for s, t in zip(L, R[::-1][1:])))

Solution (Python):
"""
配列の値を書き換える＝＝削除すると同義
削除する値を一つ決め、それを区切りに右と左の配列に分け、GCDを求める
更に左右のGCDをマージしGCDを求め、最大値が答え
"""
import functools, fractions

N = int(input())
A = list(map(int, input().split()))
L = [0]*(N+1)
R = [0]*(N+1)

for i in range(N):
  L[i+1] = fractions.gcd(L[i], A[i])

for i in range(N-1, 0, -1):
  R[i] = fractions.gcd(R[i+1], A[i])
  
ans = 0
for i in range(N):
  l = L[i]
  r = R[i+1]
  ans = max(ans, fractions.gcd(l, r))
print(ans)

Solution (Python):
import fractions
import sys

def chmax(a, b):
  if (a > b):
    return a

  return b

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

if N == 2:
  if li[0] > li[1]:
    print(li[0])
  else:
    print(li[1])
  sys.exit()

left = []
right = []

for index, i in enumerate(li):
  if index == 0:
    left.append(i)
    continue

  left.append(fractions.gcd(left[index-1], i))

for index, i in enumerate(reversed(li)):
  if index == 0:
    right.append(i)
    continue

  right.append(fractions.gcd(right[index-1], i))

ans = 0

for n in range(N):
  if n == 0:
    ans = chmax(ans, right[-2])
    continue
  
  if n == N-1:
    ans = chmax(ans, left[-2])
    continue

  ans = chmax(ans, fractions.gcd(left[n-1], right[N-n-2]))

print(ans)

Solution (Python):
from fractions import gcd

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

left = [0 for _ in range(n + 1)]
right = [0 for _ in range(n + 1)]
for i in range(n):
    left[i + 1] = gcd(left[i], a[i])

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

ans = 0
for i in range(n):
    l = left[i]
    r = right[i+1]
    ans = max(ans, gcd(l, r))

print(ans)

Solution (Python):

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

def gcd(a,b):
    if (a==0) or (b==0):
        return max(a,b) 
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

lm = [0] *(n+1)
rm = [0] *(n+1)
for i in range(1,n):
    lm[i+1] = gcd(lm[i],s[i-1])
for i in range(n-1,0,-1):
    rm[i] = gcd(rm[i+1],s[i])

ans = float('-inf')
for i in range(1,n+1):
    ans = max(ans,gcd(lm[i],rm[i]))
print(ans)

Solution (Python):
from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
right,left=[a[n-1]],[a[0]]
for i in range(1,n):
  left.append(gcd(left[i-1],a[i]))
  right.append(gcd(right[i-1],a[n-i-1]))
ans=max(left[n-2],right[n-2])
for i in range(1,n-1):
  ans=max(ans,gcd(left[i-1],right[n-i-2]))
print(ans)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7


def main():
    
    N = Scanner.int()
    A = Scanner.map_int()
    L = [0] * N
    R = [0] * N
    for i in range(N-1):
        L[i+1] = Math.gcd(L[i], A[i])
    for i in reversed(range(N-1)):
        R[i] = Math.gcd(R[i+1], A[i+1])
    M = [0] * N
    for i in range(N):
        M[i] = Math.gcd(L[i], R[i])
    print(max(M))


if __name__ == "__main__":
    main()