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 gcd(a,b):
    if a<b:
        a,b=b,a
    if b==0:
        return a
    else:
        return gcd(b,a%b)
n=int(input())
A=list(map(int,input().split()))
F=[0]*n
B=[0]*n
F[0]=A[0]
B[-1]=A[-1]
for i in range(1, n):
    F[i]=gcd(F[i-1],A[i])
    B[-i]=gcd(B[-(i-1)],A[-i])
ans=[0]*n
ans[0]=B[1]
ans[-1]=F[-2]
for i in range(1,n-1):
    ans[i]=gcd(F[i-1],B[i+1])
print(max(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):
def gcd(x,y):
    if y == 0:
        return x
    else:
        return gcd(y,x%y)

n = int(input())
a = [int(i) for i in input().split()]
ra = list(reversed(a))
ans = 0
left = [0]*(n+1)
right = [0]*(n+1)

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

right = list(reversed(right))

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

print(ans)

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

print(ans)

Solution (Python):
N = int(input())
l = list(map(int, input().split()))
l_gcd = [None] * N
l_gcd[0] = l[0]


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


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

r_gcd = [None] * N
r_gcd[-1] = l[-1]

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

max_gcd = max(l_gcd[-2], r_gcd[1])

for i in range(1, N-1):
    max_gcd = max(max_gcd, gcd(l_gcd[i-1], r_gcd[i+1]))

print(max_gcd)

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):
def gcd(x,y):
    while y>0:
        x,y = y,x%y
    return x

N = int(input())
A = sorted(list(map(int,input().split())))
amin = A[0]
ind = 0
for i in range(1,N):
    a = gcd(amin,A[i])
    if a<amin:
        ind = i
        amin = a
a0 = A[1]
for i in range(2,N):
    a0 = gcd(a0,A[i])
a1 = A[0]
for i in range(2,N):
    a1 = gcd(a1,A[i])
a = A[0]
for i in range(1,N):
    if i != ind:
        a = gcd(a,A[i])
print(max(a0,a1,a))

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])
    j = (N - 1) - i
    R[j] = gcd(R[j + 1], A[j])

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

print(ans)

Solution (Python):
def gcd(a, b):
    if b > a:
        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 = [0 for i in range(N+1)]
for i in range(0,N):
    L[i + 1] = gcd(L[i], A[i])
    
R = [0 for i in range(N+1)]
for i in range(N,0,-1):
    R[i-1] = gcd(R[i],A[i-1]) 

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

print(max(ans))

Solution (Python):
import sys
from math import sqrt
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=list(map(int,input().split()))
    divisor=set()
    for x in range(1,int(sqrt(A[0]))+1):
        if A[0]%x==0:
            divisor.add(x)
            divisor.add(A[0]//x)
    for x in range(1,int(sqrt(A[1]))+1):
        if A[1]%x==0:
            divisor.add(x)
            divisor.add(A[1]//x)
    
    def solve(mid):
        f=False
        for x in A:
            if x%mid:
                if f:
                    return False
                else:
                    f=True
        return True
    
    ans=0
    for d in divisor:
        if solve(d):
            ans=max(ans,d)
    print(ans)
    

if __name__ == '__main__':
    main()

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

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-i-1] = gcd(R[N-i], A[N-i-1])
    
M = []
for i in range(N):
    M.append(gcd(L[i],R[i+1]))

print(max(M))

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


def segfunc(x,y):
    return math.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


"""
最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
　　和のセグ木 → 0　(上の単位元の説明を参照)
　　積のセグ木 → 1　(上の単位元の説明を参照)
　　gcdのセグ木 → 0　(gcdを更新しない値は0)
"""
ide_ele = 0


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

init(lst1)
ans = 0
for i in range(n):
    
    ans = max(ans,math.gcd(query(0,i),query(i+1,n)))
print(ans)

Solution (Python):
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a
n=int(input())
A=list(map(int,input().split()))
A.append(0)
A.insert(0,0)
B=[0]
C=[0]
for i in range(n+1):
  B.append(gcd(B[-1],A[i+1]))
  C.append(gcd(C[-1],A[n-i]))
ans=1
for i in range(n):
  c=gcd(B[i],C[n-i-1])
  if c>ans:
    ans=c
print(ans)

Solution (Python):

import math
import heapq
import bisect
import numpy as np


def gcd(A,B):
    if B>A:
        A,B = B,A

    if(A%B==0):
        return B
    else:
        return gcd(B,A%B)

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

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

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

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

print(ans)

Solution (Python):
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
b,c = [], []
bb,cc = a[0], a[-1]

for i in range(n):
  bb, cc = gcd(bb, a[i]), gcd(cc, a[-i-1])
  b.append(bb)
  c.append(cc)

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

Solution (Python):
import fractions
import functools


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


l_gcd = [0]
l_append = l_gcd.append

r_gcd = []
r_append = r_gcd.append

for i, a_i in enumerate(a):
    if i == 0:
        l_append(a_i)
    else:
        l_append(fractions.gcd(a_i, l_gcd[i]))

for i, a_i in enumerate(reversed(a)):
    if i == 0:
        r_append(a_i)
    else:
        r_append(fractions.gcd(a_i, r_gcd[i-1]))
r_gcd.reverse()
r_append(0)

m = []
m_append = m.append
for i in range(n):
    m_append(fractions.gcd(l_gcd[i], r_gcd[i+1]))
ans = max(m)
print(ans)

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

import fractions
if N==2:
  print(max(A))
else:
  L=[0]*(N)
  R=[0]*(N)
  L[0]=A[0]
  R[N-1]=A[N-1]
  for i in range(1,N):
    L[i]=fractions.gcd(L[i-1],A[i])
  for i in range(1,N):
    R[N-1-i]=fractions.gcd(R[N-i],A[N-1-i])
  ans=0
  for i in range(1,N-1):
    x=fractions.gcd(L[i-1],R[i+1])
    ans=max(ans,x)

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

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

import fractions
if N==2:
  print(max(A))
else:
  L=[0]*(N)
  R=[0]*(N)
  L[0]=A[0]
  R[N-1]=A[N-1]
  for i in range(1,N):
    L[i]=fractions.gcd(L[i-1],A[i])
  for i in range(N-1,0,-1):
    R[i-1]=fractions.gcd(R[i],A[i-1])
  ans=0
  for i in range(1,N-1):
    x=fractions.gcd(L[i-1],R[i+1])
    ans=max(ans,x)

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

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

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

u = [a[n-1]]
for i in range(n-2,-1,-1):
    u.append(gcd(u[-1],a[i]))



ans = max(u[-2],s[-2])
for i in range(1,n-1):
    
    now = gcd(s[i-1],u[-2-i])
    ans = max(ans,now)
print(ans)

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

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

ans = 0

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

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

print(ans)

Solution (Python):
def gcd(x, y):
    while y != 0:
        x, y = y, x%y
    return x

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

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

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

print(ans)

Solution (Python):
from fractions import gcd
from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
B = list(accumulate(A, gcd))
C = list(accumulate(A[::-1], gcd))[::-1]
C = C[2:] + C[:2]
B[-1] = C[-1]
C[-2] = B[-2]
print(max(map(gcd, B, C)))

Solution (Python):

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

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


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 = 0
for i in range(N):
    ans = max(ans, fractions.gcd(query(0, i), query(i+1, N)))
print(ans)

Solution (Python):

from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
l1, l2 = [0] * N, [0] * N

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

for i in range(N-1)[::-1]:
    l2[i] = gcd(l2[i+1], A[i+1])
ll = []
ans = 0
for i in range(N):
    ans = max(ans, gcd(l1[i], l2[i]))
print(ans)

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

n=int(input())
a=list(map(int,input().split()))
a.append(a[-1])

ans=[]

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

ans=[]
for i in range(n):
    ans.append(gcd(gcd_left[i],gcd_right[i]))

print(max(ans))

Solution (Python):

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

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

ans_gcd = -1


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


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


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


if N > 2:
    ans_gcd = max(ans_gcd, gcd(A[-2], L[N-3]), gcd(A[1], R[2]))
else:
    ans_gcd = max(A)

print(ans_gcd)

Solution (Python):
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

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


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



lefts = list(itertools.accumulate(A, gcd))
rights = list(itertools.accumulate(A[::-1], gcd))[::-1]

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

Solution (Python):

import sys
input = sys.stdin.readline

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

from fractions import gcd

l_gcd = [0 for _ in range(n)]
r_gcd = [0 for _ in range(n)]

for i in range(n):
    l_gcd[i]=gcd(l_gcd[i-1],a[i])
for i in range(n-1,-1,-1):
    if i == n-1:
        r_gcd[i]=a[i]
    else:
        r_gcd[i]=gcd(r_gcd[i+1],a[i])
ret = 1

for i in range(n):
    if i==0:
        ret = max(ret,gcd(0,r_gcd[i+1]))
    elif i==n-1:
        ret = max(ret,gcd(l_gcd[i-1],0))
    else:
        ret = max(ret,gcd(l_gcd[i-1],r_gcd[i+1]))
print(ret)

Solution (Python):

n=int(input())
a=[int(i) for i in input().split()]
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
l=[1]*n
r=[1]*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-i-1])
if n>=3:
    ans = max(l[-2],r[-2],max(gcd(l[i-1],r[n-i-2]) for i in range(1,n-1)))
    print(ans)
else:
    print(max(a))

Solution (Python):
import math
from itertools import accumulate
from fractions import gcd

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

L = [0]+list(accumulate(a, gcd))
R = list(accumulate(reversed(a), gcd))[::-1]+[0]


ans = 0

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

if n == 2:
    print(max(a))
else:
    print(ans)

Solution (Python):
from fractions import gcd

n = int(input())
list_ = list(map(int, input().strip().split()))

gcd_from_left = [0]
gcd_from_right = [0]
for i in range(n):
    gcd_from_left.append(gcd(gcd_from_left[i], list_[i]))
    gcd_from_right.append(gcd(gcd_from_right[i], list_[-(i + 1)]))

gcd_from_left.insert(0, 0)
gcd_from_right.insert(0, 0)
gcd_from_right.reverse()

print(max(gcd(gcd_from_left[i], gcd_from_right[i]) for i in range(n + 2)))

Solution (Python):
from fractions import gcd


def solve():
    N, *A = map(int, open(0).read().split())
    
    ans = 0
    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], A[i])
    for i in range(N-1, -1, -1):
        right[i] = gcd(right[i+1], A[i])
    for i in range(N):
        ans = max(ans, gcd(left[i], right[i+1]))
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def gcd(a,b):
    while b>0:a,b=b,a%b
    return a

def main():
    n=int(input())
    aa=LI()
    gl=[0]*n
    gr=[0]*n
    g=aa[0]
    for i,a in enumerate(aa):
        g=gcd(g,a)
        gl[i]=g
    g=aa[-1]
    for i,a in enumerate(aa[::-1]):
        g=gcd(g,a)
        gr[n-1-i]=g
    ans=max(gl[n-2],gr[1])
    for i in range(1,n-1):
        g=gcd(gl[i-1],gr[i+1])
        if g>ans:ans=g
    print(ans)

main()

Solution (Python):
from fractions import gcd

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

g1 = [0]*N
g2 = [0]*N

g1[0] = a[0]
g2[N-1] = a[N-1]

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

g = [gcd(g1[i], g2[i]) for i in range(N)]
print(max(g))

Solution (Python):

import fractions
N=int(input())
A=list(map(int,input().split()))
GL=[0]*N
GR=[0]*N

GL[0]=A[0]
GR[N-1]=A[N-1]

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

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



G=0
for i in range(1,N-1):
    G=max(fractions.gcd(GL[i-1],GR[i+1]),G)
    
print(max(G,GR[1],GL[N-2]))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    gcd = fractions.gcd
    N = I()
    A = LI()
    left = [1] * N
    right = [1] * N
    left[0] = A[0]
    right[N-1] = A[N-1]
    ans = -1

    for i in range(1, N):
        left[i] = gcd(A[i], left[i-1])
    for j in range(N-2, -1, -1):
        right[j] = gcd(A[j], right[j+1])
    for i in range(N):
        if i-1<0:
            ans = max(ans, right[i+1])
            continue
        if i+1 >= N:
            ans = max(ans, left[i-1])
            continue
        ans = max(ans, gcd(left[i-1], right[i+1]))

    print(ans)

main()


'''

N = int(input())
S = list(input())

ans = 0
s_count = 0
if len(S) == 1:
    print(ans)
elif len(S) == 2:
    if S == ['
        print("1")
    else:
        print("0")
elif len(S) == 3:
    for i in range(len(S)-1):
        if S[i] == '
            ans += 1
    print(ans)
            
else:
    for c in S[:-1]:
        if c=='
            s_count += 1
    for i in range(len(S)-3):
        if S[i:i+4] == ['.','
            S[i:i+4] = ['.','.','.','.']
            
        elif S[i:i+4] == ['.','
            S[i:i+4] = ['.','

        elif S[i:i+4] == ['
            S[i:i+4] = ['

        elif S[i:i+4] == ['
            S[i:i+4] = ['
        else:
            continue
        ans += 1

    print(min(s_count, ans, len(S)-s_count))
print(S)
'''

Solution (Python):
import fractions
N = int(input())
A = list(map(int, input().split()))
B = [0]*N
B[0] = A[0]
for i in range(1, N-1):
    B[i] = fractions.gcd(A[i], B[i-1])

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

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

Solution (Python):



from fractions import gcd
from itertools import accumulate

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

left = list(accumulate(A, gcd))
right = list(accumulate(A[::-1], gcd))[::-1]

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

print(ans)

Solution (Python):
import fractions
N=int(input())
ls=[int(s) for s in input().split()]
gcd_l=[0 for _ in range(N+1)]
gcd_l[0]=ls[0]
gcd_r=[0 for _ in range(N+1)]
gcd_r[N-1]=ls[N-1]
for i in range(N-1):
  gcd_l[i+1]=fractions.gcd(gcd_l[i],ls[i+1])
  gcd_r[N-i-2]=fractions.gcd(gcd_r[N-i-1],ls[N-i-2])
ans=set()
for i in range(N):
  ans.add(fractions.gcd(gcd_l[i-1],gcd_r[i+1]))
print(max(ans))

Solution (Python):
from itertools import accumulate
from fractions import gcd


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

cum_gcd_l = list(accumulate(A, gcd))
cum_gcd_r = list(accumulate(reversed(A), gcd))[::-1]

ans = 0
for i in range(N):
    if i == 0:
        tmp = cum_gcd_r[1]
    elif i == N-1:
        tmp = cum_gcd_l[-2]
    else:
        tmp = gcd(cum_gcd_l[i-1], cum_gcd_r[i+1])
    ans = max(tmp, ans)

print(ans)

Solution (Python):
from itertools import accumulate
from fractions import gcd


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

cum_gcd_l = list(accumulate(A, gcd))
cum_gcd_r = list(accumulate(reversed(A), gcd))

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

print(ans)

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

Solution (Python):


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

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

memo1 = 10**9
memo2 = 10**9

lf = [0 for i in range(n)]
rgt = [0 for i in range(n)]

lf[0] = a[0]
rgt[0] = a[n-1]

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


mx = 0
mx = max(mx,lf[n-2])
mx = max(mx,rgt[n-2])

for i in range(1,n-1):
	mx = max(mx,gcd(lf[i-1],rgt[i*(-1)-2]))

print(mx)

Solution (Python):
import copy
import fractions
N=int(input())
A=list(map(int,input().split()))
ans=[]
L=[0 for i in range(N)]
R=[0 for i in range(N)]
for i in range(N):
  if i != 0:
    L[i]=fractions.gcd(L[i-1],A[i-1])
    R[N-1-i]=fractions.gcd(R[N-i],A[N-i])

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

print(max(ans))

Solution (Python):
from fractions import gcd
def gc(a,b):
  if a==0 or b==0:
    return max(a,b)
  else:
    return gcd(a,b)
n=int(input())
a=list(map(int,input().split()))
a=[0]+a+[0]
lgcd=[0]
rgcd=[0]
for i in range(1,n):
  lgcd.append(gc(a[i],lgcd[-1]))
  rgcd.append(gc(a[-i-1],rgcd[-1]))
GCD=0
for i in range(n):
  GCD=max(GCD,gc(lgcd[i],rgcd[-i-1]))
print(GCD)

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

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

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

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

Solution (Python):

import fractions

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

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

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

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

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

Solution (Python):
from fractions import gcd
def init(init_val,n):
    
    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 segfunc(x,y):
    return gcd(x,y)

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

init(a,N)
res = 0
for i in range(N):
    tmp = gcd(query(0,i),query(i+1,N))
    if tmp >= res:
        res = tmp
print(res)

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

gl=[0]*n
gl[0]=a[0]
gr=[0]*n
gr[-1]=a[-1]
for i in range(1,n):
    gl[i]=gcd(gl[i-1],a[i])
    gr[-i-1]=gcd(gr[-i],a[-i-1])
ans=max(gr[1],gl[-2])
for i in range(1,n-1):
    ans=max(ans,gcd(gl[i-1],gr[i+1]))
print(ans)

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

gl=[0]*n
gl[0]=a[0]
gr=[0]*n
gr[-1]=a[-1]
for i in range(1,n):
    gl[i]=gcd(gl[i-1],a[i])
    gr[-i-1]=gcd(gr[-i],a[-i-1])
ans=0
for i in range(n):
    if i==0:
        ans=gr[1]
    elif i==n-1:
        ans=max(ans,gl[i-1])
    else:
        ans=max(ans,gcd(gl[i-1],gr[i+1]))
print(ans)

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

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



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

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

res = 0
for i in range(1, N+1):
    rm_i = gcd(L[i-1], R[i+1])
    if res < rm_i:
        res = rm_i
print(res)

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

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

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

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

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

print(ans)

Solution (Python):
import fractions as f

N = int(input())
A = [int(i) for i in input().split()]
L = [A[0]]
for i in range(1, N):
    L.append(f.gcd(L[-1], A[i]))
A.reverse()
R = [A[0]]
for i in range(1, N):
    R.append(f.gcd(R[-1], A[i]))
R.reverse()
ans = 0
for i in range(N):
    if i == 0:
        ans = max(ans, R[1])
    elif i == N - 1:
        ans = max(ans, L[N - 2])
    else:
        ans = max(ans, f.gcd(L[i - 1], R[i + 1]))
print(ans)

Solution (Python):


def euclid(a,b):
    a,b=max(a,b),min(a,b)
    if a%b==0:
        return b
    else:
        a,b=b,a%b
        return euclid(a,b)

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

org_A=A[:]

A=A[::-1]
l=[A.pop(-1)]
while A:
    l.append(euclid(l[-1],A.pop(-1)))

A=org_A
r=[A.pop(-1)]
while A:
    r.append(euclid(r[-1],A.pop(-1)))
r=r[::-1]

ans=0

for i in range(N):
    temp=euclid(l[i-1] if i!=0 else r[i+1],r[i+1] if i!=N-1 else l[i-1])
    
    ans=max(ans,temp)

print(ans)

Solution (Python):
import fractions
import functools
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(fractions.gcd(left[i], right[i+1]), ans)

print(ans)

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

    if N == 2:
        if A[0] <= A[1]:
            return print(A[1])
        else:
            return print(A[0])
    

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

    ans = 1
    nonneed_idx = -1
    if gcd(A[0], A[1]) > gcd(A[1], A[2]) and gcd(A[0], A[1]) > gcd(A[0], A[2]):
        ans = gcd(A[0], A[1])
        nonneed_idx = 2
    elif gcd(A[0], A[2]) > gcd(A[1], A[2]) and gcd(A[0], A[2]) > gcd(A[0], A[1]):
        ans = gcd(A[0], A[2])
        nonneed_idx = 1
    else:
        ans = gcd(A[1], A[2])
        nonneed_idx = 0

    for i in range(3, N):
        if gcd(ans, A[nonneed_idx]) < gcd(ans, A[i]):
            ans = gcd(ans, A[i])
        else:
            ans = gcd(ans, A[nonneed_idx])
            nonneed_idx = i
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import fractions


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = list(map(int, readline().split()))
    ls = [[0] * (n + 1) for _ in range(2)]
    for i in range(1, n + 1):
        ls[0][i] = fractions.gcd(ls[0][i-1], a[i-1])
        ls[1][-i-1] = fractions.gcd(ls[1][-i], a[-i])
    mt = 0
    for i in range(n):
        mt = max(mt, fractions.gcd(ls[0][i], ls[1][i+1]))
    print(mt)


if __name__ == '__main__':
    solve()

Solution (Python):
n=int(input())
a=sorted(list(map(int,input().split())))
i=a[1]
while i > 0:
  flg=0
  for j in a:
    if j%i!=0:
      flg+=1
      if flg>1:
        break
  if flg<=1:
    print(i)
    break
  else:
    i-=1

Solution (Python):
n=int(input())
a=sorted(list(map(int,input().split())))
i=a[1]
while i > 0:
  flg=0
  for j in a:
    if j%i!=0:
      flg+=1
      if flg>1:
        break
  if flg<=1:
    print(i)
    break
  else:
    i-=1

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

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

from fractions import gcd
from functools import reduce
import numpy as np

new_gcd = np.frompyfunc(gcd, 2, 1)

a = np.array(a)
left = new_gcd.accumulate(a, dtype=np.object).astype(np.int)
right = new_gcd.accumulate(a[::-1], dtype=np.object).astype(np.int)[::-1]
left = np.append([0], left[:-1])
right = np.append(right[1:], 0)

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