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 fractions import gcd
from functools import reduce

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

my_gcd = reduce(gcd, A)
A = [a // my_gcd for a in A]

flag = False
my_gcd_2 = 0
my_gcd_3 = 0

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

for i in range(N):
    a = A[i]
    if my_gcd_2 == 0:
        my_gcd_2 = a
    else:
        if gcd(my_gcd_2, a) == 1:
            if flag is False:
                if i == 1:
                    my_gcd_3 = a
                else:
                    divisors = make_divisors(a)
                    for d in divisors[::-1]:
                        if len([j for j in A[:i] if j % d]) == 1:
                            my_gcd_3 = d
                            break
                flag = True
                continue
            else:
                my_gcd_2 = -1
        if my_gcd_3 and gcd(my_gcd_3, a) == 1:
            my_gcd_3 = -1
        if my_gcd_2:
            my_gcd_2 = gcd(my_gcd_2, a)
        if my_gcd_3:
            my_gcd_3 = gcd(my_gcd_3, a)

else:
    ans_1 = my_gcd * my_gcd_2
    ans_2 = my_gcd * my_gcd_3
    print(max(ans_1, ans_2, my_gcd))

Solution (Python):
import fractions
def GCD(a, b):
    if a * b == 0:
        return a + b
    return fractions.gcd(a, b)

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

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

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

M = [0] * n
for i in range(n):
    M[i] = GCD(L[i], R[i])
print(max(M))

Solution (Python):

import sys
from fractions import gcd

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N = ni()
A = nl()
assert len(A) == N


def solve():
    al = [None] * N
    ar = [None] * N
    al[0] = A[0]
    ar[-1] = A[-1]
    for i in range(1, N):
        al[i] = gcd(al[i - 1], A[i])
        ar[N - 1 - i] = gcd(ar[N - i], A[N - 1 - i])
    gmax = max(al[-2], ar[1])
    gmi = 0 if gmax == ar[1] else N - 1
    for i in range(1, N - 1):
        g = gcd(al[i - 1], ar[i + 1])
        if gmax < g:
            gmax = g
            gmi = i
    return gmax


if __name__ == "__main__":
    print(solve())

Solution (Python):

from fractions import gcd

def main():
    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])
        R[N-1-i] = gcd(R[N-i], A[N-1-i])
    ans = 0
    for i in range(N):
        ans = max(ans, gcd(L[i], R[i+1]))
    print(ans)

if __name__ == "__main__":
    main()

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

m = 0

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

Solution (Python):



import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

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=I()
lis=sorted(LI())
u=make_divisors(lis[0])

for j in range(len(u)):
    br=u[j]
    count=0
    
    for i in range(n):
        if lis[i]%br!=0:
            count+=1
    if count<=1:
        ans1=br
        break


v=make_divisors(lis[1])

for j in range(len(v)):
    bre=v[j]
    counti=0
    
    for i in range(n):
        if lis[i]%bre!=0:
            counti+=1
    if counti<=1:
        ans2=bre
        break

print(max(ans1,ans2))

Solution (Python):



import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

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=I()
lis=sorted(LI())
u=make_divisors(lis[0])

for j in range(len(u)):
    br=u[j]
    count=0
    
    for i in range(n):
        if lis[i]%br!=0:
            count+=1
    if count<=1:
        ans1=br
        break


v=make_divisors(lis[1])

for j in range(len(v)):
    bre=v[j]
    counti=0
    
    for i in range(n):
        if lis[i]%bre!=0:
            counti+=1
    if counti<=1:
        ans2=bre
        break

print(max(ans1,ans2))

Solution (Python):
from fractions import gcd
n = int(input())
an = list(map(int, input().split()))

left = [an[0]]
right = [an[-1]]
for i in range(1, n-1):
    left.append(gcd(left[-1], an[i]))
    right.append(gcd(right[-1], an[-(i+1)]))

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

print(ans)

Solution (Python):
import sys
from fractions import gcd


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


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    N = int(input())
    A = list(map(int, input().split()))
    left = [A[0]]
    right = [A[-1]]
    for i in range(1, N - 1):
        left.append(gcd(left[-1], A[i]))
        right.append(gcd(right[-1], A[N - i - 1]))
    answer = max(left[-1], right[-1])
    for i in range(N - 2):
        g = gcd(left[i], right[N - 3 - i])
        if answer < g:
            answer = g
    print(answer)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from fractions import gcd


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    gcd_from_left = [None] * N
    gcd_from_left[0] = A[0]
    
    gcd_from_right = [None] * N
    gcd_from_right[-1] = A[-1]

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

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

    gcd_from_right.sort()

    
    ans = max(gcd_from_left[-2], gcd_from_right[1])
    for i in range(1, N - 1):
        tmp = gcd(gcd_from_right[i + 1], gcd_from_left[i - 1])
        if tmp > ans:
            ans = tmp

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):


import sys



















from fractions import gcd                    


def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n = ii()
    L = lmi()
    gcd_before_dp = [L[0]] * n   
    gcd_after_dp = [L[-1]] * n    
    
    g = L[0]
    for i in range(1, n):
        g = gcd(g, L[i])
        gcd_before_dp[i] = g
    g = L[-1]
    for i in range(n-2, -1, -1):
        g = gcd(g, L[i])
        gcd_after_dp[i] = g

    ans = 0
    for i in range(n):
        
        if i == 0:
            ans = max(ans, gcd_after_dp[i+1])
        elif i == n - 1:
            ans = max(ans, gcd_before_dp[i-1])
        else:
            ans = max(ans, gcd(gcd_before_dp[i-1], gcd_after_dp[i+1]))
    print(ans)



if __name__ == "__main__":
    main()

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

from fractions import gcd
import math

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

mx = 0
for i in range(n):
    cd = gcd(llis[i],rlis[n-i-1])
    mx = max(mx,cd)

print(mx)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq
from fractions import gcd

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = LI()
    dp = [[0,0] for _ in range(N-1)]
    dp[0] = [A[0],A[1]]
    for i in range(1,N-1):
        dp[i][0] = gcd(dp[i-1][0],A[i])
        dp[i][1] = max(gcd(dp[i-1][0],A[i+1]),gcd(dp[i-1][1],A[i+1]))
    print(max(dp[-1]))

if __name__ == '__main__':
    main()

Solution (Python):
from fractions  import gcd


n=int(input())
a=list(map(int,input().split()))
inf = 0
num_min =2**(n-1).bit_length()
dat=[inf]*(2*num_min-1)


for i in range(n):
    dat[i+num_min-1]=a[i]
for i in range(num_min-2,-1,-1):
    dat[i]=gcd(dat[2*i+1],dat[2*i+2])




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

def update(i,x):
    i+=n-1
    dat[i]=x
    while i>0:
        i=(i-1)//2
        dat[i]=segfunc(dat[2*i+1],dat[2*i+2])
def query(a,b): 
    if b<=a:
        return inf
    res=inf
    a += num_min-1
    b += num_min-2
    while b-a>1:
        if a&1==0:
            res = segfunc(res,dat[a])
        if b&1==1:
            res = segfunc(res,dat[b])
            b-=1
        a=a//2
        b=(b-1)//2
    if a==b:
        res = segfunc(res,dat[a])
    else:
        res=segfunc(segfunc(res,dat[a]),dat[b])
    return res

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

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

DP_first = [0] * N
DP_last = [0] * N

DP_first[0] = A[0]
DP_last[0] = A[-1]

for i in range(1, N):
    DP_first[i] = fractions.gcd(DP_first[i-1], A[i])
    DP_last[i] = fractions.gcd(DP_last[i-1], A[-1-i])

ans = max(DP_first[N-2], DP_last[N-2])
for i in range(1, N-1):
    ans = max(ans, fractions.gcd(DP_first[i-1], DP_last[N-2-i]))
print(ans)

Solution (Python):
from math import*
n,*a=map(int,open(0).read().split())
b=[0]
for i in a:b+=gcd(b[-1],i),
w=m=0
for i in range(n):m=max(m,gcd(w,b[-i-2]));w=gcd(w,a[~i])
print(m)

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

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

def main():
    n = int(input())
    a = sorted(int(i) for i in input().split())
    a0 = a[0]
    if a0 == 1:
        print(reduce(gcd, a[1:]))
        return
    c = []
    for i in range(2, int(a0**0.5) + 1):
        while a0 % i == 0:
            c.append(i)
            a0 //= i
    if a0 != 1:
        c.append(a0)
    d = [0] * len(c)
    for ai in a[1:]:
        for i, ci in enumerate(c):
            if ai % ci == 0:
                ai //= ci
            else:
                d[i] += 1
    e = []
    g = 1
    for k, v in zip(c, d):
        if v == 0:
            g *= k
        elif v == 1:
            e.append(k)
    f = [1] * (n - 1)
    for i, ai in enumerate(a[1:]):
        for ei in e:
            if ai % ei == 0:
                ai //= ei
            else:
                f[i] *= ei
    print(max(g * max(f), reduce(gcd, a[1:])))

if __name__ == '__main__':
    main()

Solution (Python):
import random
from operator import itemgetter
import sys
sys.setrecursionlimit(1000000)
ans=0

def gcd(x,y):
    x,y=max(abs(x),abs(y)),min(abs(x),abs(y))
    if x%y==0:
        return y
    while x%y!=0:
        x,y=y,x%y
    return y

def gcd_all(l):
    rt=l.pop()
    for i in l:
        rt=gcd(i,rt)
    return rt
    
n=int(input())

g=[]

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

ans=0
d=a[-1]
m=a[-1]
mi=-1
k1=[]
flg=0
for i in range(n):
    gg=gcd(a[i],d)
    if gg<m:
        m=gg
        mi=i
ans=max(ans,gcd_all(a[:mi]+(a[mi+1:] if mi+1<n else [])))

d=a[0]
m=a[0]
mi=0
k1=[]
flg=0
for i in range(n):
    gg=gcd(a[i],d)
    if gg<m:
        m=gg
        mi=i
ans=max(ans,gcd_all(a[:mi]+(a[mi+1:] if mi+1<n else [])))

print(ans)

Solution (Python):
from fractions import gcd

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] = gcd(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] = gcd(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return I
    p += num-1
    q += num-2
    res = I
    while q-p>1:
        if p&1 == 0:
            res = gcd(res,seg[p])
        if q&1 == 1:
            res = gcd(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = gcd(res,seg[p])
    else:
        res = gcd(gcd(res,seg[p]),seg[q])
    return res


I = 0
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
n = int(readline())
a = [int(i) for i in readline().split()]
num = 2**(n-1).bit_length()
seg=[I]*2*num
init(a)
ans = 1
for i in range(n):
  ans = max(ans,gcd(query(0,i),query(i+1,n)))
  
print(ans)

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

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

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



ans = 1
for i in range(N):
    if i == 0:
        ans = max(ans, GCD_r[0])
    elif i == N-1:
        ans = max(ans, GCD_l[N-2])
    else:
        ans = max(ans, fractions.gcd(GCD_l[i-1], GCD_r[i]))
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


n = I()
A = LI()


tmpl = 0
tmpr = 0
L = []
R = []
for i in range(n):
    tmpl = gcd(tmpl, A[i])
    tmpr = gcd(tmpr, A[-1-i])
    L.append(tmpl)
    R.append(tmpr)

R = list(reversed(R))



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

print(ans)

Solution (Python):
import sys
from fractions import gcd
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    """
    「中間の値に関してうんぬん　→　その値の左右の区間から計算」
    は定石と思っていい気がする。

    言われてみればA[i]を除いたGCDはgcd(A[:i])とgcd(A[i+1:])から求まるわなあ
    素因数分解してとか考える以前の話だった。。。
    """

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

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


if __name__ == "__main__":
    main()

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

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

gcd_from_left = [0]*N 
gcd_from_right = [0]*N

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

ans = 0

for a,b in zip(gcd_from_left, gcd_from_right):
  x = gcd(a,b)
  if ans < x:
    ans = x
    
print(ans)

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

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

gcd_from_left = [0]*N 
gcd_from_right = [0]*N

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

ans = 0

for a,b in zip(gcd_from_left, gcd_from_right):
  x = gcd(a,b)
  if ans < x:
    ans = x
    
print(ans)

Solution (Python):
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
gcd_l = a[0]
gcd_r = a[-1]
gcd_l_li = []
gcd_r_li = []
for i in range(n):
    gcd_l = gcd(gcd_l, a[i])
    gcd_l_li.append(gcd_l)
for i in range(n)[::-1]:
    gcd_r = gcd(gcd_r, a[i])
    gcd_r_li.append(gcd_r)



ans = max(gcd_r_li[n-2], gcd_l_li[n-2])  
for target in range(1, n-1):
    ans = max(ans, gcd(gcd_l_li[target-1], gcd_r_li[n-2-target]))
print(ans)

Solution (Python):
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
gcd_l = a[0]
gcd_r = a[-1]
gcd_l_li = []
gcd_r_li = []
for i in range(n):
    gcd_l = gcd(gcd_l, a[i])
    gcd_l_li.append(gcd_l)
for i in range(n)[::-1]:
    gcd_r = gcd(gcd_r, a[i])
    gcd_r_li.append(gcd_r)



ans = max(gcd_r_li[n-2], gcd_l_li[n-2])  
for target in range(1, n-1):
    ans = max(ans, gcd(gcd_l_li[target-1], gcd_r_li[n-2-target]))
print(ans)

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

Solution (Python):
from fractions import gcd

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

B = [0] * (N - 1)
C = [0] * (N - 1)

for n in range(N - 1):
    if n == 0:
        B[0] = A[0]
        C[N - 2] = A[N - 1]
    else:
        B[n] = gcd(B[n - 1], A[n])
        C[N - n - 2] = gcd(A[N - n - 1], C[N - n - 1])

ans = 0
for n in range(N):
    if n == 0:
        ans = C[0]
    elif n == N - 1:
        ans = max(ans, B[N - 2])
    else:
        ans = max(ans, gcd(B[n - 1], C[n]))
print(ans)

Solution (Python):
from fractions import gcd
from itertools import accumulate
N = int(input())
A = tuple(map(int, input().split()))
to_right = [0] + list(accumulate(A, gcd))[:-1]
to_left = list(reversed(list(accumulate(reversed(A), gcd))))[1:] + [0]
print(max(gcd(r, l) for r, l in zip(to_right, to_left)))

Solution (Python):
from subprocess import *
call(('pypy3','-c',"""
import sys
def input(): return sys.stdin.readline().rstrip()

from fractions import gcd
class seg():
    def __init__(self,init_val):
        self.n=len(init_val)
        self.ide_ele=0 
        self.num=2**(self.n-1).bit_length() 
        self.seg=[self.ide_ele]*2*self.num
        for i in range(self.n):
            self.seg[i+self.num-1]=init_val[i]
        for i in range(self.num-2,-1,-1):
            self.seg[i]=self.seg_func(self.seg[2*i+1],self.seg[2*i+2])
    def seg_func(self,a,b):
        
        
        return gcd(a,b) 
        
        
    def update(self,k,x):
        k+=self.num-1
        self.seg[k]=x
        while k:
            k=(k-1)//2
            self.seg[k]=self.seg_func(self.seg[k*2+1],self.seg[k*2+2])
    def query(self,p,q): 
        if q<=p:return self.ide_ele
        p+=self.num-1
        q+=self.num-2
        self.res=self.ide_ele
        while q-p>1:
            if p&1==0:
                self.res=self.seg_func(self.res,self.seg[p])
            if q&1==1:
                self.res=self.seg_func(self.res,self.seg[q])
                q-=1
            p=p//2
            q=(q-1)//2
        if p==q:self.res=self.seg_func(self.res,self.seg[p])
        else:self.res=self.seg_func(self.seg_func(self.res,self.seg[p]),self.seg[q])
        return self.res

def main():
    n=int(input())
    A=[int(_) for _ in input().split()]
    ans=0
    seg_a=seg(A)
    for i in range(n):
        ans=max(ans,gcd(seg_a.query(0,i),seg_a.query(i+1,n)))
    print(ans)
if __name__=='__main__':
    main()
"""))

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

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

gcd_L = [A[0]]
gcd_R = [A[N - 1]]

for i in range(1, N):
    new_gcd_l = gcd(gcd_L[-1], A[i])
    gcd_L.append(new_gcd_l)
    new_gcd_r = gcd(gcd_R[-1], A[N - i - 1])
    gcd_R.append(new_gcd_r)
    
best = gcd_L[N - 1]
for i in range(N):
    if i > 0:
        if i == N - 1:
            a = gcd_L[i - 1]
            if best < a:
                best = a
        else:
            l = gcd_L[i - 1]
            r = gcd_R[N - 2 - i]
            gcd_without_i = gcd(l, r)
            if gcd_without_i > best:
                best = gcd_without_i
    else:
        a = gcd_R[N - 2]
        if a > best:
            best = a

print(best)

Solution (Python):
import fractions

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

for i in range(0, N, 1):
    if i==0:
        L[i] = fractions.gcd(0, A[i])
        continue
    L[i] = fractions.gcd(L[i-1], A[i])

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

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

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
import math
from fractions import gcd
import operator
from functools import reduce
from itertools import accumulate

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


def prime_factorization_preprocess(n):
    """
    エラトステネスの篩を用いて、sqrt(n)以下の素数を列挙する
    """
    m = math.floor(math.sqrt(n)) + 1
    primes = []
    is_prime = [True for i in range(m)]
    for i in range(2, m):
        if is_prime[i]:
            primes.append(i)
            for j in range(i+i, m, i):
                is_prime[j] = False
    return primes


def prime_factorization(x, primes):
    """
    試し割り法により、数値の素因数分解を求める
    """
    factors = defaultdict(int)
    for p in primes:
        if x % p == 0:
            n = 0
            while x % p == 0:
                x //= p
                n += 1
            factors[p] = n
    return factors


def solve(N, A, AMAX = 10**9, INF=10**9):
    sl = list(accumulate(A, gcd))
    sr = list(reversed(list(accumulate(reversed(A), gcd))))
    max_gcd = sl[-1]
    for i in range(N):
        
        v = 0
        if i > 0:
            v = gcd(v, sl[i-1])
        if i < N-1:
            v = gcd(v, sr[i+1])
        max_gcd = max(max_gcd, v)
    return max_gcd


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))

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

Solution (Python):
class ABSsegtree: 
    def __init__(self,N,ie,func):
        self.func=func
        self.getLEN=1 
        while self.getLEN<N:
            self.getLEN*=2
        self.getsize=self.getLEN*2 
        self.getLIN=self.getsize-self.getLEN 
        self.ST=[ie]*self.getsize

    def update(self,i,x): 
        i+=self.getLIN
        self.ST[i]=x
        while i>1:
            i//=2
            self.ST[i]=self.func(self.ST[2*i],self.ST[2*i+1])
    
    def get_interval(self,a,b): 
        a+=self.getLIN
        b+=self.getLIN
        ret=self.func(self.ST[a],self.ST[b-1])
        while a+1<b: 
            if a%2==1:
                ret=self.func(self.ST[a],ret)
                a+=1
            a//=2
            if b%2==1:
                ret=self.func(self.ST[b-1],ret)
            b//=2
        if a==b:
            pass
        else:
            ret=self.func(ret,self.ST[a])
        return ret
      
import fractions

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

ins=ABSsegtree(N,0,fractions.gcd)
for i,a in enumerate(A):
  ins.update(i,a)
ans=0
for i,a in enumerate(A):
  ins.update(i,0)
  ans=max(ans,ins.get_interval(0,N))
  ins.update(i,a)
print(ans)

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

def gcd(a,b):
  aa=max(a,b)
  bb=min(a,b)
  return gcd(bb,aa%bb) if bb else aa
  

left=[]
right=[]
for i in range(0,n):
  j=n-i-1
  if left:
    hahaha=gcd(left[i-1],a[i])
    left.append(hahaha)
  else:
    left.append(a[i])
  if right:
    hahaha=gcd(right[i-1],a[j])
    right.append(hahaha)
  else:
    right.append(a[j])
    
keep=0
for i in range(0,n):
  if i==0:
    temp=right[-2]
  elif i==n-1:
    temp=left[-2]
  else:
    temp=gcd(left[i-1],right[n-i-2])
  if temp>keep:
    keep=temp

print(keep)

Solution (Python):


import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))








from fractions import gcd
def resolve():
    N,=pin()
    A=tupin()
    lgcd,rgcd=[0]*(N),[0]*(N)
    ltemp,tempr=A[0],A[-1]
    for g in range(N):
        ltemp=gcd(ltemp,A[g])
        lgcd[g]=ltemp
        
        tempr=gcd(tempr,A[N-g-1])
        
        rgcd[N-g-1]=tempr
    
    ans=1
    for i in range((N)):
        a,t=0,0
        if i==0:
            t=rgcd[1]
        elif i==N-1:
            t=lgcd[N-2]
        else:
            t=gcd(lgcd[i-1],rgcd[i+1])
        ans=max(ans,t)
    print(ans)

resolve()

Solution (Python):
from fractions import gcd

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

left = [0]*n
right = [0]*n

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

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

Solution (Python):
from fractions import gcd  


def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    L, R = [0 for _ in range(N)], [0 for _ in range(N)]
    L[0], R[N - 1] = A[0], A[N - 1]
    for i in range(1, N):
        L[i] = gcd(L[i - 1], A[i])
    for j in range(N - 2, -1, -1):
        R[j] = gcd(R[j + 1], A[j])
    max_gcd = 0
    for i in range(N):
        if i == 0:
            g = R[1]
        elif i == N - 1:
            g = L[N - 2]
        else:
            g = gcd(L[i - 1], R[i + 1])
        max_gcd = max([g, max_gcd])
    print(max_gcd)


if __name__ == '__main__':
    main()

Solution (Python):
from fractions import gcd

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

L=[0]*n
R=[0]*n
L[0]=A[0]
R[n-1]=A[n-1]
res=0

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

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

from fractions import gcd
class seg():
    def __init__(self,init_val):
        self.n=len(init_val)
        self.ide_ele=0 
        self.num=2**(self.n-1).bit_length() 
        self.seg=[self.ide_ele]*2*self.num
        for i in range(self.n):
            self.seg[i+self.num-1]=init_val[i]
        for i in range(self.num-2,-1,-1):
            self.seg[i]=self.seg_func(self.seg[2*i+1],self.seg[2*i+2])
    def seg_func(self,a,b):
        
        
        return gcd(a,b) 
        
        
    def update(self,k,x):
        k+=self.num-1
        self.seg[k]=x
        while k:
            k=(k-1)//2
            self.seg[k]=self.seg_func(self.seg[k*2+1],self.seg[k*2+2])
    def query(self,p,q): 
        if q<=p:return self.ide_ele
        p+=self.num-1
        q+=self.num-2
        self.res=self.ide_ele
        while q-p>1:
            if p&1==0:
                self.res=self.seg_func(self.res,self.seg[p])
            if q&1==1:
                self.res=self.seg_func(self.res,self.seg[q])
                q-=1
            p=p//2
            q=(q-1)//2
        if p==q:self.res=self.seg_func(self.res,self.seg[p])
        else:self.res=self.seg_func(self.seg_func(self.res,self.seg[p]),self.seg[q])
        return self.res

def main():
    n=int(input())
    A=[int(_) for _ in input().split()]
    ans=0
    seg_a=seg(A)
    for i in range(n):
        ans=max(ans,gcd(seg_a.query(0,i),seg_a.query(i+1,n)))
    print(ans)
if __name__=='__main__':
    main()

Solution (Python):
from fractions import gcd
n = int(input())
aaa = list(map(int, input().split()))
p = aaa[0]
f = [p]
for a in aaa[1:-1]:
    p = gcd(p, a)
    f.append(p)
aaa.reverse()
p = aaa[0]
b = [p]
for a in aaa[1:-1]:
    p = gcd(p, a)
    b.append(p)
b.reverse()

f = [b[0]] + f
b = b + [f[-1]]

print(max(gcd(p, q) for p, q in zip(f, b)))