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

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

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

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


ide_ele = 0
num =2**(n-1).bit_length() 
seg=[ide_ele]*(2*num - 1)
init(a)
ans = 0
for i in range(n):
    ans = max(ans, fractions.gcd(query(0,i), query(i+1, n)))
print(ans)

Solution (Python):
def main():
    import sys
    from fractions import gcd
    input = sys.stdin.readline
    
    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 ide_ele
        p += num-1
        q += num-2
        res=ide_ele
        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
    n = int(input())
    a = list(map(int,input().split()))
    
    
    
    
    ide_ele = 0
    
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num
    init(a)

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

if __name__ == '__main__':
    main()

Solution (Python):
from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
left = [0] * (n + 1)
right = [0] * (n + 1)
middle = [0] * (n + 1)

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

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

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

print(max(middle))

Solution (Python):
import sys
input = sys.stdin.readline

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

def gcd(x,y):
  while y:
    x, y = y, x%y
  return x

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

print(max(ll[n-2], lr[1], *[gcd(l,r) for l,r in zip(ll[:n-2], lr[2:])]))

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

def gcd(x,y):
  while y:
    x, y = y, x%y
  return x

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

print(max(ll[n-2], lr[1], *[gcd(l,r) for l,r in zip(ll[:n-2], lr[2:])]))

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
L = [0]
R = [0]
import fractions
def GCD(a,b):
    if a*b != 0:
        return fractions.gcd(a,b)
    else:
        return max(a,b)
for i in range(N-1):
    x = A[i]
    y = A[-i-1]
    L.append(GCD(L[i],x))
    R.append(GCD(R[i],y))
ans = 0
for i in range(N):
    x = L[i]
    y = R[-i-1]
    ans = max(GCD(x,y),ans)
print(ans)

Solution (Python):
def gcd(xxx,yyy):
    if xxx<yyy:
        xxx,yyy=yyy,xxx
    if yyy==0:
        return xxx
    else:
        return gcd(yyy,xxx%yyy)

def seg_tree_update(n,x):
    ind=2**m-1+n
    tree[ind]=x
    ind=(ind-1)//2
    while ind>=0:
        tree[ind]=gcd(tree[2*ind+1],tree[2*ind+2])
        ind=(ind-1)//2

def seg_tree_find_gcd(L,R):
    qqq=A[L]
    L,R=2**m-1+L,2**m-1+R
    while L<R:
        if L%2==0:
            qqq=gcd(qqq,tree[L])
        if R%2==1:
            qqq=gcd(qqq,tree[R])
        L//=2
        R=R//2-1
        
    if L==R:
        qqq=gcd(qqq,tree[L])
    return qqq

N=int(input())
A=list(map(int,input().split()))
inf=float("inf")
m=0
while pow(2,m)<N:
    m+=1
tree=[0]*(pow(2,m+1)-1)

for i in range(N):
    seg_tree_update(i,A[i])
    
ans=max(seg_tree_find_gcd(1,N-1),seg_tree_find_gcd(0,N-2))
for i in range(1,N-1):
    ddd=gcd(seg_tree_find_gcd(0,i-1),seg_tree_find_gcd(i+1,N-1))
    ans=max(ans,ddd)
print(ans)

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

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

    if N == 2:
        print(max(A))
        exit()

    A0, A1, A2 = A[:3]
    A_min_sq = int(math.sqrt(A2)) + 1
    
    gcd_ls = set()
    for i in range(A_min_sq, 0, -1):
        div = set()
        c = 0
        if A0 % i == 0:
            div.add(A0 // i)
            c += 1
        if A1 % i == 0:
            div.add(A1 // i)
            c += 1
        if A2 % i == 0:
            div.add(A2 // i)
            c += 1
        if c < 2:
            continue
        gcd_ls.add(i)

        for j in div:
            if A0 % j == 0 and (A1 % j == 0 or A2 % j == 0):
                gcd_ls.add(j)
            elif A1 % j == 0 and A2 % j == 0:
                gcd_ls.add(j)
    gcd_ls = sorted(gcd_ls, reverse=True)

    for i in gcd_ls:
        wa = False
        for j in A:
            if j % i != 0:
                if wa:
                    break
                wa = True
        else:
            print(i)
            exit()

if __name__ == '__main__':
    main()

Solution (Python):
def gcd(m, n):
    r = m % n
    return n if r == 0 else gcd(n, r)


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

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

GCD = [1] * n
GCD[0], GCD[-1] = GCD_right[1], GCD_left[-2]
for i in range(1, n - 1):
    GCD[i] = gcd(GCD_left[i - 1], GCD_right[i + 1])

print(max(GCD))

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def gcd(a, b):

    if a == 0:
        return b
    if b == 0:
        return a

    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return b

def main():
    N = INT()
    A = LIST()
    A.insert(0, 0)
    A.append(0)
    L = [0] * (N + 2)
    R = [0] * (N + 2)
    L[0] = 0
    
    R[N + 1] = 0
    for i in range(0, N + 1):
        L[i + 1] = gcd(L[i], A[i])
    for i in range(N, -1, -1):
        R[i] = gcd(R[i + 1], A[i])

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

if __name__ == "__main__":
    main()

Solution (Python):
import sys

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

n, *a = map(int, sys.stdin.read().split())

def main():
    l_gcd = [None] * n
    r_gcd = [None] * n
    l_gcd[1] = a[0]
    r_gcd[n-2] = a[-1]

    for i in range(2, n):
        l_gcd[i] = gcd(l_gcd[i-1], a[i-1])
    for i in range(n-3, -1, -1):
        r_gcd[i] = gcd(r_gcd[i+1], a[i+1])

    res = max(r_gcd[0], l_gcd[n-1])
    for i in range(1, n-1):
        res = max(res, gcd(l_gcd[i], r_gcd[i]))
    return res

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

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

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

import fractions
ans=0
left=[0]
for i in range(1,n):
    ans=fractions.gcd(ans,al[i-1])
    left.append(ans)

right=[0 for i in range(n+1)]
for i in range(1,n+1):
    right[n-i]=fractions.gcd(right[n-i+1],al[n-i])


ans=0

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

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
A = inpl()

if len(A) <= 2:
    ans = max(A)
else:
    gcd_left = [A[0]]
    gcd_right = [A[N-1]] 
    for i in range(N-1):
        gcd_left.append(gcd(gcd_left[i],A[i+1]))
        gcd_right.append(gcd(gcd_right[i],A[N-2-i]))
    p_ans1 = max([gcd(gcd_left[i], gcd_right[N-i-3]) for i in range(N-2)])
    p_ans2 = gcd_left[N-2]
    p_ans3 = gcd_right[N-2]
    ans = max(p_ans1, p_ans2, p_ans3)
print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
def gcd(m, n):
  while n != 0:
    m, n = n, m % n
  return m
gl = [A[0]]
gr = [A[N-1]]
x, y = A[0], A[N-1]
for i in range(1, N):
  x = gcd(x, A[i])
  gl.append(x)
  y = gcd(y, A[N-i-1])
  gr.append(y)
gg = [gr[N-2]]
for i in range(1, N-1):
  gg.append(gcd(gl[i-1], gr[N-i-2]))
gg.append(gl[N-2])
if N != 2:
  print(max(gg))
else:
  print(max(A[0], A[1]))

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

GCDF, GCDB = [0]*N, [0]*N
GCDF[1],GCDB[-2] = A[0], A[N-1]
for i in range(2, N):
    GCDF[i] = gcd(GCDF[i-1],A[i-1])
    GCDB[-(i+1)] = gcd(GCDB[-i], A[-i])
GCDm = [0]*N
GCDm[0] = GCDB[0]
GCDm[N-1] = GCDF[N-1]
for i in range(1, N-1):
    GCDm[i] = gcd(GCDF[i],GCDB[i])
ans = max(GCDm)
print(ans)

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

Solution (Python):

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

from fractions import gcd
from itertools import accumulate

X = list(accumulate(A, gcd))
Y = list(accumulate(A[::-1], gcd))

Y.insert(0,0)
X.insert(0,0)

ans = -1
for i in range(N):
  ans = max(ans, gcd(X[i], Y[N-1-i]))

print(ans)

Solution (Python):
from fractions import gcd

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

gcdl = [0] * n
gcdr = gcdl[:]

gcdl[0]  = a[0]
gcdr[-1] = a[-1] 

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

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

max_gcd = max(gcdl[-2], gcdr[1])

for i in range(1, n - 1):
  temp_gcd = gcd(gcdl[i - 1], gcdr[i + 1])
  if temp_gcd > max_gcd:
    max_gcd = temp_gcd

print(max_gcd)

Solution (Python):
def gcd(a,b):
  if a*b == 0:
    return max(a,b)
  if a<b:
    a,b = b,a
  return gcd(b,a%b)
n = int(input())
ls = list(map(int,input().split()))
length = 2**(n.bit_length())
calc = gcd
unit = 0
Seg = [unit for i in range(length*2-1)]
def init():
  for i in range(n):
    Seg[i+length-1] = ls[i]
  for i in range(length-2,-1,-1):
    Seg[i] = calc(Seg[2*i+1],Seg[2*i+2])
def update(i,x):
  i += length-1
  Seg[i] = x
  while i>0:
    i = (i-1)//2
    Seg[i] = calc(Seg[2*i+1],Seg[2*i+2])
def query(a,b,k,l,r):
  if r<=a or b<=l:
    return unit
  if a<=l and r<=b:
    return Seg[k]
  else:
    vl = query(a,b,2*k+1,l,(l+r)//2)
    vr = query(a,b,2*k+2,(l+r)//2,r)
    return calc(vl,vr)

init()
ans = []
for i in range(n):
  ans.append(gcd(query(0,i,0,0,length),query(i+1,n,0,0,length)))
print(max(ans))

Solution (Python):
def gcd(a,b):
  if a*b == 0:
    return max(a,b)
  if a<b:
    a,b = b,a
  return gcd(b,a%b)
n = int(input())
ls = list(map(int,input().split()))
length = 2**(n.bit_length())
calc = gcd
unit = 0
Seg = [unit for i in range(length*2-1)]
def init():
  for i in range(n):
    Seg[i+length-1] = ls[i]
  for i in range(length-2,-1,-1):
    Seg[i] = calc(Seg[2*i+1],Seg[2*i+2])
def update(i,x):
  i += length-1
  Seg[i] = x
  while i>0:
    i = (i-1)//2
    Seg[i] = calc(Seg[2*i+1],Seg[2*i+2])
def query(a,b,k,l,r):
  if r<=a or b<=l:
    return unit
  if l<=a and b<=r:
    return Seg[k]
  else:
    vl = query(a,b,2*k+1,l,(l+r)//2)
    vr = query(a,b,2*k+2,(l+r)//2,r)
    return calc(vl,vr)

init()
ans = []
for i in range(n):
  update(i,0)
  ans.append(query(0,n,0,0,length))
  update(i,ls[i])
print(max(ans))

Solution (Python):
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
input()
l = list(map(int,input().split()))
gcd_l = [i for i in l]
gcd_r = [i for i in l]
for i in range(1,len(l)):
    gcd_l[i] = gcd(gcd_l[i-1],gcd_l[i])

for i in range(0, len(l)-1)[::-1]:
    gcd_r[i] = gcd(gcd_r[i+1], gcd_r[i])

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

Solution (Python):
from fractions import gcd

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

L = [0]
R = [0]

g = A[0]
for a in A:
  g = gcd(g, a)
  L.append(g)

A = A[::-1]
g = A[0]
for a in A:
  g = gcd(g, a)
  R.append(g)

R = R[::-1]

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

print(ans)

Solution (Python):
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor


"""
DP1[i][j] =the maximum sum of deliciousness of dishes, which are chosen from 1st- to i-th dishes,
such that he can finish them in j minutes

still WA!!!

"""


def gcd(a, b):
    if a < b:
        return gcd(b, a)
    elif a % b:
        return gcd(b, a % b)
    else:
        return b


N = gi()
A = [0] * N
ls = [0] * N
rs = [0] * N

for i in range(N):
    A[i] = gi()

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

ans = max(ls[N - 2], rs[1])

for mid in range(1, N - 1):
    ans = max(ans, gcd(ls[mid - 1], rs[mid + 1]))

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]
import fractions
from functools import reduce

def gcd(*numbers):
    return abs(reduce(fractions.gcd, numbers))

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

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

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

L=[0]*(N+1)
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[N-i-1])

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

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

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

fromLeft = [a[0]] + [None] * (n - 1)
for i in range(1, n):
    fromLeft[i] = gcd(fromLeft[i - 1], a[i])
fromRight = [None] * (n - 1) + [a[-1]]
for i in range(n - 2, -1, -1):
    fromRight[i] = gcd(fromRight[i + 1], a[i])
ret = 1
for repr in range(n):
    if repr == 0:
        curGcd = fromRight[repr + 1]
    elif repr == n - 1:
        curGcd = fromLeft[repr - 1]
    else:
        curGcd = gcd(fromLeft[repr - 1], fromRight[repr + 1])
    ret = max(ret, curGcd)
print(ret)

Solution (Python):
import os, sys, re, math, fractions

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

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

memo_L = [1] * N
memo_R = [1] * N

for i in range(N):
    if i == 0:
        memo_L[i] = A[i]
        memo_R[i] = A[N-1]
    elif i == N - 1:
        memo_L[i] = gcd(A[i], memo_L[i-1])
        memo_R[i] = gcd(A[0], memo_R[i-1])
    else:
        memo_L[i] = gcd(A[i], memo_L[i-1])
        memo_R[i] = gcd(A[N-1-i], memo_R[i-1])

memo_R.reverse()

ret = 1
for j in range(N):
    if j == 0:
        ret = max(ret, memo_R[1])
    elif j == N-1:
        ret = max(ret, memo_L[j-1])
    else:
        common_gcd = fractions.gcd(memo_L[j-1], memo_R[j+1])
        ret = max(ret, common_gcd)

print(ret)

Solution (Python):
import os, sys, re, math, fractions

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

memo_L = [1] * N
memo_R = [1] * N

for i in range(N):
    if i == 0:
        memo_L[i] = A[i]
        memo_R[i] = A[N-1]
    elif i == N - 1:
        memo_L[i] = fractions.gcd(A[i], memo_L[i-1])
        memo_R[i] = fractions.gcd(A[0], memo_R[i-1])
    else:
        memo_L[i] = fractions.gcd(A[i], memo_L[i-1])
        memo_R[i] = fractions.gcd(A[N-1-i], memo_R[i-1])

memo_R.reverse()

ret = 1
for j in range(N):
    if j == 0:
        ret = max(ret, memo_R[1])
    elif j == N-1:
        ret = max(ret, memo_L[j-1])
    else:
        common_gcd = fractions.gcd(memo_L[j-1], memo_R[j+1])
        ret = max(ret, common_gcd)

print(ret)

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

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


n = int(input())
nl = sorted(list(map(int, input().split(' '))))
rl = nl[::-1]
sumnl = [nl[0]]
sumrl = [rl[0]]
for i in range(1, len(nl)):
    sumnl.append(gcd(sumnl[-1], nl[i]))
    sumrl.append(gcd(sumrl[-1], rl[i]))
sumrl = sumrl[::-1]
if len(sumnl) == 1:
    print(sumnl[0])
else:
    print(max([sumnl[-2]] + [gcd(sumnl[i],sumrl[i+2]) for i in range(len(sumrl) - 2)] + [sumrl[1]]))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
def gcd(a, b):
    return b if a == 0 else gcd(b % a, a)
l = [0]
r = [0]
for i in range(n):
    l.append(gcd(l[-1], a[i]))
    r.append(gcd(r[-1], a[n - i - 1]))
ret = 0
for i in range(n):
    ret = max(ret, gcd(l[i], r[n - i - 1]))
print(ret)

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


N = int(input())
A = list(map(int, input().split()))
r = 0
b = -1

for i in range(N):
    a = gcd(r, A[i]) if r != 0 else A[i]
    if a < r:
        b = i
    r = a

r3 = 0
for i in range(N):
    if i == b - 1:
        continue
    r3 = gcd(r3, A[i]) if r3 != 0 else A[i]

r4 = 0
for i in range(N):
    if i == b:
        continue
    r4 = gcd(r4, A[i]) if r4 != 0 else A[i]

d = sorted([(gcd(A[i], A[i + 1]), i) for i in range(N - 1)])
t = d[0][1]
r1 = 0
for i in range(N):
    a = A[i-1] if i == t + 1 else A[i]
    if r1 == 0:
        r1 = a
    else:
        r1 = gcd(r1, a)
r2 = 0
for i in range(N):
    a = A[i+1] if i == t else A[i]
    if r2 == 0:
        r2 = a
    else:
        r2 = gcd(r2, a)
print(max(r1, r2, r3, r4))

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

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

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

print(ans)

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

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

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

ans=rightgcd[1]
for i in range(1,n-1):
	ans=max(ans,gcd(leftgcd[i-1],rightgcd[i+1]))
print(max(ans,leftgcd[n-2]))

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

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

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



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



ans = max(gcdf[-2],gcdb[1])

for i in range(1,N-1):
    ans = max(ans,gcd(gcdf[i-1],gcdb[i+1]))

print(ans)

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

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

l_ans = [0] * n
g = 0
for i in range(1, n):
    g = gcd(g, v[i-1])
    l_ans[i] = g
r_ans = [0] * n
g = 0
for i in range(1, n):
    g = gcd(g, v[n-i])
    r_ans[i] = g
r_ans.reverse()
ans = 1
for i in range(n):
    ans = max(ans, gcd(l_ans[i], r_ans[i]))
print(ans)

Solution (Python):
import fractions
N = int(input())
A = [int(x) for x in input().split()]
kouho_set = set()
kouho_set = [0] * (N + 1)
kouho_set[0] = set()
kouho_set[0].add(A[1])
nowgcd = A[0]
for i in range(1, N):
    kouho_set[i] = set()
    for j in kouho_set[i-1]:
        kouho_set[i].add(fractions.gcd(A[i], j))
    kouho_set[i].add(nowgcd)
    nowgcd = fractions.gcd(A[i], nowgcd)

print(max(kouho_set[N-1]))

Solution (Python):
N=int(input())
A=sorted(list(map(int,input().split())))
min0,min1=A[0],A[1]

if min0==min1==1:
    print(1)
    exit()
if N==2:
    print(max(A))
    exit()
yakusuu0lst=[]
yakusuu1lst=[]

if min0>1:
    for i in range(1,int(min0**0.5+1)):
        if min0%i==0:
            yakusuu0lst.append(i)
            yakusuu0lst.append(min0//i)
if min1>1:
    for i in range(1,int(min1**0.5+1)):
        if min1%i==0:
            yakusuu1lst.append(i)
            yakusuu1lst.append(min1//i)
yakusuu0count=[0 for i in range(len(yakusuu0lst))]
yakusuu1count=[0 for i in range(len(yakusuu1lst))]
length0=len(yakusuu0lst)
length1=len(yakusuu1lst)

for a in A:
    for i in range(length0):
        if a%yakusuu0lst[i]==0:yakusuu0count[i]+=1
    for i in range(length1):
        if a%yakusuu1lst[i]==0:yakusuu1count[i]+=1


div=1
for i in range(length0):
    if yakusuu0count[i]>=N-1 and div<yakusuu0lst[i]:
        div=yakusuu0lst[i]

for i in range(length1):
    if yakusuu1count[i]>=N-1 and div<yakusuu1lst[i]:
        div=yakusuu1lst[i]

print(div)

Solution (Python):
import sys
input = sys.stdin.readline
import fractions
 
 
def main():
    N = int(input())
    A = list(map(int, input().split()))
 
    L_gcds = [0] * N
    L_gcd_tmp = L_gcds[0]
    for i in range(1, N):
        L_gcd_tmp = fractions.gcd(L_gcd_tmp, A[i-1])
        L_gcds[i] = L_gcd_tmp
 
    R_gcds = [0] * N
    R_gcd_tmp = R_gcds[0]
    for j in range(1, N):
        R_gcd_tmp = fractions.gcd(R_gcd_tmp, A[N-j])
        R_gcds[j] = R_gcd_tmp
    R_gcds.reverse()
 
    LR_gcds = [0] * N
    for k in range(0, N):
        LR_gcds[k] = fractions.gcd(L_gcds[k], R_gcds[k])
 
    print(max(LR_gcds))
 
main()

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
class SegmentTree:
    def segfunc(self,x,y):
        return gcd(x,y)

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

n = onem()

a = l()


ans = 0
p = SegmentTree(n,a,0)
for i in range(n):
    ans = max(ans,gcd(p.query(0,i),p.query(i+1,n)))
print(ans)

Solution (Python):
N = int(input())
A=sorted(list(map(int,input().split())))
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
ans = []
gcdlist = [A[0]]
for i in range(1,N):
    gcdlist.append(gcd(gcdlist[i-1],A[i]))
gcdlistr = [A[-1]]
for i in range(N-2,-1,-1):
    gcdlistr.append(gcd(gcdlistr[N-i-2],A[i]))
gcdlistr.reverse()
gcdlist.insert(0,0)
gcdlist.append(0)
gcdlistr.insert(0,0)
gcdlistr.append(0)
for i in range(N):
    ans.append(gcd(gcdlist[i],gcdlistr[i+2]))
print(max(ans))

Solution (Python):


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

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

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

ans=1

if RCD[N-2]>ans:
    ans=RCD[N-2]

for i in range(1,N-1):
    if gcd(LCD[i-1],RCD[N-i-2])>ans:
        ans=gcd(LCD[i-1],RCD[N-i-2])

if LCD[N-2]>ans:
    ans=LCD[N-2]
print(ans)

Solution (Python):
import fractions
import math


def gcd(a,b):
    return fractions.gcd(a, b)




def calculate(arr):
    
    L = [arr[0]]*len(arr)

    
    R = [arr[-1]]*len(arr)

    for i in range(len(arr)):
        if i == 0:
            continue

        L[i] = gcd(L[i-1],arr[i])


        R[len(arr) - (i + 1)] = gcd(R[len(arr) - i],arr[len(arr) - (i + 1)])

    max = 0
    for i in range(len(arr)):

        if i == 0:
            max = R[i+1]

        elif i == len(arr) - 1:
            if max < L[i-1]:
                max = L[i-1]
        else:
            if max < gcd(L[i-1],R[i+1]):
                max = gcd(L[i-1],R[i+1])

    print(max)

N = int(input())
arr = [int(s) for s in input().split(" ")]
calculate(arr)

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

left = []
right = []
left.append(1)
right.append(1)
left.append(l[0])
right.append(l[-1])
le = l[0]
ri = l[-1]
for i in range(1,n-1):
    le = fractions.gcd(le,l[i])
    left.append(le)
    ri = fractions.gcd(ri,l[-i-1])
    right.append(ri)
m = []
for i in range(1,n-1):
    m.append(fractions.gcd(left[i],right[-i-1]))
m.append(left[-1])
m.append(right[-1])
print(max(m))

Solution (Python):

from fractions import gcd



def segfunc(x,y):
    if x==0 or y==0:
        return x+y
    return gcd(x,y)



def init(init_val):
    
    for i in range(N):
        seg[i+num-1]=init_val[i]    
    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
        


def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

        

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



ide_ele = 0

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


num =2**(N-1).bit_length()
seg=[ide_ele]*2*num
init(A)


max_gcd=[0]*N
for i in range(N):
    gcd_l=query(0,i)
    gcd_r=query(i+1,N)
    max_gcd[i]=gcd(gcd_l,gcd_r)
print(max(max_gcd))

Solution (Python):

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

Solution (Python):
import sys
input = sys.stdin.readline
import fractions


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

    L_gcds = [0] * N
    L_gcd_tmp = L_gcds[0]
    for i in range(1, N):
        L_gcd_tmp = fractions.gcd(L_gcd_tmp, A[i-1])
        L_gcds[i] = L_gcd_tmp

    R_gcds = [0] * N
    R_gcd_tmp = R_gcds[0]
    for j in range(1, N):
        R_gcd_tmp = fractions.gcd(R_gcd_tmp, A[N-j])
        R_gcds[j] = R_gcd_tmp
    R_gcds.reverse()

    LR_gcds = [0] * N
    for k in range(0, N):
        LR_gcds[k] = fractions.gcd(L_gcds[k], R_gcds[k])

    print(max(LR_gcds))

main()