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

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

Solution (Python):
from fractions import gcd

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

fgcd, ftmp = [], a[0]
for i in a:
    ftmp = gcd(ftmp, i)
    fgcd.append(ftmp)

bgcd, btmp = [], a[-1]
for i in a[::-1]:
    btmp = gcd(btmp, i)
    bgcd.append(btmp)
bgcd = bgcd[::-1]

egcd = [bgcd[1]] + [0] * (n - 2) + [fgcd[n - 2]]
for i in range(1, n - 1):
    egcd[i] = gcd(fgcd[i - 1], bgcd[i + 1])
print(max(egcd))

Solution (Python):
from fractions import gcd

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

fgcd, ftmp = [], a[0]
for i in a:
    ftmp = gcd(ftmp,i)
    fgcd.append(ftmp)

bgcd, btmp = [], a[-1]
for i in a[::-1]:
    btmp = gcd(btmp, i)
    bgcd.append(btmp)
bgcd=bgcd[::-1]

egcd = [bgcd[1]] + [0] * (n - 2) + [fgcd[n - 2]]
for i in range(1, n - 1):
    egcd[i] = gcd(fgcd[i - 1], bgcd[i + 1])
print(max(egcd))

Solution (Python):
from fractions import gcd

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

L = [-1] * (N-1)
L[0] = A[0]
R = [-1] * (N-1)
R[0] = A[-1]

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

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

ans = max(ans, L[N-2])
ans = max(ans, R[N-2])
print(ans)

Solution (Python):
from collections import deque
from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
l = a[0]
r = a[-1]
ll = deque([l])
rl = deque([r])
for i in range(1,n-1):
    l = gcd(l,a[i])
    r = gcd(r,a[-(i+1)])
    ll.append(l)
    rl.appendleft(r)

llas = ll.pop()
rlas = rl.popleft()

res = max(llas,rlas)
for i in range(n-2):
    res = max(res, gcd(ll.pop(), rl.pop()))
print(res)

Solution (Python):
from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
GCD= a[0]
dp = [set() for i in range(n)]
dp[1].add(a[0])
dp[1].add(a[1])
for i in range(1,n):
    x = a[i]
    for j in dp[i-1]:
            dp[i].add(gcd(j,x))
    if x % GCD != 0:
        dp[i].add(GCD)
        GCD = gcd(GCD,x)
print(max(dp[n-1]))

Solution (Python):
from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
GCD= a[0]
dp = [set() for i in range(n)]
dp[0].add(a[0])
dp[0].add(a[1])
for i in range(1,n):
    x = a[i]
    for j in dp[i-1]:
            dp[i].add(gcd(j,x))
    if x % GCD != 0:
        dp[i].add(GCD)
        GCD = gcd(GCD,x)
print(max(dp[n-1]))

Solution (Python):
from fractions import gcd


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



def init(a):
    for i in range(n):
        seg[i+num-1] = a[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(res, segfunc(seg[p], seg[q]))
    
    return res


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

ide_ele = 0
num = 2 ** (len(bin(n - 1)) - 2)
seg = [ide_ele] * 2 * num
init(a)

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

print(res)

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

left.append(a[0])
for i in range(1,n-1):
    left.append(gcd(left[-1],a[i]))
a = a[::-1]
right.append(a[0])
for i in range(1,n-1):
    right.append(gcd(right[-1],a[i]))
ans = 1
for i in range(n-1):
    ans = max(ans,gcd(left[i],right[n-i-3]))
ans = max(ans,left[n-2],right[n-2])
print(ans)

Solution (Python):
from fractions import gcd


def init(a):
    for i in range(n):
        seg[i+num-1] = a[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 % 2 == 0:
            res = gcd(res, seg[p])
        if q % 2 == 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 ** (len(bin(n - 1)) - 2)
seg = [ide_ele] * 2 * num
init(a)

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

print(res)

Solution (Python):
from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
left = a[:]
right = a[:]
for i in range(1, n):
  left[i] = gcd(left[i], left[i-1])
  right[n-i-1] = gcd(right[n-i], right[n-i-1])
maximum = max(left[n-2], right[1])
for i in range(n-2):
  common_divisor = gcd(left[i], right[i+2])
  if common_divisor > maximum:
    maximum = common_divisor
print(maximum)

Solution (Python):



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

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])
    R[n - i - 1] = gcd(R[n - i], A[n - i - 1])
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] + [int(i) for i in input().split()] + [0]


L = [0 for i in range(n+1)]
R = [0 for i in range(n+1)]
M = [0 for i in range(n)]


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


print(max(M))

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache






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






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


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 make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


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


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


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




N = I()
A = IL()

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

kake1 = A[0]
kake2 = A[1]
zenbu = gcd(A[0],A[1])

for a in A[2:]:
  kake1 = max(gcd(kake1,a),zenbu)
  kake2 = max(gcd(kake2,a),zenbu)
  zenbu = gcd(zenbu,a)
print(max(kake1,kake2,zenbu))

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

'''
'init(a)': 配列aで初期化。O(N)
'update(k,x)': a[k]をxに変更 O(logN)
'query(p,q)': [p,q)について "segfunc" したものを返す O(logN)
'ide_ele' : 単位元。
'''


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



ide_ele = 0


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

init(A)



ans = 1
for i in range(N):
    if i == 0:
        ans = max(ans, query(1, N))
    elif i == N-1:
        ans = max(ans, query(0, N-1))
    else:
        ans = max(ans, fractions.gcd(query(0, i), query(i+1, N)))
print(ans)

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

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

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

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

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

right = [None] * N
right[-1] = A[-1]
for i in range(len(A) - 2,-1,-1):
  right[i] = gcd(right[i + 1],A[i])

ans = max(left[-2],right[1])
for i in range(1, len(A) - 1):
  g = gcd(left[i - 1],right[i + 1])
  if ans < g:
    ans = g
print(ans)

Solution (Python):
from fractions import gcd


def init(a):
    for i in range(n):
        seg[i+num-1] = a[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 ** (len(bin(n - 1)) - 2)
seg = [ide_ele] * 2 * num
init(a)

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

print(res)

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

Solution (Python):
import fractions
from functools import reduce
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]))
  right[N-i-1] = (fractions.gcd(right[N-i],A[N-1-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=[int(i) for i in input().split()]
a1=[a[0]]
for i in range(1,n-1):
    a1.append(gcd(a1[-1],a[i]))
a2=[a[-1]]
for i in range(n-2,0,-1):
    a2.append(gcd(a2[-1],a[i]))
m=[]
for i in range(n-2):
    m.append(gcd(a1[i],a2[-i-2]))
m.append(a1[-1])
m.append(a2[-1])
print(max(m))

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
size=len(a)
def gcd(a,b):
    while True:
        r=a%b
        if r==0:
            return b
        a,b=b,r
forward=[]
backward=[]
temp=a[0]
for ele in a:
    temp=gcd(temp,ele)
    forward.append(temp)

temp=a[len(a)-1]
for ele in reversed(a):
    temp=gcd(temp,ele)
    backward.append(temp)
backward.reverse()
ans=max(backward[1],forward[len(a)-2])
for i in range(len(a)-2):
    temp=gcd(forward[i],backward[i+2])
    ans=max(ans,temp)
print(ans)

Solution (Python):
import fractions

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

L=[0]*(N+1)
R=[0]*(N+1)

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

for i in range(N):
    j=N-i

    L[i+1]=gcd(L[i],A[i])
    R[j-1]=gcd(R[j],A[j-1])
ans=0

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

print(ans)

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

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

import fractions
left, right = [], []
for arr, l in zip([a, a[::-1]], [left, right]):
    l.append(arr[0])
    for i in range(1, n):
        l.append(fractions.gcd(l[-1], arr[i]))

left = [right[-1], right[-2]] + left
right = right[::-1] + [left[-2], left[-1]]

ans = 0
for (l, r) in zip(left, right):
    ans = max(ans, fractions.gcd(l, r))

print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
from fractions import gcd
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

from itertools import permutations
from math import factorial, hypot

N = getN()
A = getList()

course = []
x1 = A[0]
for i in A:
    x2 = i
    opt = gcd(x1, x2)
    course.append(opt)
    x1 = opt

reverse = []
y1 = A[-1]
for i in A[::-1]:
    y2 = i
    opt = gcd(y1, y2)
    reverse.append(opt)
    y1 = opt
reverse.sort()

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

Solution (Python):


import fractions

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


left_gcd = [0 for _ in range(n)]
right_gcd = [0 for _ in range(n)]

left_gcd[0] = a[0]
right_gcd[-1] = a[-1]

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

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



ans = 1
for i in range(1, n-1):
    num1 = left_gcd[i-1]
    num2 = right_gcd[i+1]
    ans = max(ans, fractions.gcd(num1, num2))

ans = max(ans, right_gcd[1], left_gcd[-2])
print(ans)

Solution (Python):
import sys
import heapq
import re
from heapq import heapify, heappop, heappush
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)


def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True



def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


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




    


left = [0 for i in range(n)]
right = [0 for i in range(n)]
ans = 0
for i in range(n):
    if i == 0:
        left[i] = a[i]
    else:
        left[i] = gcd(left[i - 1], a[i])
for i in reversed(range(n)):
    if i == n - 1:
        right[i] = a[i]
    else:
        right[i] = gcd(right[i + 1], a[i])


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

Solution (Python):
from fractions import gcd

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

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

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

Solution (Python):
import sys
from fractions import gcd

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

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

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

Solution (Python):
from fractions import gcd

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

left = [0 for _ in range(N+1)]
right = [0 for _ in range(N+1)]

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

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

print(ans)

Solution (Python):
"""参考
@ct158603292321　　2019年05月03日に更新
qiita AtCoder ABC125 解説
https://qiita.com/ct158603292321/items/4cddafa5c2500a657ccf
"""

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


import numpy as np
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A_np =np.array(A)


div_A_2 =make_divisors(A[0]) + make_divisors(A[1])
ans =[]
for i in div_A_2:
    aa= np.count_nonzero(A_np %i ==0) 
    if aa >=N-1:
        ans.append(i)
print(max(ans))

Solution (Python):
import sys
N=int(input())
A=list(map(int,input().split()))
A.sort()
MIN=A[1]
for i in range(MIN,0,-1):
  miss=0
  for k in range(N):
    if A[k]%i != 0:
      miss+=1
      if miss==2:
        break
    if k==N-1:
      ans=i
      print(ans)
      sys.exit()

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

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

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N = int(input())

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

a = List[0]
L = [0 for i in range(N)]
L[0] = a
for i in range(1,N):
  L[i] = gcd(List[i],L[i-1])
  
a = List[-1]
R = [0 for i in range(N)]
R[0] = a
for i in range(1,N):
  R[i] = gcd(List[-i-1],R[i-1])


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

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

def gcd(n, m):
    
    a = max(n,m)
    b = min(n,m)
    while b:
        a, b = b, a % b
    return a

g = As[0]
left = []
for a in As:
    g = gcd(g, a)
    left.append(g)

As_r = As[::-1]
g_r = As_r[0]
right = []    
for a in As_r:
    g_r = gcd(g_r, a)
    right.append(g_r)
    
l = left
r = right[::-1]
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:     
        g = gcd(l[i-1],r[i+1])
        ans = max(ans, g)
print(ans)

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

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

left = [0 for _ in range(N + 1)]
right = [0 for _ in range(N + 1)]

for i in range(1, N + 1):
    left[i] = gcd_(left[i - 1], A[i - 1])
for i in reversed(range(N)):
    right[i] = gcd_(right[i + 1], A[i])

ans = -1
for i in range(N):
    ans = max(gcd_(left[i], right[i + 1]), ans)
print(ans)

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

X = [0]*N
Y = [0]*N

import fractions

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

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

cand = []
cand.append(X[N-2])
cand.append(X[N-1])
cand.append(Y[1])
for i in range(1,N-1):
    cand.append(fractions.gcd(X[i-1],Y[i+1]))

print(max(cand))

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

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

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

n = int(input())
aaa = list(map(int, input().split()))
cnt_l = [0] * (n - 1)
cnt_r = [0] * (n - 1)

cnt_l[0] = aaa[0]
for i in range(1, n - 1):
    cnt_l[i] = gcd(cnt_l[i - 1], aaa[i])

aaa.reverse()
cnt_r[0] = aaa[0]
for i in range(1, n - 1):
    cnt_r[i] = gcd(cnt_r[i - 1], aaa[i])

cnt_l = [cnt_r[-1]] + cnt_l
cnt_r = [cnt_l[-1]] + cnt_r
cnt_r.reverse()

ans = 1
for i in range(n):
    tmp = gcd(cnt_l[i], cnt_r[i])
    ans = max(ans, tmp)

print(ans)

Solution (Python):
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 = int(input())
A = list(map(int,input().split()))
l=[]
cnt = 0
for i in set(dv(A[0])+dv(A[1])):
    cnt = 0
    for j in range(len(A)):
        if A[j]%i == 0:
            cnt += 1
    if cnt >= N-1:
        l.append(i)
print(max(l))

Solution (Python):
from fractions import gcd


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] = (gcd(left[i], a[i]))
    right[n - i - 1] = (gcd(right[n - i], a[n - 1 - i]))

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

Solution (Python):
from fractions import gcd
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 = 1
for i in range(1, N+1):
  ans = max(ans, gcd(L[i-1], R[i+1]))
print(ans)

Solution (Python):
from fractions import gcd
import numpy as np
n=int(input())
data=list(map(int,input().split()))
left=np.zeros(n+1,dtype=np.int)
right=np.zeros(n+1,dtype=np.int)
kotae=1
for i in range(n):
    left[i+1]=gcd(left[i],data[i])
    right[n-i-1]=gcd(right[n-i],data[n-i-1])
for j in range(n):
    num=gcd(left[j],right[j+1])
    kotae=max(num,kotae)
print(kotae)

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

n = int(input())
a = list(map(int, input().split()))
l = [a[0]] * n
r = [a[n-1]] * n
for i in range(1, n):
    l[i] = gcd(l[i-1], a[i-1])
for i in range(n-2, -1, -1):
    r[i] = gcd(r[i+1], a[i+1])
l[0] = r[0]
r[n-1] = l[n-1]
ans = 0
for i in range(n):
    ans = max(ans, gcd(l[i], r[i]))
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])
    r[n-i-1] = gcd(r[n-i],a[n-i-1])

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

Solution (Python):
from fractions import gcd

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

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

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