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 = [int(_) for _ in input().split()]


class SegmentTree():
    def __init__(self, array, m, e, size):
        self.m = m  
        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] = m(dat[i << 1], dat[i << 1 | 1])

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

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


gcd = lambda x, y: gcd(y, x) if x < y else x if y == 0 else gcd(y, x % y)
e = 0
size = 10**6
ST = SegmentTree(A, m=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):
import copy
N = int(input())
A = list(map(int, input().split()))

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

F = copy.copy(A)
B = copy.copy(A)

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

mx = max(F[N-2], B[1])
for i in range(1, N - 1):
  mx = max(mx, gcd(F[i-1], B[i+1]))
print(mx)

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


class SegmentTree():
    def __init__(self, array, m, e, size):
        self.m = m  
        self.e = e  
        self.size = size  
        n = self.n = len(array)
        dat = self.dat = [e] * n + array + [e] * (2 * size - 2 * n)
        for i in range(n - 1, 0, -1):  
            dat[i] = m(dat[i << 1], dat[i << 1 | 1])

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

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


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


e = 0
size = 10**6
ST = SegmentTree(A, m=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):
N = int(input())
A  = [int(i) for i in 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):
from sys import exit
def gcd(a,b):
    if (a<b):
        a,b = b,a
    while(b>0):
        a,b = b ,a%b
    return a
N = int(input())
A = [int(n) for n in input().split()]
straight = [0]*N
straight[0] = gcd(A[0],A[0])
for i in range(1,len(A)):
    straight[i] = gcd(straight[i-1], A[i])

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

back = back[::-1]


ans = straight[-2]
for i in range(N-2):
    ans = max(ans, gcd(straight[i], back[i+2]))
    
    
ans = max(ans, back[1])
print(ans)

Solution (Python):
from fractions import gcd
def get_result(L, N):
    Gl = [0]*N
    Gr = [0]*N
    Gl[0] = L[0]
    Gr[N-1] = L[N-1]
    for i in range(1, N):
        Gl[i] = gcd(Gl[i-1], L[i])
    for j in range(N-2, -1, -1):
        Gr[j] = gcd(Gr[j+1], L[j])
    
    full_gcd = Gr[0]
    result = full_gcd
    for i in range(N):
        if i == 0:
            x = Gr[1]
        elif i == N-1:
            x = Gl[N-2]
        else:
            x = gcd(Gl[i-1], Gr[i+1])
        if x > full_gcd:
            result = max(result, x)
    return result



N = int(input())
L = [int(s) for s in input().split(" ")]
result = get_result(L, N)
print(result )

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


def gcd(a, b):
    """
    自然数a, b の最大公約数を求める
    """
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


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

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

print(ans)

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


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


class SegmentTree():
    def m(self, v1, v2):  
        return gcd(v1, v2)

    def __init__(self, array):
        m = self.m
        e = self.e = 0  
        size = self.size = 10**5  
        n = self.n = len(array)
        dat = self.dat = [e] * n + array + [e] * (2 * size - 2 * n)
        for i in range(n - 1, 0, -1):  
            dat[i] = m(dat[i << 1], dat[i << 1 | 1])

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

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


ST = SegmentTree(A)
ans = 0
for i, a in enumerate(A):
    ST.modify(i, ST.e)
    ans = max(ans, ST.query(0, N))
    ST.modify(i, a)
print(ans)

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    L = [A[0]]
    R = [A[-1]]
    for i in range(1, N - 1):
        L.append(gcd(L[-1], A[i]))
    for j in range(N - 2, 0, -1):
        R.append(gcd(R[-1], A[j]))
    ans = R[-1]
    for k in range(1, N - 1):
        ans = max(ans, gcd(L[k - 1], R[N - 2 - k]))
    print(max(ans, L[-1]))
    
main()

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    L = [A[0]]
    R = [A[-1]]
    for i in range(1, N - 1):
        L.append(gcd(L[-1], A[i]))
    for j in range(N - 2, 0, -1):
        R.append(gcd(R[-1], A[j]))
    ans = R[-1]
    for k in range(1, N - 1):
        ans = max(ans, gcd(L[k - 1], R[N - 2 - k]))
    print(max(ans, L[-1]))
    
main()

Solution (Python):
from fractions import*
N,*A=map(int,open(0).read().split())
B=[0]
a=range(N)
for x in a:B+=[gcd(B[-1],A[x])]
w=M=0
for x in a[::-1]:M=max(M,gcd(w,B[x]));w=gcd(w,A[x])
print(M)

Solution (Python):
from fractions import*
N,*A=map(int,open(0).read().split())
w,B=0,[0]
a=range(N)
for x in a[:]:B+=[gcd(B[-1],A[x])]
w=M=0
for x in a[::-1]:M,w=max(M,gcd(w,B[x])),gcd(w,A[x])
print(M)

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

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

w = 0
B = [w]
for x in range(N-1, 0, -1):
    B += [gcd(B[-1], A[x])]

w = 0
M = 0
for x in range(N):
    M = max(M, gcd(w, B.pop()))
    w = gcd(w, A[x])

print(M)

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

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

gcd_forward = [numbers[0]]
for i in range(1, N - 1):
  gcd_all = gcd(gcd_forward[-1], numbers[i])
  gcd_forward.append(gcd_all)

gcd_backward = [numbers[-1]]
for i in range(N - 2, 0, -1):
  gcd_all = gcd(gcd_backward[-1], numbers[i])
  gcd_backward.append(gcd_all)

gcd_max = 1
for i in range(N):
  gcd_temp = 1
  if (i == 0):
    gcd_temp = gcd_backward[-1]
  elif (i == N - 1):
    gcd_temp = gcd_forward[-1]
  else:
    gcd_temp = gcd(gcd_forward[i - 1], gcd_backward[N - 2 - i])
  gcd_max = max(gcd_max, gcd_temp)
  
print(gcd_max)

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

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

def F(init, add):
    w = [0]
    for i in range(init, init + add * N, add):
        w += [gcd(w[-1], A[i])]
    return w[:-1]

print(max(map(lambda x,y:gcd(x,y), F(0, 1), F(N-1, -1)[::-1])))

Solution (Python):

import sys
import math
from collections import Counter
import collections
INF = float("inf")


def factorial(n):
    
    prime_count = collections.Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


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


def GCDs(*a):
    
    if len(a) == 0:
        return -1  

    if len(a) == 1:
        return a[0]

    res = a[0]
    for i in range(1, len(a)):
        res = GCD(res, a[i])
    return res


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


def solve(N: int, A: "List[int]"):

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

    buf = []
    for i in range(N):
        buf.append(GCD(asc[i], desc[N-i-1]))
    print(max(buf))

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


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

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

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

for i in range(N):
    left[i+1] = gcd(A[i], left[i])
for i in reversed(range(N)):
    right[i] = gcd(A[i], right[i+1])
    
res = 0
for i in range(N):
    l = left[i]
    r = right[i+1]
    res = max(gcd(l, r), res)

print(res)

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

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

param = [[0, 0, 0]]
addr = 0
while True:
    if len(param) <= 0:
        break
    addr, Li, Lv = param.pop()
    if addr == 0:
        if Li == N-1:
            Rv = 0
            M, isCall = Lv, False
            continue            
        param += [[1, Li, Lv], [0, Li+1, gcd(Lv, A[Li])]]
        isCall = True
        continue 
    elif addr == 1:
        Rv = gcd(A[Li+1], Rv)
        M, isCall = max(M, gcd(Lv, Rv)), False
        continue

print(M)

Solution (Python):

def main():
    import math

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

    
    

    
    

    
    

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

    
    N_ADJUST = 2**int(math.ceil(math.log(N)/math.log(2)))
    
    ST_SIZE = N_ADJUST*2-1
    
    INT_IDENTITY = 0
    li = [INT_IDENTITY]*ST_SIZE
    
    
    def init_segtree(li, k, l, r, binop, li_init):
        if r-l==1:
            li[k] = INT_IDENTITY if l >= len(li_init) else li_init[l]
        elif r-l>1:
            k_l, k_r = k*2+1, k*2+2
            init_segtree(li, k_l, l, (l+r)//2, binop, li_init)
            init_segtree(li, k_r, (l+r)//2, r, binop, li_init)
            li[k] = binop(li[k_l],li[k_r])

    init_segtree(li,0,0,N_ADJUST,gcd,a)

    
    
    def update_segtree(li,k,binop):
        if k > 0:
            k_2 = (k-1)//2
            k_l = k_2*2+1
            k_r = k_l+1
            li[k_2] = binop(li[k_l],li[k_r])
            update_segtree(li,k_2,binop)

    val = []
    for i in range(N_ADJUST-1,N_ADJUST+N-1):
        tmp = li[i]
        li[i] = 0
        update_segtree(li,i,gcd)
        
        val.append(li[0])
        li[i] = tmp
        update_segtree(li,i,gcd)

    print(max(val))

main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
 
 
def gcd(x,y):
    while y:
        x,y = y, x % y
    return x
    
gcd_left = [0]
gcd_rigth = [0]
gcd_list = []

for i in range(n):
    s = gcd(gcd_left[i], a[i])
    gcd_left.append(s)
    
for i in range(n):
    t = gcd(gcd_rigth[i], a[-i-1])
    gcd_rigth.append(t)

for i in range(n):
    v = gcd(gcd_left[i], gcd_rigth[n-1-i])
    gcd_list.append(v)

print(max(gcd_list))

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

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

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

right = [0] * (n+1)

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

ans = -1

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

print(ans)

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

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

ans=[]
L={}
L[0]=0
R={}
R[N+1]=0
R[N+2]=0

def gcd2(x,a):
    if x==0:
        return a
    else:
        return gcd(x,a)

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

for i in range(N):
    ans.append(gcd2(L[i],R[i+2]))
print(max(ans))

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
l = [0]*N
r = [0]*N
gcds = [0]*N
def gcd(a,b):
    if (a < b):
        a,b = b,a
    if (b == 0):
        return a
    return gcd(b, a%b)

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

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

Solution (Python):

from fractions import gcd


N = int(input())
A = [0]+list(map(int,input().split()))+[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):
from fractions import gcd

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

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

print(max(result))

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

Solution (Python):

import fractions
import numpy as np
from itertools import accumulate, chain, islice, starmap
N = int(input())
numbers = list(map(int, input().split()))




def calculate_maximum_subgcd_with_np_ufunc(numbers):
    gcd = np.frompyfunc(fractions.gcd, 2, 1)
    cumgcds = gcd.accumulate(numbers, dtype=np.object).astype(np.int)
    sub_cumgcds = np.roll(cumgcds, 1)
    sub_cumgcds[0] = 0
    reverse_cumgcds = gcd.accumulate(
        numbers[::-1], dtype=np.object).astype(np.int)
    sub_reverse_cumgcds = np.roll(reverse_cumgcds, 1)
    sub_reverse_cumgcds[0] = 0
    return np.max(gcd(sub_cumgcds, sub_reverse_cumgcds[::-1]))


def calculate_maximum_subgcd_with_func(numbers):
    operation = fractions.gcd
    cumgcds = accumulate(numbers, operation)
    sub_cumgcds = islice(chain([0], cumgcds), len(numbers))
    reverse_cumgcds = accumulate(numbers[::-1], operation)
    sub_reverse_cumgcds = islice(chain([0], reverse_cumgcds), len(numbers))
    sub_gcds = starmap(operation, zip(sub_cumgcds, list(sub_reverse_cumgcds)[::-1]))
    return max(sub_gcds)


calculate_maximum_subgcd = calculate_maximum_subgcd_with_np_ufunc


print(calculate_maximum_subgcd(numbers))

Solution (Python):

import fractions
import numpy as np
from itertools import accumulate, chain, islice, starmap
N = int(input())
numbers = list(map(int, input().split()))




def calculate_maximum_subgcd_with_np_ufunc(numbers):
    gcd = np.frompyfunc(fractions.gcd, 2, 1)
    cumgcds = gcd.accumulate(numbers, dtype=np.object).astype(np.int)
    sub_cumgcds = np.roll(cumgcds, 1)
    sub_cumgcds[0] = 0
    reverse_cumgcds = gcd.accumulate(
        numbers[::-1], dtype=np.object).astype(np.int)
    sub_reverse_cumgcds = np.roll(reverse_cumgcds, 1)
    sub_reverse_cumgcds[0] = 0
    return np.max(gcd(sub_cumgcds, sub_reverse_cumgcds[::-1]))


def calculate_maximum_subgcd_with_func(numbers):
    operation = fractions.gcd
    cumgcds = accumulate(numbers, operation)
    sub_cumgcds = islice(chain([0], cumgcds), len(numbers))
    reverse_cumgcds = accumulate(numbers[::-1], operation)
    sub_reverse_cumgcds = islice(chain([0], reverse_cumgcds), len(numbers))
    sub_gcds = starmap(operation, zip(sub_cumgcds, list(sub_reverse_cumgcds)[::-1]))
    return max(sub_gcds)



calculate_maximum_subgcd = calculate_maximum_subgcd_with_func

print(calculate_maximum_subgcd(numbers))

Solution (Python):
def gcd_(a,b):
    if a<b:    a,b=b,a
    if b==0:    return a
    return gcd_(b,a%b)
  
def gcd(l):
    ans=l[0]
    for i in l:
        ans=gcd_(ans,i)
    return ans


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

gcd_list=[A[0]]
rev_gcd_list=[A[-1]]

for i in range(1,N):
    gcd_list.append(gcd([gcd_list[-1],A[i]]))
    rev_gcd_list.append(gcd([rev_gcd_list[-1],A[-i-1]]))
rev_gcd_list=rev_gcd_list[::-1]

ans=max(gcd_list[N-2],rev_gcd_list[1])
for i in range(1,N-1):
    ans=max(ans,gcd([gcd_list[i-1],rev_gcd_list[i+1]]))
print(ans)

Solution (Python):
def main():
    from fractions import gcd
    def build() :
        for k in range(N0-2,-1,-1) :
            data[k]=gcd(data[2*k+1],data[2*k+2]) 
            
    def update(k,x):
        k+=N0-1
        data[k]=x
        while k+1:
            k=~-k//2
            data[k]=gcd(data[2*k+1],data[2*k+2])
    def query(l,r):
        L,R=l+N0,r+N0
        s=0
        while L<R:
            if R&1:
                R-=1
                s=gcd(s,data[R-1])
            if L&1:
                s=gcd(s,data[L-1])
                L+=1
            L>>=1
            R>>=1
        return s
    n,*a=map(int,open(0).read().split())
    N0=2**(n-1).bit_length()
    data=[0]*2*N0
    for i in range(n):
        data[i + N0 - 1] = a[i]
    build()
    print(max(gcd(query(0,i),query(i+1,n))for i in range(n)))
if __name__=='__main__':
    main()

Solution (Python):
import fractions
 
N = int(input())
A = list(map(int,input().split()))
L = [0] * N
R = [0] * N

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

ans = [0] * N

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

print(max(ans))

Solution (Python):
from fractions import gcd

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

def f(l):
    yield 0
    a = 0
    for i in l:
        a = gcd(a, i)
        yield a

L = list(f(A))
R = list(reversed(list(f(reversed(A)))))

print(max([gcd(a, b) for a, b in zip(L, R[1:])]))

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

def gcd(x, y):
    if x < y:
        x = x ^ y
        y = x ^ y
        x = x ^ y
    div = x % y
    while div != 0:
        x = y
        y = div
        div = x % y
    return y

memo = {}
memo[(0, 1)] = nums[0]
memo[(N-1, N)] = nums[N-1]

for i in range(2, N+1):
    memo[(0, i)] = gcd(memo[(0, i - 1)], nums[i-1])

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

res = 1
for i in range(1, N-1):
    res = max(res, gcd(memo[(0, i)], memo[(i+1, N)]))

res = max(res, memo[(0, N-1)])
res = max(res, memo[(1, N)])

print(res)

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

import fractions
gcd_forward  = [A[0]]*N
gcd_backward = [A[N-1]]*N
for i in range(1,N):
    gcd_forward[i]  = fractions.gcd(A[i],gcd_forward[i-1])
for i in range(N-2,0,-1):
    gcd_backward[i] = fractions.gcd(A[i],gcd_backward[i+1])

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

Solution (Python):
def gcd(a,b):
  while b:a,b=b,a%b
  return a
n,a,b=int(input()),list(map(int,input().split())),[]
if n==2:print(max(a[0],a[1]))
elif n==3:print(max(gcd(a[0],a[1]),gcd(a[0],a[2]),gcd(a[1],a[2])))
else:
  no,mi=a[0],a[0]
  for i in range(1,n):
    s=gcd(no,a[i])
    if s!=no:
      no=max(s,mi)
      mi=gcd(s,mi)
  print(no)

Solution (Python):

import sys
from functools import reduce
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))

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


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

M = [None] * n
R = R[::-1]
for i in range(n):
	M[i] = gcd(L[i], R[i])

print(max(M))

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

def gcd(x, y):
    if x < y:
        x = x ^ y
        y = x ^ y
        x = x ^ y
    div = x % y
    while div != 0:
        x = y
        y = div
        div = x % y
    return y

memo = {}
memo[(0, 1)] = nums[0]
memo[(N-1, N)] = nums[N-1]

for i in range(2, N+1):
    memo[(0, i)] = gcd(memo[(0, i - 1)], nums[i-1])
    


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

res = 1
for i in range(1, N-1):
    res = max(res, gcd(memo[(0, i)], memo[(i+1, N)]))
    

res = max(res, memo[(0, N-1)])
res = max(res, memo[(1, N)])

print(res)

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
def gcd(p,q):
    if p%q: return gcd(q,p%q)
    else: return q
if n==2: print(max(a))
else:
    num,x,num2 = a[2],[],gcd(a[0],a[1])
    for i in range(3,n): num = gcd(num,a[i])
    ans = max(gcd(num,a[0]),gcd(num,a[1]))
    for i in range(1,int(num2**0.5)+1):
        if num2%i==0:
            x.append(i)
            if i**2!=num2: x.append(num2//i)
    x = sorted(x)[::-1]
    for i in x:
        m = 0
        for j in a[2:]:
            if j%i: m+=1
            if m>1: break
        if m<2: break
    print(max(ans,i))

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

Solution (Python):
from fractions import*
from numpy import*

def dv(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

n,*a=map(int,open(0).read().split())
a=array(a)
l=[1]
for i in set(dv(a[0])+dv(a[1])):
    if sum(a%i==0)>=n-1:
        l.append(i)
print(max(l))

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

Solution (Python):
n=int(input())
left=list(map(int,input().split()))
right=list(left)
right.reverse()
gcds=[]
gcdleft=[]
gcdright=[]

gcdleft.append(left[0])
gcdright.append(right[0])

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

if n==2:
    gcds.append(gcdleft[0])
    gcds.append(gcdright[0])
else:
    for i in range(1,n-1):
        gcdleft.append(gcd(gcdleft[i-1],left[i]))
        gcdright.append(gcd(gcdright[i-1],right[i]))
    gcds.append(gcdright[-1])
    for i in range(0,n-2):
    	gcds.append(gcd(gcdleft[i],gcdright[n-3-i]))
    gcds.append(gcdleft[-1])

print(max(gcds))

Solution (Python):
def gcd(x, y):
    if y > x:
        x, y = y, x
    while y:
        x, y = y, x % y
    return x

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

l=[0]*N
l[0]=a[0]
for i in range(1,N):
    l[i]=gcd(l[i-1],a[i])

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

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

print(ans)

Solution (Python):
def gcd(x, y):
    if y > x:
        x, y = y, x
    while y:
        x, y = y, x % y
    return x

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

l=[0]*N
l[0]=a[0]
for i in range(1,N):
    l[i]=gcd(l[i-1],a[i])

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

ans=max(r[1],l[N-2])
for i in range(1,N-1):
    tmp=gcd(l[i-1],r[i+1])
    ans=max(tmp,ans)

print(ans)

Solution (Python):


import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nnn = lambda n: ss2nnn(ii2ss(n))

cache = {}


def gcdr(a, b):
    if a not in cache:
        cache[a] = {}
    if b in cache[a]:
        return cache[a][b]
    if b == 0:
        cache[a][b] = a
        return a
    n = gcdr(b, a % b)
    cache[a][b] = n
    return n

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

def main_lte(N, An):
    if N == 2:
        n = max(An[0], An[1])
        print(n)
        return
    nn = [An[0]] * N
    nn[0] = An[1]
    for i in range(1, N):
        for j in range(N):
            if i == j:
                continue
            nn[j] = gcd(nn[j], An[i])
    print(int(max(nn)))

def main_ok(N, An):
    if N == 2:
        n = max(An[0], An[1])
        print(n)
        return
    nn0 = gcd(An[0], An[1])
    nn1 = set((An[0], An[1]))
    for i in range(2, N):
        t1 = nn0
        nn0 = gcd(nn0, An[i])
        t2 = [gcd(n, An[i]) for n in nn1]
        nn1 = set(t2)
        nn1.add(t1)
    n = max(nn1)
    print(int(n))

def main(N, An):
    nnl = [0] * N
    nnr = [0] * N
    nnl[0] = An[0]
    nnr[N-1] = An[N-1]
    for i in range(1, N):
        nnl[i] = gcd(nnl[i-1], An[i])
    for i in range(N-2, -1, -1):
        nnr[i] = gcd(nnr[i+1], An[i])
    nn = [0] * N
    nn[0] = nnr[1]
    nn[N-1] = nnl[N-2]
    for i in range(1, N-1):
        nn[i] = gcd(nnl[i-1], nnr[i+1])
    n = max(nn)
    print(int(n))

N = i2n()
An = i2nn()
main(N, An)

Solution (Python):
from fractions import*
n,*a=map(int,open(0).read().split())
p=gcd(a[0],a[1])
l=[a[0],p]
c=list(reversed(a))
q=gcd(c[0],c[1])
r=[q]
for i in range(1,n-1):
    p=gcd(p,a[i+1])
    l.append(p)
    q=gcd(q,c[i+1])
    r.append(q)

r=r[::-1]+[a[-1]]
r=r[1:]+[0]
l=[0]+l

print(max(gcd(s,t)for s,t in zip(r,l)))

Solution (Python):
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return a

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

l=[0]*N
l[0]=a[0]
for i in range(1,N):
    l[i]=gcd(l[i-1],a[i])

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

ans=max(r[1],l[N-2])
for i in range(1,N-1):
    tmp=gcd(l[i-1],r[i+1])
    ans=max(tmp,ans)

print(ans)

Solution (Python):

import sys

import heapq
import re
import bisect
import random
import math
import fractions
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

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

left = [0] * (n + 1)
right = [0] * (n + 1)
for i in range(n):
    left[i + 1] = fractions.gcd(left[i], a[i])
for i in reversed(range(n)):
    right[i] = fractions.gcd(right[i + 1], a[i])
mx = 0
for i in range(n):
    l = left[i]
    r = right[i + 1]
    mx = max(mx, fractions.gcd(l, r))
print(mx)

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

n = int(input())
a = list(map(int, input().split()))
A = list(set(a))
ans = [reduce(gcd, A)]

if len(A) == 1:
    print(A[0])
    exit()
for i in A:
    b = sorted(A)
    b.remove(i)
    if a.count(i) == 1:
        ans.append(reduce(gcd, b))

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

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

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

from fractions import gcd

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

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

print(max(gcd(l, r) for l, r in zip(L[:N], R[1:])))

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

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

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

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

print(max(m))