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 sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
from fractions import gcd

class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = N
        self.func = func
        self.I = I
        self.seg = [I for i in range(self.sz * 2)]
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k //= 2
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])
 
    def query(self, a, b):
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a % 2 == 1:
                R = self.func(R, self.seg[a])
                a += 1
            if b % 2 == 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a //= 2
            b //= 2
        return R

def main():
    N = int(readline())
    m = map(int,read().split())
    seg = SegmentTree(N , gcd , 0)
    for i in range(N):
        seg.assign(i , next(m))
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

main()

Solution (Python):
class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = N
        self.func = func
        self.I = I
        self.seg = [I for i in range(self.sz * 2)]
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k //= 2
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])
 
    def query(self, a, b):
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a % 2 == 1:
                R = self.func(R, self.seg[a])
                a += 1
            if b % 2 == 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a //= 2
            b //= 2
        return R

def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    from fractions import gcd
    N = int(readline())
    m = map(int,read().split())
    seg = SegmentTree(N , gcd , 0)
    for i in range(N):
        seg.assign(i , next(m))
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

main()

Solution (Python):
import copy
class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = N
        self.func = copy.deepcopy(func)
        self.I = I
        self.seg = [I for i in range(self.sz * 2)]
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k //= 2
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])
 
    def query(self, a, b):
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a % 2 == 1:
                R = self.func(R, self.seg[a])
                a += 1
            if b % 2 == 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a //= 2
            b //= 2
        return R

def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    from fractions import gcd
    N = int(readline())
    m = map(int,read().split())
    seg = SegmentTree(N , gcd , 0)
    for i in range(N):
        seg.assign(i , next(m))
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

main()

Solution (Python):

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

def calcGCDr():
    R = [0 for i in range(n+1)]
    R[n] = 0
    for i in range(1,n+1):
        R[n-i] = fractions.gcd(R[n-i+1],a[n-i])
    return R

def calcGCDl():
    L = [0 for i in range(n+1)]
    L[0] = 0
    for i in range(n):
        L[i+1] = fractions.gcd(L[i],a[i])
    return L

R = calcGCDr()
L = calcGCDl()
max_ans = 1
for i in range(n):
    pre_ans = fractions.gcd(L[i], R[i+1])
    max_ans = max(pre_ans, max_ans)

print(max_ans)

Solution (Python):
import math
import collections
from operator import mul
from functools import reduce
import bisect
import string


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

n=int(input())
a=list(map(int,input().split()))
b=make_divisors(a[0])+make_divisors(a[1])
b=list(set(b))
y=0
for bi in b:
    c=0
    for ai in a:
        if ai%bi!=0:
            c+=1
        if c>=2:
            break
    if c<2:
        y=max(y,bi)

print(y)

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

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

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

gcd_front = gcd(A[0], A[1])
gcd_front_list = [A[0],gcd_front, ]
for i in range(2, N):
    gcd_front = gcd(gcd_front, A[i])
    gcd_front_list.append(gcd_front)

gcd_rear = gcd(A[N-1], A[N-2])
gcd_rear_list = [A[N-1], gcd_rear, ]

for i in range(N-3, -1, -1):
    gcd_rear = gcd(gcd_rear, A[i])
    gcd_rear_list.append(gcd_rear)

ans = 0

for i in range(N):
    if i == 0:
        ans = max(ans, gcd_rear_list[-2])
    if i == N-1:
        ans = max(ans, gcd_front_list[-2])   

    ans = max(ans, gcd(gcd_front_list[i-1],gcd_rear_list[N-2-i]))
    
print(ans)

Solution (Python):
import copy
class SegmentTree(object):
    __slots__ = ['sz','func','I','seg']
    def __init__(self, N, func, I):
        self.sz = N
        self.func = copy.deepcopy(func)
        self.I = I
        self.seg = [I for i in range(self.sz * 2)]
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k //= 2
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])
 
    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a % 2 == 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b % 2 == 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a //= 2
            b //= 2
        return self.func(L, R)

def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    from fractions import gcd
    N = int(readline())
    m = map(int,read().split())
    seg = SegmentTree(N , gcd , 0)
    for i in range(N):
        seg.assign(i , next(m))
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

main()

Solution (Python):
import copy
class SegmentTree:
    __slots__ = ['sz','func','I','seg']
    def __init__(self, N, func, I):
        self.sz = N
        self.func = copy.deepcopy(func)
        self.I = I
        self.seg = [I for i in range(self.sz * 2)]
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k //= 2
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])
 
    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a % 2 == 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b % 2 == 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a //= 2
            b //= 2
        return self.func(L, R)

def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    from fractions import gcd
    N = int(readline())
    m = map(int,read().split())
    seg = SegmentTree(N , gcd , 0)
    for i in range(N):
        seg.assign(i , next(m))
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

main()

Solution (Python):
from sys import stdin
from fractions import gcd

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


L = []

R = []

for i in range(N):
    if i == 0:
        gl = A[i]
        gr = A[N - 1 - i]
    else:
        gl = gcd(gl, A[i])
        gr = gcd(gr, A[N - 1 - i])
    L.append(gl)
    R.append(gr)

ans = 0

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

print(ans)

Solution (Python):
from fractions import gcd
import copy

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

ans_list = []
l_list = [0]*(n+1)
r_list = [0]*(n+1)

for i in range(n):
    l_list[i+1] = gcd(l_list[i], a_list[i])
    r_list[n-i-1] = gcd(r_list[n-i], a_list[n-i-1])

ans_list = []
for j in range(n):
    ans_list.append(gcd(l_list[j], r_list[j+1]))



print(max(ans_list))

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

m = [0]*n

for i in range(n):
    m[i] = gcd(l[i], r[i+1])

print(max(m))

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)

fl_gcd=[0]*(n+1)
fr_gcd=[0]*(n+1)

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



ans=0
for i in range(n):
    lr_gcd=gcd(fl_gcd[i],fr_gcd[i+1])
    ans=max(ans,lr_gcd)
print(ans)

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


class SEGMENT_TREE:
    def __init__(self, N):
        self.N = N
        self.tree = [0] * (2 * N)  

    def init(self, arr):
        N = self.N
        for i in range(N):
            self.tree[N + i] = arr[i]
        for i in range(N - 1, 0, -1):
            self.tree[i] = gcd(
                self.tree[i * 2], self.tree[i * 2 + 1])  

    def update(self, p, value):
        i = p + self.N
        self.tree[i] = value
        while i > 1:
            self.tree[i // 2] = gcd(self.tree[i], self.tree[i ^ 1])  
            i //= 2

    def query(self, l, r):
        N = self.N
        res = 0  
        l += N
        r += N
        while l < r:
            if (l & 1):
                res = gcd(res, self.tree[l])  
                l += 1
            if (r & 1):
                r -= 1
                res = gcd(res, self.tree[r])  
            l //= 2
            r //= 2
        return res


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    seg = SEGMENT_TREE(N)
    seg.init(A)
    ans = 0
    for i in range(N):
        tmp = gcd(seg.query(0, i), seg.query(i + 1, N))
        ans = max(ans, tmp)
    print(ans)

Solution (Python):
from fractions import gcd

N = int(input())
A = list(map(int,input().split()))
'''
res = 0
for i in range(N):
    tmp = A[i+1:] + A[:i]
    ans = tmp[0]
    for i in range(1,N-1):
        ans = gcd(ans,tmp[i])
    res = max(ans,res)
print(res)
'''

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])
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] * (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-1-i])

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

print(ans)

Solution (Python):
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

n=int(input())
a=sorted(list(map(int,input().split())))
option=[]
x=make_divisors(a[0])
y=make_divisors(a[1])

for num in x:
    if num<=a[1]:
        option.append(num)
for num in y:
    if num<=a[1] and num not in option:
        option.append(num)

option=sorted(option,reverse=True)       

for i in option:
    cnt=0
    for j in a:
        if j%i!=0:
            cnt+=1
    if cnt<=1:
        print(i)
        exit()

Solution (Python):
def gcd(a,b):
  while b:a,b=b,a%b
  return a
n,a=int(input()),list(map(int,input().split()))
if n==2:print(max(a));exit()
if n==3:print(max(gcd(a[0],a[1]),gcd(a[0],a[2]),gcd(a[1],a[2])));exit()
ans=ans2=a[0]
for i in range(1,n):
  g=gcd(ans,a[i])
  if g!=ans:
    ans=max(g,ans2)
    ans2=gcd(g,ans2)
print(ans)

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

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

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

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

print(ans)

Solution (Python):
from fractions import gcd
def main():
    n = int(input())
    a = list(map(int,input().split()))
    lg = [a[0]]
    rg = [a[-1]]
    for i in range(n-1):
        lg.append(gcd(lg[-1],a[i+1]))
        rg.append(gcd(rg[-1],a[-i-2]))
    rg.reverse()
    ans = 0
    for i in range(n):
        if i == 0:
            ans = rg[i+1]
        elif i == n-1:
            ans = max(ans,lg[i-1])
        else:
            ans = max(ans,gcd(lg[i-1],rg[i+1]))

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
lg = [a[0]]
rg = [a[-1]]
for i in range(n-1):
    lg.append(gcd(lg[-1],a[i+1]))
    rg.append(gcd(rg[-1],a[-i-2]))
rg.reverse()
ans = 0
for i in range(n):
    if i == 0:
        ans = rg[i+1]
    elif i == n-1:
        ans = max(ans,lg[i-1])
    else:
        ans = max(ans,gcd(lg[i-1],rg[i+1]))

print(ans)

Solution (Python):
import sys
from fractions import gcd
input = sys.stdin.readline
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])
a.reverse()
for i in range(N): r[i + 1] = gcd(r[i], a[i])
res = 0
for i in range(N + 1): res = max(res, gcd(l[i], r[N - i - 1]))
print(res)

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

n = INT()
a = LIST()
arr1 = [0 for _ in range(n)]
arr2 = [0 for _ in range(n)]
arr1[0] = a[0]
arr2[-1] = a[-1]
for i in range(1, n):
    arr1[i] = gcd(arr1[i - 1], a[i])
for i in reversed(range(n - 1)):
    arr2[i] = gcd(arr2[i + 1], a[i])
ans = arr1[-1]
for i in range(n): 
    if 0 < i < n - 1:
        ans = max(ans, gcd(arr1[i - 1], arr2[i + 1]))
    elif i == 0:
        ans = max(ans, arr2[1])
    elif i == n - 1:
        ans = max(ans, arr1[n - 2])
print(ans)

Solution (Python):
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    gcd_L = [0]*(N+2)
    gcd_R = [0]*(N+2)

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

    for i, a in enumerate(A):
        gcd_L[i+1] = gcd(gcd_L[i], a)
    for i, a in enumerate(A[::-1], start=1):
        gcd_R[-(i+1)] = gcd(gcd_R[-i], a)
    gcd_R[0] = gcd_R[1]
    gcd_L[-1] = gcd_L[-2]
    
    ans = 0
    for i in range(1, N+1):
        cur = gcd(gcd_L[i-1], gcd_R[i+1])
        ans = max(ans, cur)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    gcd_L = [0]*(N+1)
    gcd_R = [0]*(N+1)

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

    for i, a in enumerate(A):
        gcd_L[i+1] = gcd(gcd_L[i], a)
    for i, a in enumerate(A[::-1], start=1):
        gcd_R[-(i+1)] = gcd(gcd_R[-i], a)
    ans = 0
    for i in range(N):
        cur = gcd(gcd_L[i], gcd_R[i+1])
        ans = max(ans, cur)
    print(ans)


if __name__ == '__main__':
    main()

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

N = int(input())
A = list(map(int, input().split()))
left = [A[0]] * N
right = [A[-1]] * N
for i in range(1, N):
    left[i] = gcd(left[i-1], A[i-1])
for i in range(1, N)[::-1]:
    right[i-1] = gcd(right[i], A[i])
ans = max(right[0], left[-1])
for i in range(1, N-1):
    ans = max(ans, gcd(left[i], right[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()))
if n==2:print(max(a[0],a[1]));exit()
left=[a[0]]
for i in range(1,n):left.append(gcd(left[-1],a[i]))
right=[a[n-1]]
for i in range(n-2,-1,-1):right.append(gcd(right[-1],a[i]))
right.reverse()
ans=max(right[1],left[n-2])
print(max(ans,max(gcd(left[i-1],right[i+1])for i in range(1,n-1))))

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

def gcd(n, m):
    if m == 0:
        return n
    return gcd(m, n % m)

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

for i, a in enumerate(A, start=1):
    L[i] = gcd(L[i - 1], a)
for i, a in enumerate(A[:: -1], start=1):
    R[i] = gcd(R[i - 1], a)

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

Solution (Python):
def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor: GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)


class Ruiseki_lr:
    """左右からの畳み込みをそれぞれ計算する"""
    def __init__(self, array, op, e):
        self.op = op
        self.e = e

        n = len(array)
        self.left = [e] * (n + 1)
        self.right = [e] * (n + 1)
        for i in range(n):
            self.left[i + 1] = self.op(self.left[i], array[i])
        for i in reversed(range(n)):
            self.right[i] = self.op(self.right[i + 1], array[i])

    def left(self, p):
        """区間[0, p)の畳み込み結果を返す"""
        return self.left[p]

    def right(self, p):
        """区間[p, n)の畳み込み結果を返す"""
        return self.right[p]

    def fold(self, p):
        """p番目を除いた区間[0, n)の畳み込み結果を返す"""
        return self.op(self.left[p], self.right[p + 1])

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

ru = Ruiseki_lr(a, gcd, 0)
max_ = 0
for i in range(n):
    max_ = max(ru.fold(i), max_)
print(max_)

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

lc = [0]
for a in A:
    lc.append(gcd(lc[-1], a))
rc = [0]
for a in A[::-1]:
    rc.append(gcd(rc[-1], a))
rc.reverse()

ans = 0
for l,r in zip(lc,rc[1:]):
    g = gcd(l,r)
    ans = max(ans, g)
print(ans)

Solution (Python):
import copy
class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = N
        self.func = copy.deepcopy(func)
        self.I = I
        self.seg = [I for i in range(self.sz * 2)]
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k //= 2
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])
 
    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a % 2 == 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b % 2 == 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a //= 2
            b //= 2
        return self.func(L, R)

def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    from fractions import gcd
    N = int(readline())
    a = tuple(map(int,input().split()))
    seg = SegmentTree(N , gcd , 0)
    for i in range(N):
        seg.assign(i , a[i])
    seg.build()
    
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import copy
class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = N
        self.func = copy.deepcopy(func)
        self.I = I
        self.seg = [I for i in range(self.sz * 2)]
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k //= 2
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])
 
    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a % 2 == 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b % 2 == 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a //= 2
            b //= 2
        return self.func(L, R)

def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    from fractions import gcd
    N = int(readline())
    m = map(int,read().split())
    seg = SegmentTree(N , gcd , 0)
    for i in range(N):
        seg.assign(i , next(m))
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

main()

Solution (Python):
import copy
class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = N
        self.func = func
        self.I = I
        self.seg = [I for i in range(self.sz * 2)]
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k //= 2
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])
 
    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a % 2 == 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b % 2 == 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a //= 2
            b //= 2
        return self.func(L, R)

def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    from fractions import gcd
    N = int(readline())
    m = map(int,read().split())
    seg = SegmentTree(N , gcd , 0)
    for i in range(N):
        seg.assign(i , next(m))
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

main()

Solution (Python):
import copy
class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = N
        self.func = func
        self.I = copy.deepcopy(I)
        self.seg = [copy.deepcopy(I) for i in range(self.sz * 2)]
 
    def assign(self, k, x):
        self.seg[k + self.sz] = copy.deepcopy(x)
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = copy.deepcopy(x)
        while k > 1:
            k //= 2
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])
 
    def query(self, a, b):
        L = copy.deepcopy(self.I)
        R = copy.deepcopy(self.I)
        a += self.sz
        b += self.sz
        while a < b:
            if a % 2 == 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b % 2 == 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a //= 2
            b //= 2
        return self.func(L, R)

def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    from fractions import gcd
    N = int(readline())
    m = map(int,read().split())
    seg = SegmentTree(N , gcd , 0)
    for i in range(N):
        seg.assign(i , next(m))
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

main()

Solution (Python):
import copy
class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = N
        self.func = func
        self.I = copy.deepcopy(I)
        self.seg = [copy.deepcopy(I) for i in range(self.sz * 2)]
 
    def assign(self, k, x):
        self.seg[k + self.sz] = copy.deepcopy(x)
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = copy.deepcopy(x)
        while k > 1:
            k //= 2
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])
 
    def query(self, a, b):
        L = copy.deepcopy(self.I)
        R = copy.deepcopy(self.I)
        a += self.sz
        b += self.sz
        while a < b:
            if a % 2 == 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b % 2 == 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a //= 2
            b //= 2
        return self.func(L, R)

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
from fractions import gcd
N = int(readline())
m = map(int,read().split())
seg = SegmentTree(N , gcd , 0)
for i in range(N):
    seg.assign(i , next(m))
seg.build()
ans = 1
for i in range(N):
    ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
print(ans)

Solution (Python):
import copy
class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = N
        self.func = func
        self.I = I
        self.seg = [I for i in range(self.sz * 2)]
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k //= 2
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])
 
    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a % 2 == 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b % 2 == 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a //= 2
            b //= 2
        return self.func(L, R)

N = int(input())
a = list(map(int,input().split()))
from fractions import gcd
seg = SegmentTree(N , gcd , 0)
for i in range(N):
    seg.assign(i , a[i])
seg.build()
ans = 1
for i in range(N):
    ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
print(ans)

Solution (Python):
import copy
class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = N
        self.func = func
        self.I = copy.deepcopy(I)
        self.seg = [copy.deepcopy(I) for i in range(self.sz * 2)]
 
    def assign(self, k, x):
        self.seg[k + self.sz] = copy.deepcopy(x)
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = copy.deepcopy(x)
        while k > 1:
            k //= 2
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])
 
    def query(self, a, b):
        L = copy.deepcopy(self.I)
        R = copy.deepcopy(self.I)
        a += self.sz
        b += self.sz
        while a < b:
            if a % 2 == 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b % 2 == 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a //= 2
            b //= 2
        return self.func(L, R)

N = int(input())
a = list(map(int,input().split()))
from fractions import gcd
seg = SegmentTree(N , gcd , 0)
for i in range(N):
    seg.assign(i , a[i])
seg.build()
ans = 1
for i in range(N):
    ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
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)