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

Solution (Python):
import math

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

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

M = A[-1]
P = [1,M]
for k in range(2,math.ceil(math.sqrt(M))+1):
    if M % k == 0:
        P.append(k)
        P.append(M//k)
M = A[-2]
P.append(M)
for k in range(2,math.ceil(math.sqrt(M))+1):
    if M % k == 0:
        P.append(k)
        P.append(M//k)
P = set(list(P))
ans = 1
for p in P:
    t = 0
    for k in range(N):
        if A[k]%p != 0:
            t += 1
        if t == 2:
            break
    if t <= 1:
        ans = max(ans,p)

print(ans)

Solution (Python):
n = int(input())
a = [int(i) for i in input().split(" ")]
f = [0] * n
r = [0] * n

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

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

m = max(f[n - 2], r[n - 2])
for i in range(0, n - 2):
    g = gcd(f[i], r[n - i - 3])
    if g > m:
        m = g

print(m)

Solution (Python):

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time
sys.setrecursionlimit(10**7)


N = int(input())
A = list(map(int,input().split()))
cumulativeGcdLeft = [A[0]]
cumulativeGcdRight = [A[N-1]]
for i in range(N-1):
    cumulativeGcdLeft.append(fractions.gcd(A[i+1],cumulativeGcdLeft[i]))
    cumulativeGcdRight.append(fractions.gcd(A[N-1-i-1],cumulativeGcdRight[i]))
ans = 1


for i in range(N):
    if i == 0:
        candidate = cumulativeGcdRight[N-2]
    elif i == N-1:
        candidate = cumulativeGcdLeft[N-2]
    else:
        left = cumulativeGcdLeft[i-1]
        right = cumulativeGcdRight[N-i-2]
        candidate = fractions.gcd(left,right)
        
    ans = max(ans,candidate)
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline

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



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


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


def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass 


res = gcdlist(a[1::])


p = sorted(divisor(a[0]))
for i in range(len(p)-1,-1,-1):
    if p[i]<=res:
        break
    cnt = 1
    for j in range(1,n):
        if a[j]%p[i]==0:
            cnt += 1
    if cnt >= n-1:
        res = p[i]
        break
print(res)

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

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

GCD=[]
GCD_INV=[]


x=A[0]
for a in A:
    x=gcd(x,a)
    GCD.append(x)

x=A[-1]
for a in A[::-1]:
    x=gcd(x,a)
    GCD_INV.append(x)

GCD_INV=GCD_INV[::-1]
    
ANS=max(GCD[-2],GCD_INV[1])

for i in range(1,N-1):
    ANS=max(ANS,gcd(GCD[i-1],GCD_INV[i+1]))

print(ANS)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 II(): return int(sys.stdin.readline())
def SI(): return input()
from fractions import gcd

def main():
    N = II()
    A = LI()
    G1 = [A[0]]
    for a in A:
        G1.append(gcd(G1[-1], a))
    G2 = [A[-1]]
    for a in A[::-1]:
        G2.append(gcd(G2[-1], a))
    G2 = G2[::-1]
    G1[0] = A[-1]
    G2[-1] = A[0]
    ans = 1
    for g1, g2 in zip(G1, G2[1:]):
        ans = max(ans, gcd(g1, g2))
    return ans

print(main())

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

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

    if N==2:
        print(max(a))
        return 

    l = [-1] * N
    r = [-1] * N

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

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

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

    
    

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


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
 
def gcd(a, b):
  if b > a:
    a, b = b, a
  r = a % b
  if r == 0:
    return b
  return gcd(b, r)

from_left = [1] * N
from_left[0] = A[0]
from_right = [1] * N
from_right[N-1] = A[N-1]

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



res = 0
for i in range(N):
  if i == 0:
    res = max(res, from_right[1])
  elif i == N-1:
    res = max(res, from_left[N-2])
  else:
	  res = max(res, gcd(from_left[i-1], from_right[i+1]))

print(res)

Solution (Python):
import fractions

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

X=[A[0]]
Y=[A[-1]]


a=A[0]
for i in range(1,n):
    a=fractions.gcd(A[i],a)
    X.append(a)
b=A[-1]
for i in range(1,n):
    b=fractions.gcd(A[-i-1],b)
    Y.append(b)
    
    
M=[X[-1],Y[-1],X[-2],Y[-2]]
for i in range(1,n-1):
    m=fractions.gcd(X[i-1],Y[-i-2])
    M.append(m)
print(max(M))

Solution (Python):
from fractions import gcd

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

if n == 1:
    ans = 1000000000
elif n == 2:
    ans = max(a)
else:
    l = [a[0]]
    for i in range(1, n):
        l.append(gcd(l[-1], a[i]))
    r = [a[-1]]
    for i in range(n - 1, -1, -1):
        r.append(gcd(r[-1], a[i]))
    r = list(reversed(r))
    ans = max(l[-2], r[1])
    for i in range(1, n - 1):
        ans = max(ans, gcd(l[i - 1], r[i + 1]))
print(ans)

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

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

gcd_from_left = [0]*N 
gcd_from_right = [0]*N

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

ans = 0

for a,b in zip(gcd_from_left, gcd_from_right):
  x = gcd(a,b)
  if ans < x:
    ans = x
    
print(ans)

Solution (Python):
from fractions import gcd
N, *A = map(int, open(0).read().split())

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

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, 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 pf(s): return print(s, flush=True)

class Prime():
    def __init__(self, n):
        self.M = m = int(math.sqrt(n)) + 10
        self.A = a = [True] * m
        a[0] = a[1] = False
        self.T = t = []
        for i in range(2, int(math.sqrt(m)) + 1):
            if not a[i]:
                continue
            t.append(i)
            for j in range(i*i,m,i):
                a[j] = False

    def is_prime(self, n):
        return self.A[n]

    def division(self, n):
        d = collections.defaultdict(int)
        for c in self.T:
            while n % c == 0:
                d[c] += 1
                n //= c
            if n < 2:
                break
        if n > 1:
            d[n] += 1
        return d.items()

    def sowa(self, n):
        r = 1
        for k,v in self.division(n):
            t = 1
            for i in range(1,v+1):
                t += math.pow(k, i)
            r *= t
        return r


def main():
    n = I()
    a = sorted(LI())
    pr = Prime(10**9)
    p = collections.defaultdict(int)

    for b in a:
        r = [1]
        for k, v in pr.division(b):
            for c in r[:]:
                for i in range(1,v+1):
                    r.append(c*(k**i))
        for k in r:
            p[k] += 1
    r = 1
    for k,v in p.items():
        if v >= n-1 and r < k:
            r = k

    return r


print(main())

Solution (Python):
from fractions import gcd

def input_ints():
    return list(map(int, input().split()))

def main():
    n = int(input())
    a = input_ints()
    x = [a[0]]
    y = [a[-1]]
    for i in range(n-1):
        x.append(gcd(x[-1], a[i + 1]))
        y.append(gcd(y[-1], a[n - i - 2]))
    ans = max(x[-2],y[-2])
    for i in range(1, n-1):
        ans = max(ans,gcd(x[i-1],y[-i-2]))
    print(ans)
    

if __name__ == '__main__':
    main()

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

def solve():
    N = int(input())
    A = list(map(int,input().split()))
    gcd1 = [0] * N  
    gcd2 = [0] * N  
    gcd1[0] = A[0]
    for i in range(1,N):
        gcd1[i] = gcd(gcd1[i-1],A[i])
    gcd2[N-1] = A[N-1]
    for i in range(N-2,-1,-1):
        gcd2[i] = gcd(gcd2[i+1],A[i])

    ans = 0
    ans = max(ans, gcd2[1])
    ans = max(ans, gcd1[N-2])
    for i in range(1,N-1):
        ans = max(ans, gcd(gcd1[i-1], gcd2[i+1]))
    return ans

print(solve())

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

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

mae = [a[0]]

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



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


ans = usi[1]
for i in range(1,n-1):
    ans = max(ans, gcd(mae[i-1],usi[i+1]))

ans = max(ans, mae[-2])

print(ans)

Solution (Python):

from __future__ import division, print_function

import os
import sys
from fractions import gcd
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    _str = str
    str = lambda x=b"": x if type(x) is bytes else _str(x).encode()


def main():
    n = int(input())
    a = sorted(readlist())

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

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

    res = 0
    for i in range(n):
        res = max(res, gcd(gcd_arr[i], gcd_arr_rev[i + 1]))
    print(res)




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._buffer = BytesIO()
        self._fd = file.fileno()
        self._writable = "x" in file.mode or "r" not in file.mode
        self.write = self._buffer.write if self._writable else None

    def read(self):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()

    def flush(self):
        if self._writable:
            os.write(self._fd, self._buffer.getvalue())
            self._buffer.truncate(0), self._buffer.seek(0)


class ostream:
    def __lshift__(self, a):
        if a is endl:
            sys.stdout.write(b"\n")
            sys.stdout.flush()
        else:
            sys.stdout.write(str(a))
        return self


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", b" "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", b"\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
cout, endl = ostream(), object()

readline = sys.stdin.readline
readlist = lambda var=int: [var(n) for n in readline().split()]
input = lambda: readline().rstrip(b"\r\n")



if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
import fractions

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    GCDbefore = {}
    GCDafter = {}
    GCDbefore[-1] = 0
    for i in range(N):
        GCDbefore[i] = fractions.gcd(GCDbefore[i-1], A[i])
    GCDafter[N] = 0
    for i in range(N):
        GCDafter[N-1-i] = fractions.gcd(GCDafter[N-i], A[N-1-i])
    ans = 0
    for i in range (N):
        ans = max(ans, fractions.gcd(GCDbefore[i-1], GCDafter[i+1]))
    print(ans)

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


@functools.lru_cache(maxsize=None)
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a


max_gcd = [[0]*n for i in range(3)]
max_gcd[0][0] = a[0]
max_gcd[0][1] = gcd(a[0], a[1])
max_gcd[1][1] = a[0]
max_gcd[2][1] = a[1]

for i in range(2, n):
    max_gcd[0][i] = gcd(max_gcd[0][i-1], a[i])
    max_gcd[1][i] = max(max_gcd[0][i-1], gcd(max_gcd[1][i-1], a[i]))
    max_gcd[2][i] = max(max_gcd[0][i-1], gcd(max_gcd[2][i-1], a[i]))

print(max(max_gcd[1][n-1],max_gcd[2][n-1]))

Solution (Python):
from fractions import gcd

n = int(input())
aaa = list(map(int, input().split()))
p = aaa[0]
f = [p]
for a in aaa[1:-1]:
    p = gcd(p, a)
    f.append(p)
aaa.reverse()
p = aaa[0]
b = [p]
for a in aaa[1:-1]:
    p = gcd(p, a)
    b.append(p)
b.reverse()

f = [b[0]] + f
b = b + [f[-1]]

print(max(gcd(p, q) for p, q in zip(f, b)))

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


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

prefix_gcd = []

prefix_gcd.append(nums[0])

for i in nums[1:]:
    prefix_gcd.append(gcd(i,prefix_gcd[-1]))

postfix_gcd = []
postfix_gcd.append(nums[-1])

for j in range(n-2,-1,-1):
    postfix_gcd.append(gcd(nums[j],postfix_gcd[-1]))

postfix_gcd = postfix_gcd[::-1]

ans = 1

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

Solution (Python):
from fractions import gcd

n = int(raw_input())
a = list(map(int, raw_input().split()))
p = list(a)
s = list(a)
for i in range(1, n):
    p[i] = gcd(p[i - 1], p[i])
for i in range(n - 2, -1, -1):
    s[i] = gcd(s[i], s[i + 1])

ans = max(p[-2], s[1])
if n > 2:
    ans = max(ans, max(gcd(p[i - 1], s[i + 1]) for i in range(1, n - 1)))

print(ans)

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

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

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

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

from fractions import gcd
from functools import reduce

ans = reduce(gcd, A[1:]) 
ans = max(ans, reduce(gcd, A[:-1]))
stock = [A[0]] * N
revS  = [A[-1]] * N
for i in range(1, N):
    stock[i] = gcd(stock[i-1], A[i])

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

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

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

Solution (Python):
from fractions import gcd

read_ints = lambda : map(int, raw_input().strip().split())

n = input()
a = read_ints()

pre = [0] * (n + 1)
for i in xrange(1, n + 1):
    pre[i] = gcd(pre[i - 1], a[i - 1])

suf = [0] * (n + 1)
suf[n - 1] = a[n - 1]
for i in xrange(n - 2, -1, -1):
    suf[i] = gcd(suf[i + 1], a[i])

ans = pre[n]
for i in xrange(n):
    g1 = pre[i]
    g2 = suf[i + 1]
    g = gcd(g1, g2)
    ans = max(ans, g)

print ans

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

N=int(input())
A=[int(i) for i in input().split()]
X=[0 for i in range(N)]
Y=[0 for i in range(N)]
for i in range(1,N):
    X[i]=gcd(X[i-1],A[i-1])
for i in range(N-1)[::-1]:
    Y[i]=gcd(Y[i+1],A[i+1])
Z=[gcd(X[i],Y[i]) for i in range(N)]
print(max(Z))