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):
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
n=int(input())
a=list(map(int,input().split()))
def gcd_l(a):
  tmp=a[0]
  for i in range(len(a)):
    tmp=gcd(tmp,a[i])
  return tmp
tmp=gcd_l(a[1:])
p=set()
for i in range(1,int(a[0]**0.5)+1):
  if a[0]%i==0:
    if i>tmp:
      p.add(i)
    if a[0]//i>tmp:
      p.add(a[0]//i)
if len(p)==0:
  print(tmp)
  exit()
p=sorted(list(p),reverse=True)
for x in p:
  b=[not a[i]%x for i in range(n)]
  if sum(b)==n-1:
    print(x)
    exit()
print(tmp)

Solution (Python):
N = int(input())
import fractions

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

gcd_start = [0]
gcd_end = [0]

ans = a[0]
gcd_start.append(ans)
for i in range(1, N-1):
    ans = fractions.gcd(ans, a[i])
    gcd_start.append(ans)

ans = a[-1]
gcd_end.append(ans)
for i in range(-2, -N, -1):
    ans = fractions.gcd(ans, a[i])
    gcd_end.append(ans)

ans_max = 0
for i in range(N):
    ans = fractions.gcd(gcd_end[-i-1], gcd_start[i])
    ans_max = max(ans, ans_max)

print(ans_max)

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

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

for i in range(N):
    gl.append(gcd(gl[-1],A[i]))
    gr.append(gcd(gr[-1],A[-i-1]))
ans = 1
for i in range(N):
    g = gcd(gl[i],gr[-i-2])
    if ans < g:
        ans = g
print(ans)

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

Solution (Python):
import sys
input = sys.stdin.readline
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from fractions import *
def print_ans(N, a_list):
    """Test Case
    >>> print_ans(3, [0, 7, 6, 8, 0])
    2
    >>> print_ans(3, [0, 12, 15, 18, 0])
    6
    >>> print_ans(2, [0, 1000000000, 1000000000,0])
    1000000000
    """
    l_list = [0 for _ in range(N + 2)]
    r_list = [0 for _ in range(N + 2)]
    for i in range(1, N + 1):
        l_list[i] = gcd(l_list[i-1], a_list[i])
    for i in range(N, 0, -1):
            r_list[i] = gcd(r_list[i + 1], a_list[i])
    m_list = [0 for _ in range(N + 1)]
    for i in range(1, N + 1):
        m_list[i] = gcd(l_list[i - 1],r_list[i+ 1])
    print(max(m_list))

if __name__ == '__main__':
    N = int(input().rstrip())
    a_list = [0] + list(map(int, input().rstrip().split())) + [0]
    print_ans(N, a_list)

Solution (Python):
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
if n == 2:
    print(max(a))
    exit()
x = [a[0], gcd(a[0], a[1])]
for i in range(n - 3):
    x.append(gcd(x[i + 1], a[i + 2]))
ans = x[-1]
y = a[-1]
for i in range(1, n - 1):
    z = gcd(y, a[-i])
    ans = max(ans, gcd(x[-i - 1], z))
    y = z
print(max(ans, gcd(y, a[1])))

Solution (Python):
from fractions import gcd


def p_c():
    n = int(input())
    *a, = map(int, input().split())
    L = [0] * n
    R = [0] * n
    for i in range(n - 1):
        L[i] = gcd(L[i - 1], a[i])
        R[n - 1 - i] = gcd(R[(n - i) % n], a[n - 1 - i])
    ans = [gcd(L[i - 1], R[(i + 1) % n]) for i in range(n)]
    print(max(ans))

p_c()

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

L = [0]
R = [0]
gcd_l = a[0]
gcd_r = a[-1]
for i in range(n):
    gcd_l = gcd(a[i],gcd_l)
    L.append(gcd_l)
    gcd_r = gcd(a[n-i-1],gcd_r)
    R.append(gcd_r)




ans = 0

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

print(ans)

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

Solution (Python):

n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(n):
  if i == 0:
    b.append(a[i])
  else:
    big = b[-1]
    sml = a[i]
    while sml != 0:
      big,sml = sml,big%sml
    b.append(big)
c = []
for j in range(n)[::-1]:
  if j == n-1:
    c.append(a[j])
  else:
    big = c[-1]
    sml = a[j]
    while sml != 0:
      big,sml = sml,big%sml
    c.append(big)
c.reverse()
d = []
for i in range(n):
  if i == 0:
    d.append(c[1])
  elif i == n-1:
    d.append(b[n-2])
  else:
    big = b[i-1]
    sml = c[i+1]
    while sml != 0:
      big,sml = sml,big%sml
    d.append(big)



print(max(d))

Solution (Python):
def gcd(x, y):
    if y == 0:
        return x
    while y != 0:
        x, y = y, x % y
    return x
class segment_gcd():
    def __init__(self,A,n,num):
        
        self.ide_ele = 0
        self.seg = [self.ide_ele] * 2 * num
        self.num = num
        
        for i in range(n):
            self.seg[i +num -1] = A[i]
            
        for i in range(num - 2, -1, -1):
            self.seg[i] = gcd(self.seg[2*i +1], self.seg[2*i +2])

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

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

def examC():
    N = I()
    A = LI()
    
    num = 2 ** (N - 1).bit_length()
    Seggcd = segment_gcd(A,N,num)
    ans = -1
    for i in range(N):
        ans = max(ans, gcd(Seggcd.query(0, i), Seggcd.query(i + 1, N)))
    print(ans)


import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()

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

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


B = [0] * (N+1)
R = [0] * (N+1)
for i in range(N):
    B[i+1] = (fractions.gcd(B[i],A[i]))
    
    R[N-i -1] = (fractions.gcd(R[N-i], A[N-1 -i]))
 
ans = 0
for i in range(N):
    ans = max(ans, fractions.gcd(B[i], 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_L=[0]*N
gcd_R=[0]*N
for i in range(1,N):
  gcd_L[i]=gcd(A[i-1],gcd_L[i-1])
  gcd_R[N-1-i]=gcd(A[N-i],gcd_R[N-i])
answer=0
for j,k in zip(gcd_L,gcd_R):
  answer=max(answer,gcd(j,k))
print(answer)

Solution (Python):
from fractions import*

class SEGMENTTREE():
    def __init__(self,lis,func,ele):
        self.monoidfunc=func
        self.identityelement=ele  
        self.n=len(lis)  
        self.node=[ele]*self.n+lis
        for i in range(self.n-1,0,-1):  
            self.node[i]=self.monoidfunc(self.node[i<<1],self.node[i<<1|1])
 
    def update(self, point, value):  
        m=self.monoidfunc
        point+=self.n
        self.node[point]=value
        while point>1:
            self.node[point>>1]=m(self.node[point], self.node[point^1])
            point>>=1
 
    def get(self, l, r):  
        m,e=self.monoidfunc,self.identityelement
        res=e
        l+=self.n
        r+=self.n
        while l<r:
            if l&1:
                res=m(res,self.node[l])
                l+=1
            if r&1:
                r-=1
                res=m(res,self.node[r])
            l>>=1
            r>>=1
        return res

n,*a=map(int,open(0).read().split())

segtree = SEGMENTTREE(a, gcd, 0)
 
ans = 1
for i, a in enumerate(a):
    segtree.update(i,0)
    ans = max(ans,segtree.get(0,n))

    segtree.update(i,a)
print(ans)

Solution (Python):
from itertools import*;from fractions import*;u=accumulate;g=gcd;n,a=open(0);*a,=map(int,a.split());a=[0]+a+[0];print(max(starmap(g,zip(u(a,g),list(u(a[:1:-1],g))[::-1]))))

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
def gcd(x,y):
  while y>0:
    x,y=y,x%y
  return x
b=[a[0]]
for i in range(1,n-1):
  b.append(gcd(b[-1],a[i]))
c=[a[n-1]]
for i in range(1,n-1):
  c.append(gcd(c[-1],a[n-1-i]))
q=b[n-2]
for i in range(0,n-2):
  p=gcd(b[i],c[n-3-i])
  q=max(p,q)
print(max(q,c[n-2]))

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines












from fractions import gcd














def main():
	N=int(input())
	A=list(map(int,input().split()))
	
	L=[0]*N
	R=[0]*N
	M=[0]*N
	
	L[0] = A[0]
	R[N-1]=A[N-1]
	
	for i in range(1,N):
		L[i]=gcd(A[i],L[i-1])
	for i in range(N-2,0,-1):
		R[i]=gcd(A[i],R[i+1])
	
	M[0]=R[1]
	M[N-1]=L[N-2]
	
	for i in range(1,N-1):
		M[i]=gcd(L[i-1],R[i+1])
	
	print(max(M))
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
if __name__ == '__main__':
	main()

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines












from fractions import gcd














def main():
	N=int(input())
	A=list(map(int,input().split()))
	
	L=[0]*N
	R=[0]*N
	M=[0]*N
	
	L[0] = A[0]
	R[N-1]=A[N-1]
	
	for i in range(1,N):
		L[i]=gcd(A[i],L[i-1])
	for i in range(N-2,0,-1):
		R[i]=gcd(A[i],R[i+1])
	
	M[0]=R[1]
	M[N-1]=L[N-2]
	
	for i in range(1,N-1):
		M[i]=gcd(L[i-1],R[i+1])
	
	print(max(M))
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
if __name__ == '__main__':
	main()

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
def GCM(a, b):
  if a < b:
    a += b
    b = a-b
    a -= b
  if a % b == 0:
    return b
  else:
    return GCM(b, a%b)

N = int(input())
A = list(map(int, input().split()))
l2r =[]
r2l = []
g = A[0]
for a in A:
  g = GCM(g, a)
  l2r.append(g)
g = A[-1]
for a in reversed(A):
  g = GCM(g, a)
  r2l.append(g)
r2l = list(reversed(r2l))
ans = r2l[1]
for i in range(1, N-1):
  ans = max(ans, GCM(l2r[i-1], r2l[i+1]))
ans = max(ans, l2r[N-2])
print(ans)

Solution (Python):
from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
m = [0]*n

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

ans = 1
for a, b in zip(l, r):
    x = gcd(a, b)
    if ans < x:
        ans = x

print(ans)

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

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

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

for i in range(1, N):
    L[i] = gca(A[i], L[i - 1])
for i in range(N - 2, -1, -1):
    R[i] = gca(A[i], R[i + 1])
maxg = 0
for i in range(1, N - 1):
    maxg = max(maxg, gca(L[i - 1], R[i + 1]))

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

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

if n == 2:
    print(max(a))
else:
    l = [0 for i in range(n)]
    r = [0 for i in range(n)]
    
    def gcd(x,y):
        while y != 0:
            x, y = y, x%y
    
        return(x)
    
    for i in range(1,n):
        l[i] = gcd(l[i-1],a[i-1])
        r[n-i-1] = gcd(r[n-i],a[n-i])
  
  
    ans = 0
    for i in range(n):
        if l[i] == -1:
            ans = max(ans,r[i])
        elif r[i] == -1:
            ans = max(ans,l[i])
        else:
            ans = max(ans,gcd(l[i],r[i]))
    print(ans)

Solution (Python):

import sys
from fractions import gcd
input = sys.stdin.readline
 
class DisjointSparseTable:
    def __init__(self, a):
        
        self.e = 0
        self.n = len(a)
        self.level = (len(a) - 1).bit_length()
        self.size = 2**self.level
        self.table = [[self.e] * self.size for _ in range(self.level)]
        
        for i, item in enumerate(a):
            self.table[-1][i] = item
        self.build()
 
    def build(self):
        for i in range(1, self.level):
            step = 2**i
            lv = self.level - 1 - i
            for mid in range(step, self.n + step, step*2):
                if mid - step >= self.n:
                    continue
                
                val = self.e 
                for j in range(step):
                    val = gcd(self.table[-1][mid + j], val)
                    self.table[lv][mid + j] = val
                
                val = self.e
                for j in range(step):
                    val = gcd(self.table[-1][mid - 1 - j], val)
                    self.table[lv][mid - 1 - j] = val
 
    
    def query(self, l, r):
        if l == r:
            return self.e
        elif l == r - 1:
            return self.table[-1][l]
        lv = self.level - (l ^ r-1).bit_length()
        return gcd(self.table[lv][l], self.table[lv][r-1])
 
 
if __name__ == "__main__":
    n = int(input())
    a = [int(item) for item in input().split()]
    DST = DisjointSparseTable(a)
    ans = 0
    for i in range(0, n):
        ans = max(ans, gcd(DST.query(0, i), DST.query(i+1, n)))
    print(ans)

Solution (Python):

import sys
from fractions import gcd
input = sys.stdin.readline
 
class DisjointSparseTable:
    def __init__(self, a):
        
        self.e = 0
        self.n = len(a)
        self.level = (len(a) - 1).bit_length()
        self.size = 2**self.level
        self.table = [[self.e] * self.size for _ in range(self.level)]
        
        for i, item in enumerate(a):
            self.table[-1][i] = item
        self.build()
 
    def build(self):
        for i in range(1, self.level):
            step = 2**i
            lv = self.level - 1 - i
            for mid in range(step, self.size, step*2):
                if mid - step >= self.n:
                    continue
                
                val = self.e 
                for j in range(step):
                    val = gcd(self.table[-1][mid + j], val)
                    self.table[lv][mid + j] = val
                
                val = self.e
                for j in range(step):
                    val = gcd(self.table[-1][mid - 1 - j], val)
                    self.table[lv][mid - 1 - j] = val
 
    
    def query(self, l, r):
        if l == r:
            return self.e
        elif l == r - 1:
            return self.table[-1][l]
        lv = self.level - (l ^ r-1).bit_length()
        return gcd(self.table[lv][l], self.table[lv][r-1])
 
 
if __name__ == "__main__":
    n = int(input())
    a = [int(item) for item in input().split()]
    DST = DisjointSparseTable(a)
    ans = 0
    for i in range(0, n):
        ans = max(ans, gcd(DST.query(0, i), DST.query(i+1, n)))
    print(ans)

Solution (Python):

import sys
from fractions import gcd
input = sys.stdin.readline

class DisjointSparseTable:
    def __init__(self, a):
        
        self.e = 0
        self.level = (len(a) - 1).bit_length()
        self.size = 2**self.level
        self.table = [[self.e] * self.size for _ in range(self.level)]
        
        for i, item in enumerate(a):
            self.table[-1][i] = item
        self.build()

    def build(self):
        for i in range(1, self.level):
            step = 2**i
            lv = self.level - 1 - i
            for mid in range(step, self.size, step*2):
                
                val = self.e 
                for j in range(step):
                    val = gcd(self.table[-1][mid + j], val)
                    self.table[lv][mid + j] = val
                
                val = self.e
                for j in range(step):
                    val = gcd(self.table[-1][mid - 1 - j], val)
                    self.table[lv][mid - 1 - j] = val

    
    def query(self, l, r):
        if l == r:
            return self.e
        elif l == r - 1:
            return self.table[-1][l]
        lv = self.level - (l ^ r-1).bit_length()
        return gcd(self.table[lv][l], self.table[lv][r-1])

 
if __name__ == "__main__":
    n = int(input())
    a = [int(item) for item in input().split()]
    DST = DisjointSparseTable(a)
    ans = 0
    for i in range(0, n):
        ans = max(ans, gcd(DST.query(0, i), DST.query(i+1, n)))
    print(ans)

Solution (Python):

import sys
from fractions import gcd
input = sys.stdin.readline


class RgcdQ:
    def __init__(self, a):
        self.n = len(a)
        self.size = 2**(self.n - 1).bit_length()
        self.data = [0] * (2*self.size-1)
        self.initialize(a)

    
    def initialize(self, a):
        for i in range(self.n):
            self.data[self.size + i - 1] = a[i]
        for i in range(self.size-2, -1, -1):
            self.data[i] = gcd(self.data[i*2 + 1], self.data[i*2 + 2])

    
    def update(self, k, x):
        k += self.size - 1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = gcd(self.data[2*k+1], self.data[2*k+2])

    
    def query(self, l, r):
        L = l + self.size; R = r + self.size
        s = 0
        while L < R:
            if R & 1:
                R -= 1
                s = gcd(s, self.data[R-1])
            if L & 1:
                s = gcd(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
 
if __name__ == "__main__":
    n = int(input())
    a = [int(item) for item in input().split()]
    ST = RgcdQ(a)
    ans = 0
    for i in range(0, n):
        ans = max(ans, gcd(ST.query(0, i), ST.query(i+1, n)))
    print(ans)

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

class DisjointSparseTable:
    def __init__(self, a):
        self.level = (len(a) - 1).bit_length()
        self.size = 2**self.level
        self.table = [[0] * self.size for _ in range(self.level)]
        
        for i, item in enumerate(a): 
            self.table[-1][i] = item
        self.build()

    def build(self):
        for lv in range(1, self.level):
            step = 2**lv
            level = self.level - 1 - lv
            for mid in range(step, self.size, step*2):
                
                val = 0
                for i in range(step):
                    val = gcd(self.table[-1][mid + i], val)
                    self.table[level][mid + i] = val
                
                val = 0
                for i in range(step):
                    val = gcd(self.table[-1][mid - 1 - i], val)
                    self.table[level][mid - 1 - i] = val
    
    
    def query(self, l, r):
        if l == r:
            return 0
        elif l == r - 1:
            return self.table[-1][l]
        level = self.level - (l ^ r-1).bit_length()
        return gcd(self.table[level][l], self.table[level][r-1])

if __name__ == "__main__":
    n = int(input())
    a = [int(item) for item in input().split()]
    DST = DisjointSparseTable(a)
    ans = 0
    for i in range(0, n):
        ans = max(ans, gcd(DST.query(0, i), DST.query(i+1, n)))
    print(ans)

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

class DisjointSparseTable:
    def __init__(self, a):
        self.level = (len(a) - 1).bit_length()
        self.size = 2**self.level
        self.table = [[0] * self.size for _ in range(self.level)]
        
        for i, item in enumerate(a): 
            self.table[-1][i] = item
        self.build()

    def build(self):
        for lv in range(1, self.level):
            step = 2**lv
            level = self.level - 1 - lv
            for mid in range(step, self.size, step*2):
                
                val = 0
                for i in range(step):
                    val = gcd(self.table[-1][mid + i], val)
                    self.table[level][mid + i] = val
                
                val = 0
                for i in range(step):
                    val = gcd(self.table[-1][mid - 1 - i], val)
                    self.table[level][mid - 1 - i] = val
    
    
    def query(self, l, r):
        if l == r:
            return 0
        elif l == r - 1:
            return self.table[-1][l]
        level = self.level - (l ^ r-1).bit_length()
        return gcd(self.table[level][l], self.table[level][r-1])

if __name__ == "__main__":
    n = int(input())
    a = [int(item) for item in input().split()]
    DST = DisjointSparseTable(a)
    ans = 0
    for i in range(0, n):
        ans = max(ans, gcd(DST.query(0, i), DST.query(i+1, n)))
    print(ans)

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

N=int(readline())
A=list(map(int,readline().split()))
B=A[::-1]

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

gcd_l=[0]*N
gcd_r=[0]*N

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



gcd_l[-1]=0
gcd_r[0]=0

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

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 for _ in range(N)]
R = [0 for _ in range(N)]

L[0] = A[0]
R[N-1] = A[N-1]

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

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

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

print(ans)

Solution (Python):
import math

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

def division_enumeration(num):
	ans = []
	d = math.floor(float(num)**(1/2))
	for i in range(1,d+1):
		if num % i == 0:
			ans.append(i)
			ans.append(num//i)

	return ans

trgs = sorted(set(division_enumeration(A[0]) + division_enumeration(A[1])), reverse = True)

for trg in trgs:
	cnt = 0
	cond = True
	for i in range(N):
		if A[i] % trg != 0:
			cnt += 1
			if cnt > 1:
				cond = False
				break
	if not cond:
		continue
	
	ans = trg
	break

print(ans)

Solution (Python):
import math

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

def division_enumeration(num):
	ans = []
	d = math.floor(float(num)**(1/2))
	for i in range(1,d+1):
		if num % i == 0:
			ans.append(i)
			ans.append(num//i)

	return ans

trgs = sorted(set(division_enumeration(A[0]) + division_enumeration(A[1])), reverse = True)

for trg in trgs:
	cnt = 0
	cond = True
	for i in range(N):
		if A[i] % trg != 0:
			cnt += 1
			if cnt > 1:
				cond = False
				break
	if not cond:
		continue
	
	ans = trg
	break

print(ans)

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


class SegTree():
    def __init__(self, ide_ele, segfunc):
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        self.seg = []
        self.num = 0

    def init(self, A):
        n = len(A)
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele]*(2*self.num)
        for i in range(n):
            self.seg[i+self.num-1] = A[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:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+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 = 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


import fractions
def main():
    s = SegTree(0, fractions.gcd)
    N = int(input())
    A = list(map(int, input().split()))
    s.init(A)
    ans = 0
    for i in range(N):
        ans = max(ans, fractions.gcd(s.query(0, i), s.query(i+1, N)))
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import fractions
n = int(input())

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

front_gcd = []

a_init = al[0]
for a in al:
    a_init = fractions.gcd(a, a_init)
    front_gcd.append(a_init)
    
back_gcd = []

b_init = al[-1]
for b in al[::-1]:
    b_init = fractions.gcd(b, b_init)
    back_gcd.append(b_init)
    
back_gcd = back_gcd[::-1]

ans = 1
for i in range(n):
    if i == 0:
        x = back_gcd[1]
    elif i == n-1:
        x = front_gcd[-2]
    else:
        x = fractions.gcd(front_gcd[i-1], back_gcd[i+1])
    if x > ans:
        ans = x

print(ans)

Solution (Python):
import fractions
from functools import reduce

n = int(input())
a = [int(_) for _ in input().split()]
left, right, ans = ([0], [0], 0)

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

for i in range(n):
    g = fractions.gcd(left[i], right[n-i-1])
    if ans < g:
        ans = g

print(ans)

Solution (Python):
from fractions import gcd




class SegTree():
    def __init__(self, n_, ele_id, operation_func):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.data = [ele_id] * (2 * self.n - 1)
        self.ele_id = ele_id
        self.operation_func = operation_func

    def __getitem__(self, idx):
        return self.data[idx + self.n - 1]

    def init(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n - 1] = data_init[i]
        for i in range(self.n - 2, -1, -1):
            self.data[i] = self.operation_func(self.data[2 * i + 1],
                                               self.data[2 * i + 2])

    def update(self, idx, x):
        
        idx += self.n - 1
        self.data[idx] = x
        while idx > 0:
            idx = (idx - 1) // 2
            self.data[idx] = self.operation_func(self.data[2 * idx + 1],
                                                 self.data[2 * idx + 2])

    def query(self, a, b):
        return self.query_(a, b, 0, 0, self.n)

    def query_(self, a, b, k, l, r):
        
        if r <= a or b <= l:
            
            return self.ele_id

        if a <= l and r <= b:
            
            return self.data[k]
        else:
            
            child_l = self.query_(a, b, 2 * k + 1, l, (l + r) // 2)
            child_r = self.query_(a, b, 2 * k + 2, (l + r) // 2, r)
            return self.operation_func(child_l, child_r)


n = int(input())
a = list(map(int, input().split()))
seg_gcd = SegTree(n, 0, gcd)
seg_gcd.init(a)

ans = seg_gcd.data[0]
for i in range(n):
    seg_gcd.update(i, 0)
    ans = max(ans, seg_gcd.data[0])
    seg_gcd.update(i, a[i])

print(ans)

Solution (Python):
import fractions

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

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])
  r[n-1-i] = fractions.gcd(r[n-i], a[n-1-i])

maxgcd = 0
for i in range(n):
  if i == 0:
    maxgcd = max(maxgcd, r[1])
  elif i == (n-1):
    maxgcd = max(maxgcd, l[n-2])
  else:
    maxgcd = max(maxgcd, fractions.gcd(l[i-1], r[i+1]))

print (maxgcd)

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

l=[]
l.append(0)
l.append(0)
r=[]
r.append(a[n-1])
r.append(a[n-1])
g=[]

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


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

for j in range(0,n):
  g.append(gcd(l[j+1],r[n-j-1]))

print(max(g))

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


if __name__ == "__main__":
    main()

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

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

L = [0]
R = [0]

for n in range(N-1):
    L.append(gcd(L[n], A[n]))
    R.append(gcd(R[n], A[-1-n]))

M = []

for n in range(N):
    M.append(gcd(L[n], R[-1-n]))

ans = max(M)
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)

leftGcd = [-1] * (N + 1)
leftGcd[0] = A[0]
for i, a in enumerate(A, start=1):
    leftGcd[i] = gcd(leftGcd[i - 1], a)

rightGcd = [-1] * (N + 1)
rightGcd[-1] = A[-1]
for i, a in enumerate(A[:: -1], start=2):
    rightGcd[-i] = gcd(rightGcd[-i + 1], a)

ans = max(leftGcd[-2], rightGcd[1])
for mid in range(N):
    ans = max(ans, gcd(leftGcd[mid], rightGcd[mid + 1]))

print(ans)