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):
from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools
import copy
import collections
from operator import itemgetter

def j(q):
    if q==1: print("Yes")
    elif q == 0:print("No")
    exit(0)


"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in range(len(a)):
        print(a[i])
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


n = ip()                                     

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








if n==2:
    print(max(a))
else:
    ans = []
    s = [a[0]]
    for i in range(1,n):
        s.append(fractions.gcd(s[i-1],a[i]))
    r = [a[n-1]]
    for i in range(n-2,-1,-1):
        r.append(fractions.gcd(r[len(r)-1],a[i]))
    r = r[::-1]
 
 
    ans.append(r[1])
    for i in range(1,n-1):
        ans.append(fractions.gcd(s[i-1],r[i+1]))
    ans.append(s[n-2])
    print(max(ans))

Solution (Python):
def gcd(num1,num2):
    if num2==0:
        return num1
    return gcd(num2,num1%num2)
from collections import deque
n=int(input())
a=[int(i) for i in input().split()]
left_gcd=a[0]
right_gcd=a[-1]
left=deque([])
right=deque([])
for i in a:
    left_gcd=gcd(left_gcd,i)
    left.append(left_gcd)
for i in a[::-1]:
    right_gcd=gcd(right_gcd,i)
    right.append(right_gcd)
right=deque(reversed(right))
Max=max(right[1],left[-2])
for i in range(1,n-1):
    Max=max(Max,gcd(left[i-1],right[i+1]))
print(Max)

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

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

L,R = [A[0]],[A[-1]]
Lg = A[0]
Rg = A[-1]
for i in range(N-1):
    Lg = gcd(Lg,A[i+1])
    L.append(Lg)
for i in range(N-1,0,-1):
    Rg = gcd(Rg,A[i-1])
    R.append(Rg)
L.append(A[-1])
R.append(A[0])

res = 0
for i in range(N):
    if i == 0:
        res = max(res,R[-3])
    elif i == N-1:
        res = max(res,L[-3])
    else:
        res = max(res,gcd(L[i-1],R[-i-3]))
        
print(res)

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):
import fractions

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

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


gcd_l=[0]*n
gcd_l[0]=a[0]
for i in range(1,n):
  gcd_l[i]=fractions.gcd(gcd_l[i-1],a[i])


ans=gcd_r[1]
for i in range(1,n-1):
  ans=max(fractions.gcd(gcd_l[i-1],gcd_r[i+1]),ans)
print(max(ans,gcd_l[n-2]))

Solution (Python):


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

def main(N, A):
    L = [0]*(N+1)
    R = [0]*(N+1)
    M = [0]*(N+1)
    
    for i in range(N):
        L[i+1] = gcd(L[i], A[i])
        R[(-2-i)] = gcd(R[-1-i], A[-1-i])
    for i in range(N):
        M[i] = gcd(L[i], R[i+1])
        
    print(max(M))

if __name__ == '__main__':
    N = int(input())
    A = [int(a) for a in input().split()]
    
    main(N, A)

Solution (Python):
from itertools import*
from fractions import*
n,*a=map(int,open(0).read().split())
b=list(accumulate([0]+a,gcd))
c=list(accumulate([0]+a[::-1],gcd))
print(max(gcd(s,t)for s,t in zip(b,c[::-1][1:])))

Solution (Python):
def gcd(a,b):
    if a ==0:
        return b
    if b==0:
        return a
    return gcd(b,a%b)
N = int(input())
A = list(map(int,input().split()))
R = [0]*(N+1)
L = [0]*(N+1)
M = [0]*(N+1)
for i in range(N):
    L[i+1]= gcd(L[i],A[i])
    R[-(i+2)] = gcd(R[-(i+1)],A[-(i+1)])
for i in range(N):
    M[i] = gcd(L[i],R[i+1])
print(max(M))

Solution (Python):




















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

import sys
p = 50
N = int(input())
if p>N : p=N
a = list(map(int,input().split()))

ans = 0

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

print(ans)

Solution (Python):
N = int(input())
li = [ int(it) for it in input().split() ]
lil = [0]*N
lir = [0]*N

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)
  
lil[0]=li[0]
lir[N-1]=li[N-1]
for i in range(N-1):
  lil[i+1]=gcd(li[i+1],lil[i])
for i in range(N-1,0,-1):
  lir[i-1]=gcd(li[i-1],lir[i])
s = -1
for i in range(N):
  if (i==0):
    gc = lir[1]
  elif (i==N-1):
    gc = lil[N-2]
  else:
    gc = gcd(lil[i-1],lir[i+1])
  s = max(s, gc )
print (s)

Solution (Python):
def gcd(a,b):
    while a%b!=0:
        a,b = b,a%b
    return b
n = int(input())
a = list(map(int,input().split()))
right,left = [0]*n,[0]*n
left[0],right[n-1] = a[0],a[n-1]
for i in range(1,n):
    left[i] = gcd(left[i-1],a[i])
for i in range(n-2,-1,-1):
    right[i] = gcd(right[i+1],a[i])
ans = max(left[-2],right[1])
for i in range(1,n-1):
    ans = max(ans,gcd(right[i+1],left[i-1]))
print(ans)

Solution (Python):
import fractions

N = int(input())
A = [int(i) for i in input().split()]

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

R = [0] * (N+1)
for i in reversed(range(N)):
        R[i] = (fractions.gcd(R[i+1], A[i]))

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

print(max(ans))

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

Solution (Python):
import fractions


if __name__ == '__main__':
  N = int(input())
  A = list(map(int, input().split()))

  gcdl = [0]
  gcdr = [0]
  for i in range(N):
      gcdl.append(fractions.gcd(gcdl[i], A[i]))
      gcdr.append(fractions.gcd(gcdr[i], A[-(i+1)]))
  gcdr = gcdr[::-1]

  ans = []
  for i in range(N):
      ans.append(fractions.gcd(gcdl[i], gcdr[i+1]))
  print(max(ans))

Solution (Python):
def gcd(a,b):
    while a%b!=0:
        a,b=b,a%b
    return b
N=int(input())
A=list(map(int,input().split()))
if N==1:
    print(10**9)
    exit()
go=[0]*N
go[0]=A[0]
back=[0]*N
back[N-1]=A[N-1]
for i in range(1,N):
    go[i]=gcd(go[i-1],A[i])
for i in range(N-2,-1,-1):
    back[i]=gcd(back[i+1],A[i])
ans=max(go[-2],back[1])
for i in range(1,N-1):
    now=gcd(go[i-1],back[i+1])
    ans=max(now,ans)
print(ans)

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

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

r = [0 for _ in range(n+1)]
l = [0 for _ in range(n+1)]

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

m = [0 for _ in range(n)]

for i in range(n):
    m[i] = gcd(l[i],r[i+1])

print(max(m))

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


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

gcd_l = [0] * N

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

gcd_r = [0] * N

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

gcd_lr = [0] * N

for i in range(N):
    if i == 0:
        gcd_lr[i] = gcd_r[i + 1]
    elif 1 <= i <= N - 2:
        gcd_lr[i] = gcd(gcd_l[i - 1], gcd_r[i + 1])
    elif i == N - 1:
        gcd_lr[i] = gcd_l[i - 1]

print(max(gcd_lr))

Solution (Python):


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

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


left_gcd=[a_array[0]] 
a=a_array[0] 
for i in range(1, n-1):
    a=gcd(a,a_array[i])
    left_gcd.append(a)


right_gcd=[a_array[-1]]
b=a_array[-1] 
for i in range(n-2,0,-1):
    b=gcd(b,a_array[i])
    right_gcd.append(b)


ans_gcd=[right_gcd[n-2],left_gcd[n-2]]

for i in range(n-2):
    ans_gcd.append(gcd(left_gcd[i],right_gcd[n-i-3]))

print(max(ans_gcd))

Solution (Python):

def gcd(a, b):
    maxi = max(a,b)
    mini = min(a,b)
    if mini==0:
        return maxi
    else:
        return gcd(mini, maxi%mini)

n = int(input())
a = list(map(int, input().split()))
L = [0] 
R = [0] 
for i in range(n):
    L.append(gcd(a[i], L[i]))
    R.append(gcd(a[n-i-1], R[i]))
R.reverse()

ans = []
for i in range(len(L)-1):
    ans.append(gcd(L[i], R[i+1]))
print(max(ans))

Solution (Python):
def gcd(a, b):
    
    if a == b:
        return a
    
    small = large = 0
    if a > b:
        small = b
        large = a
    else:
        small = a
        large = b
    
    while True:
        
        d, m = divmod(large, small)
        if m == 0:
            return small
        else:
            large = small
            small = m
    
    
    

def get_next_int():
    return int(float(input()))
def get_next_ints(delim=" "):
    return tuple([int(float(x)) for x in input().split(delim)])

def main():
    n = get_next_int()
    numbers = get_next_ints()
    
    current = numbers[0]
    candidates = {numbers[1]}
    
    for number in numbers[1:]:
        
        next_candidates = {}
        for candidate in candidates:
            next_candidates[gcd(candidate, number)] = 1
        candidates = next_candidates
        
        candidates[current] = 1
        current = gcd(current, number)    
    
    print(max(candidates.keys()))
    
if __name__ == '__main__':
    main()

Solution (Python):
def gcd(a, b):
    if a > b:
        a,b = b,a
    if a == 0:
        return b
    else:
	    while b:
		    a, b = b, a % b
	    return a

n = int(input())
a = list(map(int,input().split()))
l = [0]
r = [0]
for i in range(n):
    l.append(gcd(l[i],a[i]))
for i in range(n):
    r.append(gcd(r[i],a[-i-1]))
r.reverse()
ans = 0
for i in range(n):
    if ans < gcd(l[i],r[i+1]):
        ans = gcd(l[i],r[i+1])
print(ans)

Solution (Python):

"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""


"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""

import numpy as np
import sys
from functools import reduce 
""""
import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
import copy
import bisect
"""


def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   

def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

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(reverse = True)
    return divisors
"""
N, X = map(int, input().split())

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

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())


dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')


ABT = zip(A, B, totAB)
result = 0

sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)


(x >> i) & 1


dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break

add = 1 
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)


li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    


org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)



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



def gcd_euclid(a, b):
    if a > b:
        a, b = b, a 
    if a==0:
        return b
    return gcd_euclid(b%a, a)

def main():
    A.sort()
    res = 0
    for i in range(1,N+1):
        L[i] = gcd_euclid(L[i-1], A[i-1])
    for i in range(N-1, 0, -1):
        R[i] = gcd_euclid(R[i+1], A[i])
    
    for i in range(N):
        gcd_now = gcd_euclid(L[i], R[i+1])
        res = max(res, gcd_now)
    print(res)
    
if __name__ == '__main__':
    main()

Solution (Python):





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






try:
    from fractions import gcd
except:
    from math import gcd











lg = [1]*(N)
rg = [1]*(N)












lg[0] = A[1]
rg[0] = A[N-2]
lg[1] = A[0]
rg[1] = A[N-1]

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



ans = [gcd(lg[i], rg[N-1-i]) for i in range(N)]

    
    
print(max(ans))

Solution (Python):





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






try:
    from fractions import gcd
except:
    from math import gcd











lg = [1]*(N)
rg = [1]*(N)
ans = 0











lg[0] = A[1]
rg[0] = A[N-2]
lg[1] = A[0]
rg[1] = A[N-1]

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



ans = [gcd(lg[i], rg[N-1-i]) for i in range(N)]

    
    
print(max(ans))

Solution (Python):





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






try:
    from fractions import gcd
except:
    from math import gcd











lg = [1]*(N)
rg = [1]*(N)
ans = 0











lg[0] = A[1]
rg[0] = A[N-2]
lg[1] = A[0]
rg[1] = A[N-1]

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


for i in range(N):
    
    tmp = gcd(lg[i], rg[N-i-1])
    
    if ans < tmp:
        ans = tmp
    




print(ans)




"""
[42 54 69 92 12 23]のとき
 1 [54 69 92 12 23]の最大公約数
 2 [42 69 92 12 23]
 3 [42 54 92 12 23]
 4 [42 54 69 12 23]

"""

Solution (Python):





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






try:
    from fractions import gcd
except:
    from math import gcd











lg = [1]*(N)
rg = [1]*(N)
ans = 0











lg[0] = A[1]
rg[0] = A[N-2]
lg[1] = A[0]
rg[1] = A[N-1]

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


for i in range(N):
    
    tmp = gcd(lg[i], rg[N-i-1])
    
    if ans < tmp:
        ans = tmp
    




print(ans)




"""
[42 54 69 92 12 23]のとき
 1 [54 69 92 12 23]の最大公約数
 2 [42 69 92 12 23]
 3 [42 54 92 12 23]
 4 [42 54 69 12 23]

"""

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

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

l, r = [], []

for i in range(n):
  l.append(gcd(l[i-1], a[i-1]) if i else 0)
  r.append(gcd(r[i-1], a[n-i]) if i else 0)
print(max([gcd(l[i], r[n-i-1]) for i in range(n)]))

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

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

L = [0] * n
R = [0] * n

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

ans = 0

for i in range(n):
    ans = max(ans, gcd(L[i], R[i]))

print(ans)

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

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)
    return divisors

candidate1 = []
candidate = {}
for i in range(N):
    if i > 1:
        delete_key = []
        for c in candidate.keys():
            if A[i] % c == 0:
                candidate[c]['atari'] += 1
            else:
                candidate[c]['hazure'] += 1        
    elif i == 0:
        candidate1 = make_divisors(A[i])
    elif i == 1:
        candidate2 = make_divisors(A[i])
        prev = -1
        for c in sorted(candidate1 + candidate2):
            if c != prev and prev != -1 and candidate[prev]['atari'] < 2:
                candidate[prev]['hazure'] += 1
            if c not in candidate:
                candidate[c] = {
                    'atari': 1,
                    'hazure': 0
                }
            else:
                candidate[c]['atari'] += 1
            prev = c
        if candidate[prev]['atari'] < 2:
            candidate[prev]['hazure'] += 1            
max = 0
for c in candidate:
    if candidate[c]['hazure'] < 2 and max < c:
        max = c
print(max)

Solution (Python):
import sys
from fractions import gcd

def input():
	return sys.stdin.readline()

N = int(input())
A = [int(_) for _ in input().split()]
p1 = [0] * N
p2 = [0] * N

p1[0] = A[0]
p2[-1] = A[-1]

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

m = max(p1[-2], p2[1])

if N > 2:
	for i in range(1, N-1):
		m = max(m, gcd(p1[i-1], p2[i+1]))

print(m)

Solution (Python):
import sys
from fractions import gcd

def input():
	return sys.stdin.readline()

N = int(input())
A = [int(_) for _ in input().split()]
p1 = [0] * N
p2 = [0] * N

p1[0] = A[0]
p2[-1] = A[-1]

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

m = max(p1[-2], p2[1])

if N > 2:
	for i in range(1, N-1):
		m = max(m, gcd(p1[i-1], p2[i+1]))

print(m)

Solution (Python):
n = int(input())
li = list(map(int,input().split()))
ans = 0
lgcd = [0]*n
rgcd = [0]*n
lgcd[0] = li[0]
rgcd[-1] = li[-1]

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

for i in range(n-1):
    lgcd[i+1] = gcd(lgcd[i],li[i+1])
    rgcd[-i-2] = gcd(rgcd[-i-1],li[-(i+2)])

gcd_list = [gcd(lgcd[i],rgcd[i+2]) for i in range(n-2)]

gcd_list.append(lgcd[-2])
gcd_list.append(rgcd[1])

print(max(gcd_list))

Solution (Python):

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

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

ll = [0]*n
ll[0] = al[0]
for i in range(1,n):
    ll[i] = gcd(al[i], ll[i-1])

rl = [0]*n
rl[n-1] = al[n-1]
for i in range(n-2,-1,-1):
    rl[i] = gcd(al[i],rl[i+1])

res = -1

for i in range(n):
    if i==0:
        res = max(res, rl[1])
    elif i==n-1:
        res = max(res, ll[n-2])
    else:
        res = max(res, gcd(ll[i-1],rl[i+1]))

print(res)

Solution (Python):
import sys

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

n=int(input())
al=input().split()
al_i = [int(s) for s in al]

if (n == 2):
   print(max(al_i[0],al_i[1]))
   sys.exit()

fg = [0] * n
bg = [0] * n

for x in range(n):
   if (x == 0):
       fg[0] = al_i[0]
       y = 1
   else:
      while y <= x:
         fg[y] = gcd(fg[y-1], al_i[y])
         y += 1

for x in range(n):
   if (x == 0):
      bg[0] = al_i[n-1]
      y = 1
   else:
      while y <= x:
         bg[y] = gcd(bg[y-1], al_i[n-1-y])
         y += 1

m = 0
gm = 0

for x in range(n):
   if (x == 0):
      g = bg[n-2]
   elif (x == n-1):
      g = fg[n-2]
   else:
      g = gcd(fg[x-1],bg[n-2-x])
   if (g > gm):
      gm = g

print(gm)

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

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

fg = [0] * n
bg = [0] * n

fg[0] = al[0]
bg[0] = al[n-1]

for x in range(1,n):
    fg[x] = gcd(fg[x-1], al[x])
    bg[x] = gcd(bg[x-1], al[n-1-x])

gm = max(bg[n-2], fg[n-2])

for x in range(1,n-1):
   g = gcd(fg[x-1],bg[n-2-x])
   if (g > gm):
      gm = g

print(gm)

Solution (Python):
N = int(input())
A = [int(_) for _ in input().split()]


class SegmentTree():
    def __init__(self, array, f, e, size):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        e : 
            identity element of the monoid
        size : int
            limit for array size
        """
        self.f = f
        self.e = e
        self.size = size
        self.n = n = len(array)
        self.dat = dat = [e] * n + array + [e] * (2 * size - 2 * n)
        for i in range(n - 1, 0, -1):  
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def modify(self, p, v):  
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            dat[p >> 1] = f(dat[p], dat[p ^ 1])
            p >>= 1

    def query(self, l, r):  
        f, e, n, dat = self.f, self.e, self.n, self.dat
        res = e
        l += n
        r += n
        while l < r:
            if l & 1:
                res = f(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = f(res, dat[r])
            l >>= 1
            r >>= 1
        return res


gcd = lambda x, y: gcd(y, x) if x < y else gcd(y, x % y) if y else x
e = 0
size = N
ST = SegmentTree(A, f=gcd, e=e, size=size)
ans = 1
for i, a in enumerate(A):
    ST.modify(i, 0)
    ans = max(ans, ST.query(0, N))
    ST.modify(i, a)
print(ans)

Solution (Python):

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


n = int(input())
a = list(map(int, input().split()))  
lg = []
lg.append(0)
rg = []
rg.append(0)
for i in range(n):
    lg.append(gcd(lg[-1], a[i]))
    rg.append(gcd(rg[-1], a[n-i-1]))


m = 0
for i in range(n):
    g = gcd(lg[i], rg[n-1-i])
    if g > m:
        m = g
print(m)

Solution (Python):

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


n = int(input())
a = list(map(int, input().split()))  
lg = []
lg.append(0)
rg = []
rg.append(0)
for i in range(n):
    lg.append(gcd(lg[-1], a[i]))
    rg.append(gcd(rg[-1], a[n-i-1]))


m = 0
for i in range(n):
    g = gcd(lg[i], rg[n-1-i])
    if g > m:
        m = g
print(m)

Solution (Python):
import sys

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

n=int(input())
al=input().split()
al_i = [int(s) for s in al]

if (n == 2):
   print(max(al_i[0],al_i[1]))
   sys.exit()

fg = [0] * n
bg = [0] * n

for x in range(n):
   if (x == 0):
       fg[0] = al_i[0]
       y = 1
   else:
      while y <= x:
         fg[y] = gcd(fg[y-1], al_i[y])
         y += 1

for x in range(n):
   if (x == 0):
      bg[0] = al_i[n-1]
      y = 1
   else:
      while y <= x:
         bg[y] = gcd(bg[y-1], al_i[n-1-y])
         y += 1

m = 0
gm = 0

for x in range(n):
   if (x == 0):
      g = bg[n-2]
   elif (x == n-1):
      g = fg[n-2]
   else:
      g = gcd(fg[x-1],bg[n-2-x])
   if (g > gm):
      gm = g

print(gm)

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

gcd_L = [0]
gcd_R = [0]
for i in range(N):
    gcd_L.append(fractions.gcd(gcd_L[i], A[i]))
    gcd_R.append(fractions.gcd(gcd_R[i], A[-(i+1)]))
gcd_R = gcd_R[::-1]

x = []
for i in range(N):
    x.append(fractions.gcd(gcd_L[i], gcd_R[i+1]))
print(max(x))

Solution (Python):
import fractions
import numpy as np


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

left_gcd_array = np.array([0] * n)
left_gcd_array[0] = a[0]

right_gcd_array = np.array([0] * n)
right_gcd_array[n - 1] = a[n - 1]

for i in range(1, n):
    left_gcd_array[i] = fractions.gcd(a[i], left_gcd_array[i - 1])
    right_gcd_array[n - 1 - i] = fractions.gcd(a[n - 1 - i], right_gcd_array[n - i])

print(max([left_gcd_array[n - 2]] +
          [fractions.gcd(left_gcd_array[i], right_gcd_array[i + 2]) for i in range(0, n - 2)] +
          [right_gcd_array[1]]))


if __name__ == '__main__':
    pass

Solution (Python):
import fractions

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

gcd_left_list = [0]*N
gcd = alist[0]
for i in range(1,N):
  gcd = fractions.gcd(gcd,alist[i-1])
  gcd_left_list[i] = gcd

gcd_right_list = [0]*N
gcd = alist[N-1]
for i in reversed(range(0,N-1)):
  gcd = fractions.gcd(gcd,alist[i+1])
  gcd_right_list[i] = gcd




    
max_gcd = max(gcd_right_list[0], gcd_left_list[N-1])
for i in range(1,N-1):
  gcd = fractions.gcd(gcd_left_list[i],gcd_right_list[i])
  if gcd > max_gcd:
    max_gcd = gcd

print(max_gcd)

Solution (Python):
import fractions
n=int(input())
lis=list(map(int,input().split()))
li=[lis[0]]
l=[lis[n-1]]
for i in range (0,n-1):
  li.append(fractions.gcd(li[i],lis[i+1]))
  l.append(fractions.gcd(l[i],lis[n-i-2]))
ans_li=[]
for i in range(0,n-2):
  ans_li.append(fractions.gcd(li[i],l[n-3-i]))
ans_li.insert(0,li[n-2])
ans_li.append(l[n-2])
ans_li.sort()           
ans_li.reverse()
print(ans_li[0])

Solution (Python):
from fractions import gcd
 
n,*a = map(int, open(0).read().split())
 
rs, ls = [0], [0]
for i in range(n-1):
  rs.append(gcd(rs[i], a[i]))
  ls.append(gcd(ls[i], a[-i-1]))
 
print(max(gcd(r, l) for r, l in zip(rs, ls[::-1])))

Solution (Python):
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
front = [0]
back = [0]
for i in range(len(A)):
    front.append(gcd(A[i], front[i]))
    back.append(gcd(A[len(A) - i - 1], back[i]))
ans = 0
for i in range(len(A)):
    ans = max(gcd(front[i], back[len(A) - i - 1]), ans)
print(ans)

Solution (Python):
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
front = [0]
back = [0]
for i in range(len(A)):
    front.append(gcd(A[i], front[i]))
    back.append(gcd(A[len(A) - i - 1], back[i]))
ans = 0
for i in range(len(A)):
    ans = max(gcd(front[i], back[len(A) - i - 1]), ans)
print(ans)

Solution (Python):
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
front = [0]
back = [0]
for i in range(len(A)):
    front.append(gcd(A[i], front[i]))
    back.append(gcd(A[len(A) - i - 1], back[i]))
ans = 0
for i in range(len(A)):
    ans = max(gcd(front[i], back[len(A) - i - 1]), ans)
print(ans)

Solution (Python):

"""解説
GCD, DP, 累積和

「一つを選んで好きな数字に変えられる」とあるが、今回のケースでは「その数字を消す」と同じ。

すべてのGCDを試す

4 6 7 8 10 12 14

という数列が与えられたとき、

・4を消して、ほかの数字のGCDを計算

6 7 8 10 12 14

・6を消して、ほかの数字のGCDを計算

4 7 8 10 12 14

・7を消して、……

というのを全列挙するが、N=10**5なので、O(N**2)では計算が間に合わない。

なのでこれをもう少し高速でやりたい。

GCDは計算順序を問わない性質を利用する。

たとえば、8を消した場合

4 6 7 8 10 12 14
| 左 |× |   右  |

・左のGCD
・右のGCD
を計算し、GCD(左のGCD, 右のGCD)をやってもよい。

・左のGCDを考える
GCD(4) = L[1]
GCD(4 6) = L[2] = GCD(L[1], 6)
GCD(4 6 7) = L[3] = GCD(L[2], 7)
GCD(4 6 7 8) = L[4] = GCD(L[3], 8)
GCD(4 6 7 8 10) = L[5] = GCD(L[4], 10)

みたいな感じで計算できる。

・右のGCDについても同様に計算してやる。

この前計算ができたら、あとは累積和のように、どの数字を削除したときがGCDが最大になるのかを計算する。

"""
import copy

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

    def gcd(x, y):
        """ 最大公約数を求める """
        
        if y > x:
            x, y = y, x
        if y == 0:
            return x
        return gcd(x%y, y)

    
    L = [0]*(N+1)
    L[1] = A[0]
    for i in range(2, N):
        L[i] = gcd(L[i-1], A[i-1])

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

    print(ans)

if __name__ == "__main__":
    solve()

Solution (Python):
from fractions import gcd


def main(input_1, input_2):
    left = [0] * (input_1+1)
    for i in range(input_1):
        left[i+1] = gcd(left[i], input_2[i])

    right = [0] * (input_1 + 1)
    i = input_1 - 1
    while i >= 0:
        right[i] = gcd(right[i+1], input_2[i])
        i -= 1

    while i >= 0:
        right[i] = gcd(right[i+1], input_2[i])

    res = 0
    for i in range(input_1):
        l = left[i]
        r = right[i+1]
        gcd_val = gcd(l, r)
        if gcd_val > res:
            res = gcd_val

    return res


if __name__ == "__main__":
    input_1 = int(input())
    input_2 = list(map(int, input().split()))
    print(main(input_1, input_2))

Solution (Python):
from fractions import gcd
 
n = int(input())
a = list(map(int, input().split()))
 
rs, ls = [0], [0]
for i in range(n-1):
  rs.append(gcd(rs[i], a[i]))
  ls.append(gcd(ls[i], a[-i-1]))
 
print(max(gcd(r, l) for r, l in zip(rs, ls[::-1])))

Solution (Python):
def gcd(a,b):
    if a < b:
        a,b = b,a
    if b == 0:
        return a
    return gcd(b,a%b)

n = int(input())
a = list(map(int, input().split()))
rs, ls = [0], [0]
for i in range(n-1):
    rs.append(gcd(rs[i], a[i]))
    ls.append(gcd(ls[i], a[-i-1]))
gcd_list = [gcd(r,l) for r, l in zip(rs, ls[::-1])]
print(max(gcd_list))

Solution (Python):
import numpy as np

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

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

l = [0]*n
r = [0]*n

for i in range(1,n):
    l[i]=gcd(l[i-1],s[i-1])

tmp = list(range(0,n-1))
tmp.reverse()
for i in tmp:
    r[i]=gcd(r[i+1],s[i+1])
    
m = list([])

for i in range(n):
    m.append(gcd(l[i],r[i]))

print(max(m))

Solution (Python):
from fractions import gcd

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

rs, ls = [0], [0]
for i in range(n-1):
  rs.append(gcd(rs[i], a[i]))
  ls.append(gcd(ls[i], a[-i-1]))

gcd_list = [gcd(r,l) for r, l in zip(rs, ls[::-1])]
print(max(gcd_list))

Solution (Python):
from fractions import gcd

N = int(input())
A = [int(i) for i in input().split()]

gcd_l = [0]
gcd_r = [0]
for i in range(N):
    gcd_l.append(gcd(gcd_l[i], A[i]))
    gcd_r.append(gcd(gcd_r[i], A[-(i+1)]))
gcd_r = gcd_r[::-1]

ans = []
for i in range(N):
    ans.append(gcd(gcd_l[i], gcd_r[i+1]))

print(max(ans))

Solution (Python):
from fractions import gcd

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

rs, ls = [0], [0]
for i in range(n-1):
  rs.append(gcd(rs[i], a[i]))
  ls.append(gcd(ls[i], a[-i-1]))

print(max(gcd(r, l) for r, l in zip(rs, ls[::-1])))