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()))

def GCD(x,y):
    while y != 0:
        x,y = y,x%y
    return x

l,r = [0],[0]
for i in range(N-1):
    l.append(GCD(l[-1],A[i]))
    r.append(GCD(r[-1],A[N-i-1]))

ans = 0
for i in range(N):
    ans = max(ans,GCD(l[i],r[N-i-1]))
print(ans)

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


def gcd(x,y):
    m1 = min(x,y)
    m2 = max(x,y)
    if m1 == 0:
        return m2
    else:
        return gcd(m2%m1,m1)

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

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

Solution (Python):
N = int(input())
As = list(map(int, input().split()))
def calcgcd(a, b):
  if a > b:
    a, b = b, a
  while a > 0:
    a, b = b%a, a
  return b
gcdsl = [0]*(N+1)
for i in range(N):
  a = gcdsl[i]
  b = As[i]
  gcdsl[i+1] = calcgcd(a, b)

gcdsr = [0]*(N+1)
for i in reversed(range(N)):
  a = gcdsr[i+1]
  b = As[i]
  gcdsr[i] = calcgcd(a, b)

gcds = [0]*N
for i in range(N):
  a = gcdsl[i]
  b = gcdsr[i+1]
  gcds[i] = calcgcd(a, b)

print(max(gcds))

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):
n=int(input())
a=list(map(int,input().split()))
b=[0 for i in range (n+2)]
c=[0 for i in range (n+2)]
i=1
def g(a,b):
	if(b==0):
		return a
	else:
		return g(b,a%b)
while(i<=n):
	b[i]=g(b[i-1],a[i-1])
	c[n+1-i]=g(c[n+2-i],a[n+1-i-1])
	i+=1

i=1
d=[]
while(i<=n):
	d.append(g(b[i-1],c[i+1]))
	i+=1
d.sort()
print(d[n-1])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a, b, t = LI()
    print(b * (t // a))
    return


def B():
    n = II()
    v = LI()
    c = LI()
    ans = 0
    for i in range(n):
        if v[i] > c[i]:
            ans += v[i] - c[i]
    print(ans)
    return


def C():
    def gcd(a, b):
        if b > a: a, b = b, a
        while b:
            a, b = b, a % b
        return a
    n = II()
    a = LI()
    dp1 = [None] * (n - 1)
    dp1[0] = a[0]
    dp2 = [None] * (n - 1)
    dp2[-1] = a[-1]
    for i in range(1, n - 1):
        dp1[i] = gcd(dp1[i - 1], a[i])
        dp2[-i - 1] = gcd(dp2[-i], a[-i - 1])
    ans = 0
    dp1.insert(0, dp2[0])
    dp2.append(dp1[-1])
    for i in range(n):
        ans = max(ans, gcd(dp1[i], dp2[i]))
    print(ans)
    return


def D():
    return


if __name__ == '__main__':
    C()

Solution (Python):

import sys
from fractions import gcd

def solve(N: int, A: "List[int]"):
    L = [A[0]]
    R = [A[-1]]
    for i in range(1, N):
        L.append(gcd(L[-1], A[i]))
        R.append(gcd(R[-1], A[N-1-i]))
    mx = 0
    for i in range(N):
        if i == 0:
            m = R[N-2]
        elif i == N-1:
            m = L[N-2]
        else:
            m = gcd(L[i-1], R[N-i-2])
        if mx < m:
            mx = m
    print(mx)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [ int(next(tokens)) for _ in range(N) ]  
    solve(N, A)

if __name__ == '__main__':
    main()

Solution (Python):
import operator
class SegmentTree:
    def __init__(self, size, default, op = operator.add):
        self.size = 2**size.bit_length()
        self.dat = [default]*(self.size*2)
        self.op = op

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

    def add(self, i, x):
        i += self.size
        self.dat[i] = self.op(self.dat[i], x)
        while i > 0:
            i >>= 1
            self.dat[i] = self.op(self.dat[i], x)

    def get(self, a, b = None):
        if b is None:
            b = a + 1
        l, r = a + self.size, b + self.size
        res = None
        while l < r:
            if l & 1:
                if res is None:
                    res = self.dat[l]
                else:
                    res = self.op(res, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                if res is None:
                    res = self.dat[r]
                else:
                    res = self.op(res, self.dat[r])
            l >>= 1
            r >>= 1

        return res

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

n = int(input())
a = list(map(int, input().split()))
seg = SegmentTree(n,0,gcd)
for i in range(n):
    seg.update(i,a[i])
ans = 1
for i in range(n):
    seg.update(i,0)
    ans = max(ans, seg.get(0,n))
    seg.update(i,a[i])
print(ans)

Solution (Python):
import operator
class SegmentTree:
    def __init__(self, size, default, op = operator.add):
        self.size = 1
        while self.size < size:
            self.size *= 2
        self.dat = [default for i in range(self.size*2-1)]
        self.op = op

    def update(self, i, x):
        i += self.size - 1
        self.dat[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.dat[i] = self.op(self.dat[i*2+1], self.dat[i*2+2])

    def add(self, i, x):
        i += self.size - 1
        self.dat[i] = self.op(self.dat[i], x)
        while i > 0:
            i = (i - 1) // 2
            self.dat[i] = self.op(self.dat[i], x)

    def get(self, a, b, k = None, l = None, r = None):
        if k is None:
            k = 0
            l = 0
            r = self.size

        if r <= a or b <= l:
            return None

        if a <= l and r <= b:
            return self.dat[k]

        res_l = self.get(a, b, k*2+1, l, (l+r)//2)
        res_r = self.get(a, b, k*2+2, (l+r)//2, r)
        if res_l is None:
            return res_r
        if res_r is None:
            return res_l
        return self.op(res_l, res_r)


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

n = int(input())
a = list(map(int, input().split()))
seg = SegmentTree(n,0,gcd)
for i in range(n):
    seg.update(i,a[i])
ans = 1
for i in range(n):
    seg.update(i,0)
    ans = max(ans, seg.get(0,n))
    seg.update(i,a[i])
print(ans)

Solution (Python):
import operator
class SegmentTree:
    def __init__(self, size, default, op = operator.add):
        self.size = 1
        while self.size < size:
            self.size *= 2
        self.dat = [default]*(self.size*2-1)
        self.op = op

    def update(self, i, x):
        i += self.size - 1
        self.dat[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.dat[i] = self.op(self.dat[i*2+1], self.dat[i*2+2])

    def add(self, i, x):
        i += self.size - 1
        self.dat[i] = self.op(self.dat[i], x)
        while i > 0:
            i = (i - 1) // 2
            self.dat[i] = self.op(self.dat[i], x)

    def get(self, a, b, k = None, l = None, r = None):
        if k is None:
            k = 0
            l = 0
            r = self.size

        if r <= a or b <= l:
            return None

        if a <= l and r <= b:
            return self.dat[k]

        res_l = self.get(a, b, k*2+1, l, (l+r)//2)
        res_r = self.get(a, b, k*2+2, (l+r)//2, r)
        if res_l is None:
            return res_r
        if res_r is None:
            return res_l
        return self.op(res_l, res_r)
def gcd(a,b):
    if a == 0:
        return b
    if b == 0:
        return a
    return gcd(b%a, a)

n = int(input())
a = list(map(int, input().split()))
seg = SegmentTree(n,0,gcd)
for i in range(n):
    seg.update(i,a[i])
ans = 1
for i in range(n):
    seg.update(i,0)
    ans = max(ans, seg.get(0,n))
    seg.update(i,a[i])
print(ans)

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)

res = [0] * N
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])

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

print(max(res))

Solution (Python):
import fractions

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

for i in range(1, N+1):
  L[i] = fractions.gcd(L[i-1], A[i-1]) 
  R[N-i+1] = fractions.gcd(R[N-i+2], A[N-i+2])
ans = 0
for i in range(1, N+1):
  rest_gcd = fractions.gcd(L[i], R[i])
  ans = max(ans, rest_gcd)
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 reversed(range(N)):	
	r[i] = gcd(r[i+1],A[i])

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

Solution (Python):
import fractions

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


l = [0, A[1]] + [0] * (N - 1)
r = [0] * N + [A[N]]

for i in range(2, N + 1):
	l[i] = fractions.gcd(l[i - 1], A[i])
for i in reversed(range(1, N)):
	r[i] = fractions.gcd(r[i + 1], A[i])

gcds = [r[2]]
for i in range(2, N):
	gcds.append(fractions.gcd(l[i - 1], r[i + 1]))
gcds.append(l[N - 1])

print(max(gcds))

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

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

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

R = []
g = 0
for i in range(N-1):
    g = gcd(g, A[N-1-i])
    R.append(g)
R.reverse()
R.append(0)

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

print(ans)

Solution (Python):
from collections import defaultdict
import bisect


def divisor(n):  
    i = 1
    div_set = set()
    while i * i <= n:
        if n % i == 0:
            div_set.add(i)
            div_set.add(n//i)
        i += 1
    return div_set


def divisor2(n):  
    div_set = set()

    for i in kouho:
        if i > n:
            return div_set
        if n % i == 0:
            div_set.add(i)
    return div_set


N = int(input())
A_list = list(map(int, input().split()))
A_list.sort()
max_index = bisect.bisect_left(A_list, A_list[-1])

times = max_index

divcount = defaultdict(int)
for n in A_list[:2]:
    
    for i in divisor(n):
        divcount[i] += 1

kouho = list(divcount.keys())
kouho.sort()


for n in A_list[2:max_index+1]:
    
    for i in divisor2(n):
        divcount[i] += 1


max_divisor = 0
for key, value in divcount.items():
    if value >= max_index and key > max_divisor:
        max_divisor = key

print(max_divisor)

Solution (Python):
"""


 = sys.stdin.readline().rstrip()
 = list(sys.stdin.readline().rstrip())


 = int(sys.stdin.readline())
 = map(int, sys.stdin.readline().split())
 = list(map(int, sys.stdin.readline().split()))
 = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  


a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654


char_list = list("abcd") 
"""

import math
import sys
import itertools
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

if __name__ == "__main__":
    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[-i-2] = gcd(right[-i-1],a[-i-1])
        
        

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

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

L = [0]*N
R = [0]*N

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

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

print(gcd)

Solution (Python):
import fractions

def mygcd(a, b):
    if a == 0:
        return b
    elif b == 0:
        return a
    else:
        return fractions.gcd(a, b)
N = int(input())
A = list(map(int, input().split()))

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

M = []
for i in range(N):
    M.append(mygcd(L[i], R[i]))
print(max(M))

Solution (Python):
def Gcd(x,y):
    if( y>x ): 
        r = x
        x = y
        y = r
    if( y==0 ):
        return x
    return Gcd(y,x%y)

import sys
from collections import deque
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
MAX = 10**5+5

def resolve():
    n = int(input())
    a = [0]
    a.extend(list(map(int,input().split())))
    leftmax = [0]*(n+2)
    rightmax = [0]*(n+2)
    leftmax[1]=a[1]
    rightmax[n]=a[-1]
    for i in range(2,n):
        r=n-i+1
        leftmax[i]=Gcd(leftmax[i-1],a[i])
        rightmax[r]=Gcd(rightmax[r+1],a[r])
    ans = 0
    for i in range(1,n+1):
        s = Gcd(leftmax[i-1],rightmax[i+1])
        ans = max(ans,s)
    print(ans)

if __name__ == "__main__":
    resolve()

Solution (Python):
import fractions
n=int(input())
a=list(map(int, input().split())) 
b=[0]
c=[0]
ans=[]
for i in range(n):
    b.append(fractions.gcd(b[i],a[i]))
    c.append(fractions.gcd(c[i],a[-i-1]))
del b[n]
del c[n]
 
for i in range(n):
    d=b[i]
    e=c[n-1-i]
    ans.append(fractions.gcd(d,e))
print(max(ans))

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):
from itertools import accumulate

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

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

Ls = [As[-1]] + list(accumulate(As, gcd))
Rs = list(accumulate(As[::-1], gcd))[::-1] + [As[0]]

ans = 0
for i in range(N):
    g = gcd(Ls[i], Rs[i+1])
    ans = max(ans, g)
print(ans)

Solution (Python):
from fractions import gcd

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

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

maxi = max(l[-2], r[1])
for i in range(1, n-1):
  maxi = max(maxi, gcd(l[i-1], r[i+1]))
print(maxi)

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


a = int(input())
b = list(map(int, input().split()))
c = [0] * (a + 1)
d = [0] * (a + 1)
for i in range(1, a + 1):
    c[i] = g_c_d(b[i-1], c[i-1])
    d[-i-1] = g_c_d(b[-i], d[-i])
e = 0
for i in range(len(c)-1):
    e = max(e, g_c_d(c[i], d[i+1]))
print(e)

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right

import re




def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 



n = i_inpl()


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


def gcdlist(numbers):
    a = numbers[0]
    for i in range(len(numbers)):
        a = gcd(a, numbers[i])
    return a

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

print(max(gcd(l[i-1], r[i+1]) for i in range(1, n+1)))

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

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

L = [0] * N
R = [0] * N

ans = 0

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

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

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


print(ans)

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

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

L = [0 for i in range(N)]
R = [0 for i in range(N)]

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

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

Z=[gcd(L[i],R[i]) for i in range(N)]

print(max(Z))

Solution (Python):
import fractions

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

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

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

Solution (Python):


import math
import fractions

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

L = [0] *(N+2)
R = [0] *(N+2)
ans = 0


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

for j in range(N -1,0,-1):
    R[j - 1] = fractions.gcd(R[j], A[j])
for j in range(0,N):
    if ans < fractions.gcd(L[j],R[j]):
        ans = fractions.gcd(L[j],R[j])

print(ans)

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

def gcd(m, n) :
    if m < n :
        m, n = n, m
    while m % n :
        m, n = n, m % n
    return n

gcdL = [0] * N
gcdR = [0] * N
gcdL[0] = A[0]
gcdR[N-1] = A[N-1]

for i in range(1, N) :
    gcdL[i] = gcd(gcdL[i-1], A[i])
    gcdR[N-1-i] = gcd(gcdR[N-i], A[N-1-i])
  
ret = max(gcdL[N-2], gcdR[1])
for i in range(1, N - 1) :
    ret = max(ret, gcd(gcdL[i-1], gcdR[i+1]))

print(ret)

Solution (Python):
import fractions as f

N = int(input())

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

rightGCD = [0]*N
leftGCD = [0]*N

for i in range(N-1):
    leftGCD[i+1] = f.gcd(leftGCD[i],A[i])
    rightGCD[-i-2] = f.gcd(rightGCD[-i-1],A[-i-1])




ans = 0

for i in range(N):
    ans = max(ans,f.gcd(rightGCD[i],leftGCD[i]))

print(ans)

Solution (Python):
import sys

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

def get_cum_gcd(N, As):
    cum_gcd = [0] * N
    for i, n in enumerate(As):
        if i == 0:
            cum_gcd[i] = n
        else:
            cum_gcd[i] = gcd(cum_gcd[i-1], n)
    return cum_gcd

def get_cav_gcds(N, cum_l, cum_r):
    cav_gcds = [0] * N
    for i in range(N):
        if i == 0:
            cav_gcds[i] = cum_r[i+1]
        elif i == N-1:
            cav_gcds[i] = cum_l[i-1]
        else:
            cav_gcds[i] = gcd(cum_l[i-1], cum_r[i+1])
    return cav_gcds

def main():
    input = sys.stdin.readline
    N = int(input())
    As = list(map(int, input().split()))
    cum_l = get_cum_gcd(N, As)
    cum_r = list(reversed(get_cum_gcd(N, reversed(As))))
    cav_gcds = get_cav_gcds(N, cum_l, cum_r)
    print(max(cav_gcds))

if __name__ == '__main__':
    main()

Solution (Python):
import fractions

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

ans = 0

lf = [0]*N
rf = [0]*N

for i in range(1,N):
    lf[i] = fractions.gcd(lf[i-1],a[i-1])
    rf[i] = fractions.gcd(rf[i-1],a[-i])

ans = 0
for i in range(N):
    ans = max(ans,fractions.gcd(lf[i],rf[-i-1]))

print(ans)

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

L = [0] * N
for i in range(N) :
        if i == 0 :
                L[0] = 0
        elif i == 1 :
                L[1] = a[0]
        else :
                L[i] = fractions.gcd(L[i-1], a[i-1])

a.reverse()
R = [0] * N
for i in range(N) :
        if i == 0 :
                R[0] = 0
        elif i == 1 :
                R[1] = a[0]
        else :
                R[i] = fractions.gcd(R[i-1], a[i-1])
R.reverse()
a.reverse()

gcd = [0] * N
for i in range(N) :
        if i == 0 :
                gcd[0] = R[0]
        elif i == N-1 :
                gcd[N-1] = L[N-1]
        else :
                gcd[i] = fractions.gcd(L[i],R[i])

print(max(gcd))

Solution (Python):
from fractions import gcd
N=int(input())
a_list = list(map(int, input().split()))
gcd_l = [0] * (N+1) 
gcd_r = [0] * (N+1) 
for i, a in enumerate(a_list):
    gcd_l[i+1] = gcd(gcd_l[i], a)
for i in range(N, 0, -1):
    a = a_list[i-1]
    gcd_r[i-1] = gcd(gcd_r[i], a)
ans = 1

for i in range(N):
    tmp = gcd(gcd_l[i], gcd_r[i+1])
    if (ans < tmp):
        ans = tmp
print(ans)

Solution (Python):
import fractions

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

l = [0]*n
r = [0]*n
l[0] = an[0]
r[n-1] = an[n-1]

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

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

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


a = int(input())
b = list(map(int, input().split()))
b.append(0)
b.insert(0, 0)
c = [0]*(len(b))
d = [0]*(len(b))
for i in range(1, len(b)):
    c[i] = (g_c_d(b[i], c[i-1]))
    d[-i-1] = (g_c_d(b[-i-1], d[-i]))
e = 0
for i in range(0, len(c)-2):
    e = max(g_c_d(c[i], d[i+2]), e)
print(e)

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


a = int(input())
b = list(map(int, input().split()))
b.append(0)
b.insert(0, 0)
c = [0]*(len(b))
d = [0]*(len(b))
for i in range(1, len(b)):
    c[i] = (g_c_d(b[i], c[i-1]))
    d[-i-1] = (g_c_d(b[-i-1], d[-i]))
e = 0
for i in range(0, len(c)-2):
    e = max(g_c_d(c[i], d[i+2]), e)
print(e)

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


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

gl = []
g = 0
for aa in a:
    g = gcd(g, aa)
    gl.append(g)
gl = tuple(gl)

gr = []
g = 0
for aa in reversed(a):
    g = gcd(g, aa)
    gr.append(g)
gr = tuple(reversed(gr))

ans = 0
for rm in range(n):
    if rm - 1 < 0:
        ans = max(ans, gr[rm + 1])
    elif rm + 1 >= len(gr):
        ans = max(ans, gl[rm - 1])
    else:
        ans = max(ans, gcd(gl[rm - 1], gr[rm + 1]))
print(ans)

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


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

gl = []
g = 0
for aa in a:
    g = gcd(g, aa)
    gl.append(g)

gr = []
g = 0
for aa in reversed(a):
    g = gcd(g, aa)
    gr.append(g)
gr = list(reversed(gr))

ans = 0
for rm in range(n):
    if rm - 1 < 0:
        ans = max(ans, gr[rm + 1])
    elif rm + 1 >= len(gr):
        ans = max(ans, gl[rm - 1])
    else:
        ans = max(ans, gcd(gl[rm - 1], gr[rm + 1]))
print(ans)

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

st = set()
for tar in a[:2]:
    i = 1
    while i * i <= tar:
        if tar % i == 0:
            st.add(i)
            st.add(tar // i)
        i += 1

for d in sorted(st, reverse=True):
    cnt = 0
    for aa in a:
        if aa % d != 0:
            cnt += 1
        if cnt > 1:
            break
    else:
        print(d)
        exit()

Solution (Python):
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
n=0
i=0
while(n<N):
    i+=1
    n=2**i
INF=0
dat=[INF]*(2*n-1)
def update(i,x):
    i+=n-1
    dat[i]=x
    while(i>0):
        i=(i-1)//2
        dat[i]=gcd(dat[i*2+1],dat[i*2+2])
def find(a,b,k,l,r):
    if r<=a or b<=l:
        return INF
    if a<=l and r<=b:
        return dat[k]
    else:
        vl=find(a,b,k*2+1,l,(l+r)//2)
        vr=find(a,b,k*2+2,(l+r)//2,r)
        return gcd(vl,vr)
for i in range(N):
    update(i,A[i])
ans=0
for i in range(N):
    f=find(0,i,0,0,n)
    g=find(i+1,N,0,0,n)
    ans=max(gcd(f,g),ans)
print(ans)

Solution (Python):
import sys
import math
from collections import deque

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


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


def gcd_m(*args):
    if len(args) == 0:
        return 0
    if len(args) == 1:
        return args[0]
    if len(args) >= 2:
        ret = gcd(args[0], args[1])

    for value in args[2:]:
        ret = gcd(ret, value)
    return ret


def solve(inputs):
    [N] = string_to_int(inputs[0])
    
    A = string_to_int(inputs[1])

    if N == 2:
        return max(A)

    left_gcd_memo = deque([0])
    right_gcd_memo = deque([0])

    for v in A:
        left_gcd_memo.append(gcd(left_gcd_memo[-1], v))
    left_gcd_memo.append(0)
    for v in reversed(A):
        right_gcd_memo.appendleft(gcd(right_gcd_memo[0], v))
    right_gcd_memo.appendleft(0)

    max_gcd = 0
    for i in range(0, len(A)):
        left = left_gcd_memo[i]
        right = right_gcd_memo[i+2]
        g = gcd(left_gcd_memo[i], right_gcd_memo[i+2])
        max_gcd = g if g > max_gcd else max_gcd

    return max_gcd


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    ret = solve(inputs(2))
    print(ret)

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

    l = [0 for i in range(n)]
    r = [0 for i 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-1-i] = gcd(r[n-i],a[n-1-i])
    l = [0] + l
    r = r + [0]
    ans = 0
    for i in range(n):
        ans = max(ans,gcd(l[i],r[i+1]))

    print(ans)





main()

Solution (Python):
import fractions

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

L = [0]
R = [0]
ans_list = []

for i in range(n-1):
    L.append(fractions.gcd(L[i], A[i]))
    R.append(fractions.gcd(R[i], A[n-1-i]))

for j in range(n):
    ans_list.append(fractions.gcd(L[j], R[-j-1]))

print(max(ans_list))

Solution (Python):
import fractions

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

ans = 0

ls = [0]*n
rs = [0]*n

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

ans = 0
for i in range(n):        
    ans = max(ans,fractions.gcd(ls[i],rs[-i-1]))

print(ans)

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


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

L.append(A[0])
R.append(A[-1])
for i in range(1, N-1):
    L.append(gcd(L[i-1], A[i]))
    R.append(gcd(R[i-1], A[N-1-i]))
ans = max(R[-1], L[-1])
for i in range(N-2):
    val = gcd(L[i], R[N-i-3])
    if val > ans:
        ans = val
print(str(ans))

Solution (Python):
from fractions import gcd


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


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


r = [None for _ in range(N)]
r[N - 1] = A[N - 1]
for i in reversed(range(N - 1)):
    r[i] = gcd(r[i + 1], A[i])

ans = 0
for i in range(N):
    if i == 0:
        ans = max(ans, r[1])
    elif i == N - 1:
        ans = max(ans, l[N - 2])
    else:
        ans = max(ans, gcd(l[i - 1], r[i + 1]))
print(ans)

Solution (Python):
def larger(x, y):
	if x > y:
		return x
	return y

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

N = int(input())
A = list(map(int, input().split()))
gcdL = [A[0]]
for i in range(1, N):
	gcdL.append(euc(gcdL[-1], A[i]))
gcdR = [A[-1]]
for i in range(1, N):
	gcdR.append(euc(gcdR[-1], A[-1-i]))
gcdR.reverse()
max = gcdR[1]
for i in range(1, N-1):
	max = larger(max, euc(gcdL[i-1], gcdR[i+1]))
max = larger(max, gcdL[-2])
print(max)

Solution (Python):
import sys

sys.setrecursionlimit(1000000)

import fractions
from functools import reduce

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

def mygcd(a,b):
    if a==0:
        return b
    elif b==0:
        return a
    else:
        return fractions.gcd(a,b)

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

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

ans=1
for i in range(N):
    c=mygcd(L[i],R[i])
    ans=max(ans,c)

print(ans)

Solution (Python):
n = int(input())
ls = list(map(int, input().split()))
p = 50
ans = 0
if p>n:p=n

def gcd(a,b):
    if a < b:
        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
    
for i in range(p):
    s = cul(i,ls[:p])
    if s > ans:
        ans = s
print(ans)

Solution (Python):
from fractions import gcd

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


dp_l = [0] * (N + 1)
dp_r = [0] * (N + 1)

dp_l[0] = 0
dp_r[0] = 0

for i in range(1, N):
    dp_l[i] = gcd(dp_l[i - 1], AAA[i - 1])
    dp_r[i] = gcd(dp_r[i - 1], AAA[-i])

max_gcd = 0
for i in range(N + 1):
    gcd_cand = gcd(dp_l[i], dp_r[N - i - 1])
    max_gcd = max(gcd_cand, max_gcd)

print(max_gcd)