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


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

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

    
    ide_ele = 0

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

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


if __name__ == '__main__':
    main()

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
N = int(input())
A = list(map(int, input().split()))

L = [0]
R = [0]

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

ans = 0

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

Solution (Python):
INF = -float("inf")
def gcd(x,y):
    if x == INF:
        return y
    if y == INF:
        return x
    if x<y:
        x,y = y,x
    r = (x%y)
    while r:
        x,y = y, r
        r = (x%y)
    return y
    
N = int(input())
A = list(map(int,input().split()))
lgcd = [INF]*N
rgcd = [INF]*N
lgcd[0] = A[0]
rgcd[0] = A[-1]
for i in range(1,N):
    lgcd[i] = gcd(lgcd[i-1], A[i])
    rgcd[i] = gcd(rgcd[i-1], A[N-i-1])
lgcd = [INF]+lgcd
rgcd = [INF]+rgcd
ans = INF
for i in range(N):
    ans = max(ans, gcd(lgcd[i],rgcd[N-i-1]))
print(ans)

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

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

Solution (Python):
from fractions import gcd
import copy

class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = 2 ** (N-1).bit_length()
        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()))

def f(x,y):
    if x * y == 0:
        return x + y
    else:
        return gcd(x,y)

seg = SegmentTree(N + 1, f, 0)
for i in range(N):
    seg.assign(i , A[i])
seg.build()

ans = 1
for i in range(N):
    ans = max(ans , f(seg.query(0 , i) , seg.query(i + 1 , N)))
print(ans)

Solution (Python):
class SWAG():
    __slots__='unit','f','fold_r','fold_l','data_r','data_l'
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.construct(data)
    def construct(self,data):
        self.fold_r=[self.unit]
        self.fold_l=[self.unit]
        self.data_r=[]
        self.data_l=[]
        sep=0--len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    def append(self,x):
        self.fold_r+=self.f(self.fold_r[-1],x),
        self.data_r+=x,
    def appendleft(self,x):
        self.fold_l+=self.f(self.fold_l[-1],x),
        self.data_l+=x,
    def pop(self):
        if not self.data_r:
            self.construct(self.data_l[::-1])
        if not self.data_r:
            return self.popleft()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.construct(self.data_r)
        if not self.data_l:
            return False
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
def main():
    from fractions import gcd
    n,*a=map(int,open(0).read().split())
    l,r=SWAG(0,gcd,[]),SWAG(0,gcd,a[1:])
    m=r.fold_all()
    for i in range(n-1):
        l.append(a[i])
        r.popleft()
        m=max(m,gcd(l.fold_all(),r.fold_all()))
    print(m)
main()

Solution (Python):
from collections import deque
class SWAG():
    __slots__='unit','f','fold_r','fold_l','data_r','data_l'
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.construct(data)
    def construct(self,data):
        self.fold_r=deque([self.unit])
        self.fold_l=deque([self.unit])
        self.data_r=deque()
        self.data_l=deque()
        sep=0--len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.construct(tuple(self.data_l)[::-1])
        if not self.data_r:
            return self.popleft()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.construct(tuple(self.data_r))
        if not self.data_l:
            return False
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
def main():
    from fractions import gcd
    n,*a=map(int,open(0).read().split())
    l,r=SWAG(0,gcd,[]),SWAG(0,gcd,a[1:])
    m=r.fold_all()
    for i in range(n-1):
        l.append(a[i])
        r.popleft()
        m=max(m,gcd(l.fold_all(),r.fold_all()))
    print(m)
main()

Solution (Python):
from collections import deque
class SWAG():
    __slots__='unit','f','fold_r','fold_l','data_r','data_l'
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.construct(data)
    def construct(self,data):
        self.fold_r=deque([self.unit])
        self.fold_l=deque([self.unit])
        self.data_r=deque()
        self.data_l=deque()
        sep=0--len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.construct(list(self.data_l)[::-1])
        if not self.data_r:
            return self.popleft()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.construct(list(self.data_r))
        if not self.data_l:
            return False
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
def main():
    from fractions import gcd
    n,*a=map(int,open(0).read().split())
    l,r=SWAG(0,gcd,[]),SWAG(0,gcd,a[1:])
    m=r.fold_all()
    for i in range(n-1):
        l.append(a[i])
        r.popleft()
        m=max(m,gcd(l.fold_all(),r.fold_all()))
    print(m)
main()

Solution (Python):
class SWAG():
    __slots__='unit','f','fold_r','fold_l','data_r','data_l'
    def __init__(self,unit,f,data):
        self.unit=unit
        self.f=f
        self.construct(data)
    def construct(self,data):
        self.fold_r=[self.unit]
        self.fold_l=[self.unit]
        self.data_r=[]
        self.data_l=[]
        sep=0--len(data)//2
        for t in data[sep:]:
            self.append(t)
        for t in data[sep-1::-1]:
            self.appendleft(t)
    def append(self,x):
        self.fold_r.append(self.f(self.fold_r[-1],x))
        self.data_r.append(x)
    def appendleft(self,x):
        self.fold_l.append(self.f(self.fold_l[-1],x))
        self.data_l.append(x)
    def pop(self):
        if not self.data_r:
            self.construct(self.data_l[::-1])
        if not self.data_r:
            return self.popleft()
        self.fold_r.pop()
        return self.data_r.pop()
    def popleft(self):
        if not self.data_l:
            self.construct(self.data_r)
        if not self.data_l:
            return False
        self.fold_l.pop()
        return self.data_l.pop()
    def fold_all(self):
        return self.f(self.fold_r[-1],self.fold_l[-1])
def main():
    from fractions import gcd
    n,*a=map(int,open(0).read().split())
    l,r=SWAG(0,gcd,[]),SWAG(0,gcd,a[1:])
    m=r.fold_all()
    for i in range(n-1):
        l.append(a[i])
        r.popleft()
        m=max(m,gcd(l.fold_all(),r.fold_all()))
    print(m)
main()

Solution (Python):
import fractions
from functools import reduce
from collections import deque

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


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

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

Solution (Python):
from fractions import gcd
import copy

class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = 2 ** (N-1).bit_length()
        self.func = copy.deepcopy(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()))

def f(x,y):
    if x * y == 0:
        return x + y
    else:
        return gcd(x,y)

seg = SegmentTree(N + 1, f, 0)
for i in range(N):
    seg.assign(i , A[i])
seg.build()

ans = 1
for i in range(N):
    ans = max(ans , f(seg.query(0 , i) , seg.query(i + 1 , N)))
print(ans)

Solution (Python):
from fractions import gcd

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

cuml = [0]
cumr = [0]

for i in range(N):
    cuml.append(gcd(cuml[i], A[i]))
    cumr.append(gcd(cumr[i], A[N-i-1]))


maxg = 0
for i in range(N):
    
    maxg = max(maxg, gcd(cuml[i], cumr[N-i-1]))
print(maxg)

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

Solution (Python):


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    
    
    

    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 gcd_group(arr):
        g = gcd(arr[0], arr[1])
        for i in range(2, len(arr)):
            g = gcd(g, arr[i])
        return g
    
    def lcm(a, b):
        g = gcd(a, b)
        return (a*b)//g
    
    def lcm_group(arr):
        l = lcm(arr[0], arr[1])
        for i in range(2, len(arr)):
            l = lcm(l, arr[i])
        return l
    
    l = [0]
    for i in range(N-1):
        l.append(gcd(l[-1], A[i]))
    r = [0]
    for i in range(N-1, 0, -1):
        r.append(gcd(r[-1], A[i]))
    
    res = 0
    for i in range(N):
        res = max(res, gcd(l[i], r[-(i+1)]))
    print(res)


if __name__ == '__main__':
    main()

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

mx = 0
gd_pos = [] 
gd_pos.append(a[0])
for i in range(1, n):
    gd_pos.append(fractions.gcd(gd_pos[i-1], a[i]))
gd_neg = [] 
gd_neg.append(a[-1])
a_rev = a[::-1]
for i in range(1, n):
    gd_neg.append(fractions.gcd(gd_neg[i-1], a_rev[i]))

def popped_g(i):
    if i == 0: return gd_neg[n-2]
    elif i == n-1: return gd_pos[n-2]
    else:
        return fractions.gcd(gd_pos[i-1], gd_neg[n-i-2])

ans = [popped_g(i) for i in range(n)]
print(max(ans))

Solution (Python):
import functools

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

def gcd(nums):
    return functools.reduce(euclid, nums)

N = int(input())
A = list(map(int,(input().split())))
L = [0]*N
R = [0]*N
L[0] = A[0]
R[0] = A[N-1]
for i in range(1,N):
    L[i] = gcd([L[i-1],A[i]])
for i in range(1,N):
    R[i] = gcd([R[i-1],A[N-1-i]])

p = []

for i in range(N):
    if i == 0:
        p.append(R[N-2])
    elif i == N-1:
        p.append(L[N-2])
    else:
        p.append( gcd([L[i-1], R[N-2-i]]) )

print(max(p))

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


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


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

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

Solution (Python):
from fractions import gcd

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

M = [0]*N


L = [0]*N
R = [0]*N

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

for j in range(N):
    M[j] = gcd(L[j],R[j])

print(max(M))

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

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

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

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

max = 0
for i in range(n):
    if i == 0:
        gcd_i = r[i + 1]
    elif i == n - 1:
        gcd_i = l[i - 1]
    else:
        gcd_i = gcd(l[i - 1], r[i + 1])
    if max < gcd_i:
        max = gcd_i

print(max)

Solution (Python):


from fractions import gcd







import sys
sys.setrecursionlimit(10**9)


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

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

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


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

    print(maxgcd)


resolve()

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 sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class SegmentTree:
    """
    引数：
        N: 処理する区間の長さ
        operator: モノイド演算 (max, min, __add__,ラムダ式,関数定義など)
        UNIT: 単位元
        a: 長さNの配列 a で初期化（a を与えない場合、単位元で初期化）
    注意: 内部的には 1-indexed
    """
    def __init__(self, N, operator, unit, a=None):
        self.op = operator
        self.UNIT = unit
        self.N0 = 2**(N-1).bit_length()
        self.tree = [self.UNIT]*(2*self.N0)
        if a != None:
            self.tree[self.N0:self.N0+N] = a[:]
            for k in range(self.N0-1, 0, -1):
                self.tree[k] = self.op(self.tree[2*k], self.tree[2*k+1])
    
    def update(self, k, x):
        k += self.N0
        self.tree[k] = x
        k //= 2
        while k:
            self.tree[k] = self.op(self.tree[2*k], self.tree[2*k+1])
            k //= 2
    
    def query(self, l, r):
        L = l + self.N0
        R = r + self.N0 + 1
        s = self.UNIT
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(self.tree[R], s)
            if L & 1:
                s = self.op(s, self.tree[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    def get(self, k):  
        return self.tree[k+self.N0]

N = INT()
A = LIST()
lcm_base = lambda x, y: (x * y) // gcd(x, y)
many_lcm = lambda numbers: reduce(lcm_base, numbers)
unit = many_lcm(A)
seg = SegmentTree(N+1, gcd, unit)

for i, x in enumerate(A):
	seg.update(i+1, x)

ans = 0
for i, x in enumerate(A):
	seg.update(i+1, unit)
	ans = max(ans, seg.query(1, N))
	seg.update(i+1, A[i])
print(ans)

Solution (Python):
from sys import stdin
from fractions import gcd
def main():
    
    readline=stdin.readline
    N=int(readline())
    A=list(map(int,readline().split()))
    A.insert(0,0)
    A.append(0)

    L=[0]*N
    R=[0]*N
    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+2])

    res=0
    for i in range(N):
        res=max(res,gcd(L[i],R[i]))
    print(res)

if __name__=="__main__":
    main()

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

from fractions import gcd
n = inn()
a = inl()
l = [a[0]]*n
for i in range(1,n):
    l[i] = gcd(l[i-1],a[i])
r = [a[n-1]]*n
for i in range(n-2,-1,-1):
    r[i] = gcd(r[i+1],a[i])
mx = max(l[n-2],r[1])
for i in range(1,n-1):
    mx = max(mx, gcd(l[i-1],r[i+1]))
print(mx)

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)












class Segtree:
    

    

    
    
    

    

    def __init__(s,l,unit,oper):
        s.unit = unit
        s.oper = oper
        s.n = 1
        while s.n<l:
            s.n *= 2
        s.ary = [s.unit for i in range(2*s.n-1)]

    def get(s,i):
        return s.ary[i+s.n-1]

    def set(s,i,v):
        k = i+s.n-1
        s.ary[k] = v
        while k>0:
            k = (k-1)//2
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def setary(s,a):
        for i,v in enumerate(a):
            s.ary[i+s.n-1] = v
        for k in range(s.n-2,-1,-1):
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def query(s,x,y):
        l = x+s.n-1
        r = y+s.n-1
        res = s.unit
        while l<r:
            if not l%2:
                res = s.oper(res,s.ary[l])
                l += 1
            if not r%2:
                r -= 1
                res = s.oper(res,s.ary[r])
            l >>= 1
            r >>= 1
        return res




from fractions import gcd
n = inn()
a = inl()
sgt = Segtree(n,0,gcd)
sgt.setary(a)
mx = max(sgt.query(1,n), sgt.query(0,n-1))
for i in range(1,n-1):
    g = gcd(sgt.query(0,i),sgt.query(i+1,n))
    mx = max(mx,g)
print(mx)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
def gcd(a,b):
    if a==b:
      return a
    else:
      a,b=max(a,b),min(a,b)
      if a%b==0:
        return b
      else:
        return gcd(b,a%b)
R=[]
L=[]
for i in range(n):
  if i==0:
    L.append(a[i])
    R.append(a[-i-1])
  else:
    vl,vr=gcd(a[i],L[-1]),gcd(a[-i-1],R[-1])
    L.append(vl)
    R.append(vr)
ans=0
for i in range(n):
  if i==0:
    ans=max(ans,R[-i-2])
  elif i==n-1:
    ans=max(ans,L[i-1])
  else:
    ans=max(ans,gcd(L[i-1],R[-i-2]))
print(ans)

Solution (Python):
from fractions import gcd
n = int(input())
a = [int(i) for i in input().split()]

b = [0] * n
c = [0] * n

j = 0
for i, k in enumerate(a):
    b[i] = j
    j = gcd(j, k)

j = 0
for i, k in reversed(list(enumerate(a))):
    c[i] = j
    j = gcd(j, k)

ma = 0
for i in range(n):
    ma = max(ma, gcd(b[i], c[i]))
print(ma)

Solution (Python):
class SegTree():
    def __init__(self,data,unit,f):
        self.size=n=len(data)
        self.data=[unit for _ in range(n)]+data
        for i in range(n-1,0,-1):self.data[i]=f(self.data[i+i],self.data[i-~i])
        self.unit=unit
        self.f=f
    def update(self,i,x):
        c,f=self.data,self.f
        i+=self.size
        c[i]=x
        while i>1:
            i>>=1
            c[i]=f(c[i+i],c[i-~i])
    def add(self,i,x):
        c,f=self.data,self.f
        i+=self.size
        c[i]=f(c[i],x)
        while i>1:
            i>>=1
            c[i]=f(c[i+i],c[i-~i])
    def query(self,l,r):
        c,f=self.data,self.f
        x,y=self.unit,self.unit
        l+=self.size
        r+=self.size
        while l<r:
            if l&1:
                x=f(x,c[l])
                l+=1
            if r&1:
                r-=1
                y=f(c[r],y)
            l>>=1
            r>>=1
        return f(x,y)
def main():
    from fractions import gcd
    n,*a=map(int,open(0).read().split())
    f=SegTree(a,0,gcd).query
    m=max(f(1,n),f(0,n-1))
    for i in range(n-2):
        m=max(m,gcd(f(0,i+1),f(i+2,n)))
    print(m)
main()

Solution (Python):
class DisjointSparseTable():
    def __init__(self,data,f):
        from math import ceil,log
        self.n=n=len(data)
        m=ceil(log(n,2)) 
        self.f=f
        self.h=[0,0]
        for i in range(2,2**m):self.h.append(self.h[i//2]+1)
        self.data=[data]
        for i in range(1,m):
            d=[0]*n
            w=2**i
            for j in range(0,n,w*2):
                c=min(j+w,n)
                d[c-1]=data[c-1]
                for k in range(c-2,j-1,-1):d[k]=f(data[k],d[k+1])
                if c<n:
                    d[c]=data[c]
                    for k in range(c+1,min(j+w*2,n)):d[k]=f(data[k],d[k-1])
            self.data.append(d)
    def get(self,l,r): 
        r-=1
        if l==r:return self.data[0][l]
        d=self.data[self.h[l^r]]
        return self.f(d[l],d[r])
def main():
    from fractions import gcd
    n,*a=map(int,open(0).read().split())
    f=DisjointSparseTable(a,gcd).get
    m=max(f(1,n),f(0,n-1))
    for i in range(n-2):
        m=max(m,gcd(f(0,i+1),f(i+2,n)))
    print(m)
main()

Solution (Python):
class SegTree():
    def __init__(self,data,unit,f):
        self.size=n=len(data)
        self.data=[unit for _ in range(n)]+data
        for i in range(n-1,0,-1):self.data[i]=f(self.data[i+i],self.data[i-~i])
        self.unit=unit
        self.f=f
    def update(self,i,x):
        c,f=self.data,self.f
        i+=self.size
        c[i]=x
        while i>1:
            i>>=1
            c[i]=f(c[i+i],c[i-~i])
    def add(self,i,x):
        c,f=self.data,self.f
        i+=self.size
        c[i]=f(c[i],x)
        while i>1:
            i>>=1
            c[i]=f(c[i+i],c[i-~i])
    def query(self,l,r):
        c,f=self.data,self.f
        x,y=self.unit,self.unit
        l+=self.size
        r+=self.size
        while l<r:
            if l&1:
                x=f(x,c[l])
                l+=1
            if r&1:
                r-=1
                y=f(c[r],y)
            l>>=1
            r>>=1
        return f(x,y)
def main():
    from fractions import gcd
    n,*a=map(int,open(0).read().split())
    f=SegTree(a,0,gcd).query
    m=max(f(1,n),f(0,n-1))
    for i in range(n-2):
        m=max(m,gcd(f(0,i+1),f(i+2,n)))
    print(m)
main()

Solution (Python):
class DisjointSparseTable():
    def __init__(self,data,f):
        from math import ceil,log
        self.n=n=len(data)
        m=ceil(log(n,2)) 
        self.f=f
        self.h=[0,0]
        for i in range(2,2**m):self.h.append(self.h[i//2]+1)
        self.data=[data]
        for i in range(1,m):
            d=[0]*n
            w=2**i
            for j in range(0,n,w*2):
                c=min(j+w,n)
                d[c-1]=data[c-1]
                for k in range(c-2,j-1,-1):d[k]=f(data[k],d[k+1])
                if c<n:
                    d[c]=data[c]
                    for k in range(c+1,min(j+w*2,n)):d[k]=f(data[k],d[k-1])
            self.data.append(d)
    def get(self,l,r): 
        r-=1
        if l==r:return self.data[0][l]
        d=self.data[self.h[l^r]]
        return self.f(d[l],d[r])
def main():
    from fractions import gcd
    n,*a=map(int,open(0).read().split())
    f=DisjointSparseTable(a,gcd).get
    m=max(f(1,n),f(0,n-1))
    for i in range(n-2):
        m=max(m,gcd(f(0,i+1),f(i+2,n)))
    print(m)
main()

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

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

ans=-1
init(A)
for i in range(n):
  ans=max(ans, 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()))
LtR=[0]*N
LtR[0]=A[0]
RtL=[0]*N
RtL[-1]=A[-1]
for i in range(N-1):
  LtR[i+1]=gcd(A[i+1],LtR[i])
  RtL[-(i+2)]=gcd(A[-(i+2)], RtL[-(i+1)])
  
  
ans=max(LtR[-2], RtL[1])
for i in range(1,N-1):
  ans=max(ans, gcd(LtR[i-1], RtL[i+1]))
  

print(ans)

Solution (Python):
import fractions

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

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

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

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