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):
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed=True):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N = iip(False)
    A = iip()

    A.sort()
    A1 = [i for i in A]
    A2 = [i for i in A]

    ss1 = soinsuu_bunkai(A[0])
    ss2 = soinsuu_bunkai(A[1])
    ah1 = [1 for _ in A]
    ss1.extend(ss2)


    
    ak1 = 1
    for i in ss1:
        out = 0
        ahk = None
        for j, a in enumerate(A1):
            if a % i != 0:
                out += 1
                if out == 2: 
                    break
                else:
                    ahk = j
            else:
                A1[j] //= i
        if out == 2:
            continue
        elif out == 1:
            ah1[ahk] *= i
        else:
            ak1 *= i

    
    
    
    
    print(ak1*max(ah1))





def fprint(s):
    for i in s:
        print(i)

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Solution (Python):
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed=True):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N = iip(False)
    A = iip()

    A.sort()
    A1 = [i for i in A]
    A2 = [i for i in A]

    ss1 = soinsuu_bunkai(A[0])
    ss2 = soinsuu_bunkai(A[1])
    ah1 = [1 for _ in A]
    ah2 = [1 for _ in A]


    
    ak1 = 1
    for i in ss1:
        out = 0
        ahk = None
        for j, a in enumerate(A1):
            if a % i != 0:
                out += 1
                if out == 2: 
                    break
                else:
                    ahk = j
            else:
                A1[j] //= i
        if out == 2:
            continue
        elif out == 1:
            ah1[ahk] *= i
        else:
            ak1 *= i

    ak2 = 1
    for i in ss2:
        out = 0
        ahk = None
        for j, a in enumerate(A2):
            if a % i != 0:
                out += 1
                if out == 2: 
                    break
                else:
                    ahk = j
            else:
                A2[j] //= i
        if out == 2:
            continue
        elif out == 1:
            ah2[ahk] *= i
        else:
            ak2 *= i

    
    
    
    
    print(max(ak1*max(ah1), ak2*max(ah2)))





def fprint(s):
    for i in s:
        print(i)

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Solution (Python):
class SegmentTree:
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length()
        self.default = default
        self.dat = [default]*(self.size*2)
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

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

n = int(input())
a = list(map(int, input().split()))
s = SegmentTree(n, gcd)
for i in range(n):
    s.update(i, a[i])

ans = 1
for i in range(n):
    left = s.query(0, i)
    right = s.query(i+1, n)
    res = gcd(left, right)
    if ans < res:
        ans = res
print(ans)

Solution (Python):
class SegmentTree:
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length()
        self.default = default
        self.dat = [default]*(self.size*2)
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

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

n = int(input())
a = list(map(int, input().split()))
s = SegmentTree(n, gcd)
for i in range(n):
    s.update(i, a[i])

ans = 1
for i in range(n):
    left = s.query(0, i)
    right = s.query(i+1, n)
    res = gcd(left, right)
    if ans < res:
        ans = res
print(ans)

Solution (Python):
class SegmentTree:
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length()
        self.default = default
        self.dat = [default]*(self.size*2)
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

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

n = int(input())
a = list(map(int, input().split()))
s = SegmentTree(n, gcd)
for i in range(n):
    s.update(i,a[i])

ans = 1
for i in range(n):
    left = s.query(0,i)
    right = s.query(i+1,n)
    res = gcd(left, right)
    if ans < res:
        ans = res
print(ans)

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

class SegmentTree:
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length()
        self.default = default
        self.dat = [default]*(self.size*2)
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, a, b=None):
        if b is None:
            b = a + 1
        l, r = a + self.size, b + self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

n = int(input())
a = list(map(int, input().split()))
s = SegmentTree(n, gcd)
for i in range(n):
    s.update(i,a[i])

ans = 1
for i in range(n):
    left = s.query(0,i)
    right = s.query(i+1,n)
    res = gcd(left, right)
    if ans < res:
        ans = res
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline




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





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



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

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

print(ans)

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

def common_divisor(n):
    cd = []
    for i in range(1,int(n**0.5)+2):
        if n%i==0:
            cd.append(i)
            if i != n//i:
                cd.append(n//i)
    return set(cd)


cds = common_divisor(A[0]).union(common_divisor(A[1]))
ans = 1
for k in cds:
    
    cnt = 0
    for a in A:
        if a%k!=0:
            cnt += 1
            if cnt == 2:
                break
    else:
        ans = max(ans,k)

print(ans)

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

def common_divisor(n):
    cd = []
    for i in range(1,int(n**0.5)+2):
        if n%i==0:
            cd.append(i)
            if i != n//i:
                cd.append(n//i)
    return set(cd)


cds = common_divisor(A[0]).union(common_divisor(A[1]))
ans = 1
for k in cds:
    
    cnt = 0
    for a in A:
        if a%k!=0:
            cnt += 1
            if cnt == 2:
                break
    else:
        ans = max(ans,k)

print(ans)

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

def common_divisor(n):
    cd = []
    for i in range(1,int(n**0.5)+2):
        if n%i==0:
            cd.append(i)
            if i != n//i:
                cd.append(n//i)
    return list(set(cd))

cd_dic = {}
for cd in common_divisor(A[0]):
    cd_dic[cd] = 1

for cd in common_divisor(A[1]):
    if cd not in cd_dic:
        cd_dic[cd] = 1
    else:
        cd_dic[cd] = 2

for k in cd_dic.keys():
    if cd_dic[k] == 2:
        cd_dic[k] = True
    else:
        cd_dic[k] = False
from copy import copy
for a in A[2:]:
    
    d = copy(cd_dic)
    for k,v in cd_dic.items():
        if a%k!=0:
            if v == True:
                d[k] = False
            else:
                d.pop(k)
    cd_dic = copy(d)
ans = max(cd_dic.keys())
print(ans)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

n = I()
a = LI()
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[-1] = a[-1]
for i in range(n-1)[::-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[-2])
    else:
        ans = max(ans,gcd(l[i-1],r[i+1]))
print(ans)

Solution (Python):
import sys
import heapq

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

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

def main():
    if len(A) <= 2:
        print(max(A))
        exit()
    else:
        a0, a1 = heapq.nsmallest(2, A)
        all_divisors = list(set(make_divisors(a0) + make_divisors(a1)))

    ans = 1
    for divisor in all_divisors:
        cnt = 0
        for a in A:
            if a % divisor != 0:
                cnt += 1
            if cnt == 2:
                break
        if cnt < 2:
            ans = max(ans, divisor)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys

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

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

def main():
    if len(A) <= 2:
        print(max(A))
        exit()
    else:
        all_divisors = list(set(make_divisors(A[0]) + make_divisors(A[1])))

    ans = 1
    for divisor in all_divisors:
        cnt = 0
        for a in A:
            if a % divisor != 0:
                cnt += 1
            if cnt == 2:
                break
        if cnt < 2:
            ans = max(ans, divisor)

    print(ans)

if __name__ == '__main__':
    main()

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

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

if len(A) <= 2:
    print(max(A))
    exit()
else:
    all_divisors = list(set(make_divisors(A[0]) + make_divisors(A[1])))

ans = 1
for divisor in all_divisors:
    cnt = 0
    for a in A:
        if a % divisor != 0:
            cnt += 1
        if cnt == 2:
            break
    if cnt < 2:
        ans = max(ans, divisor)

print(ans)

Solution (Python):
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect




from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

def main():
  n = int(readline())
  a = [ int(i) for i in readline().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])
  
  ans = 0
  
  for a, b in zip(gcd_l, gcd_r):
    x = gcd(a,b)
    if ans < x:
      ans = x
   
  print(ans)
  
  
if __name__ == '__main__':
  main()

Solution (Python):

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

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

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

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

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

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

N = int(input())

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

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

gcd_left = []
tmp = A[0]
for i in range(N):
    tmp = gcd(tmp, A[i])
    gcd_left.append(tmp)

gcd_right = []
tmp = A[-1]
for i in range(N-1, -1, -1):
    tmp = gcd(tmp, A[i])
    gcd_right.append(tmp)
ans = 0
for i in range(len(A)):
    if i == 0:
        ans = max(ans, gcd_right[-2])
    elif i == len(A) - 1:
        ans = max(ans, gcd_left[-2])
    else:
        ans = max(ans, gcd(gcd_left[i-1], gcd_right[N-i-2]))

print(ans)

Solution (Python):
def main():
    from fractions import gcd

    n, *a = map(int, open(0).read().split())
    a = tuple([0] + a + [0])
    l = [0 for _ in range(n + 1)]
    r = [0 for _ in range(n + 1)]
    tmpl = 0
    tmpr = 0
    for i in range(1,n+1):
        tmpl = gcd(tmpl, a[i-1])
        tmpr = gcd(tmpr, a[-i])
        l[i] = tmpl
        r[-i] = tmpr

    ans = []
    for i, j in zip(l, r):
        ans.append(gcd(i, j))

    print(max(ans))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from fractions import gcd

    n, *a = map(int, open(0).read().split())
    a = tuple([0] + a + [0])
    l = [0 for _ in range(n + 1)]
    r = [0 for _ in range(n + 1)]
    tmpl = 0
    tmpr = 0
    for i in range(1,n+1):
        tmpl = gcd(tmpl, a[i-1])
        tmpr = gcd(tmpr, a[-i])
        l[i] = tmpl
        r[-i] = tmpr

    ans = 0
    for i, j in zip(l, r):
        g = gcd(i, j)
        ans = max(ans, g)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from fractions import gcd

    n, *a = map(int, open(0).read().split())
    a = [0] + a + [0]
    l = [0 for _ in range(n + 1)]
    r = [0 for _ in range(n + 1)]
    tmpl = 0
    tmpr = 0
    for i in range(1,n+1):
        tmpl = gcd(tmpl, a[i-1])
        tmpr = gcd(tmpr, a[-i])
        l[i] = tmpl
        r[-i] = tmpr

    ans = 0
    for i, j in zip(l, r):
        g = gcd(i, j)
        ans = max(ans, g)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
def gcd(a, b):
	if a < b:
		a, b = b, a
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
n = int(input())
a = np.array([int(x) for x in input().split()])
np.sort(a)
l = np.zeros(n + 1)
r = np.zeros(n + 1)
m = np.zeros(n)
for i in range(n):
	l[i + 1] = gcd(l[i], a[i])
for i in reversed(range(n)):
	r[i] = gcd(r[i + 1], a[i])
for i in range(n):
	m[i] = gcd(l[i], r[i + 1])
print(int(np.max(m)))

Solution (Python):
from fractions import gcd
ide = 0
def func(a,b):
  return gcd(a,b)
class SegmentTree:
  def __init__(self,ls):
    n = len(ls)
    self.tree = [ide for i in range(n)]+ls
    for i in range(1,n)[::-1]:
      self.tree[i] = func(self.tree[i<<1|0],self.tree[i<<1|1])
  def get(self,l,r):
    ret = ide
    l += n
    r += n
    while l < r:
      if l&1:
        ret = func(ret,self.tree[l])
        l += 1
      if r&1:
        ret = func(ret,self.tree[r-1])
      l >>= 1
      r >>= 1
    return ret
  def update(self,i,x):
    i += n
    self.tree[i] = x
    while i > 1:
      i >>= 1
      self.tree[i] = func(self.tree[i<<1|0],self.tree[i<<1|1])

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
sol = SegmentTree(a)
ans = 0
for i in range(n):
  t = a[i]
  sol.update(i,0)
  ans = max(ans,sol.get(0,n))
  sol.update(i,t)
print(ans)

Solution (Python):
import fractions

def main():
    n = int(input())
    A = [int(e) for e in input().split()]

    G = [A[0]]
    prev = A[0]
    for i in range(1, n):
        prev = fractions.gcd(prev, A[i])
        G.append(prev)

    ANS = [G[n - 2]]
    prev = A[n - 1]
    for i in range(n - 2, 0, -1):
        ANS.append(fractions.gcd(G[i - 1], prev))
        prev = fractions.gcd(A[i], prev)

    ANS.append(prev)

    print(max(ANS))

if __name__ == "__main__":
    main()

Solution (Python):
import fractions

n=int(input())
A=list(sorted(map(int,input().split())))
L=[A[0]]
R=[A[n-1]]

for i in range(n-2):
    L.append(fractions.gcd(L[i],A[i+1]))
    R.append(fractions.gcd(R[i],A[n-i-2]))

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

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


class SegmentTree:
    def __init__(self, N, func, I):
        self.N = N
        self.sz = 2**(N-1).bit_length()
        self.func = func
        self.I = I
        self.seg = [I] * (self.sz * 2)

    def assign(self, k, x):
        self.seg[k + self.sz] = x

    def build(self):
        for i in reversed(range(1, self.sz)):
            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 >>= 1
            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
        if b == self.N:
            b = self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)


def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = map(int, readline().split())
    seg = SegmentTree(N, gcd, 0)
    for i, n in enumerate(L):
        seg.assign(i, n)
    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 sys
readline = sys.stdin.buffer.readline


class SegmentTree:
    def __init__(self, N, func, I):
        self.N = N
        self.sz = 2**(N-1).bit_length()
        self.func = func
        self.I = I
        self.seg = [I] * (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 >>= 1
            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
        if b == self.N:
            b = self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)


def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = map(int, readline().split())
    seg = SegmentTree(N, gcd, 0)
    for i, n in enumerate(L):
        seg.assign(i, n)
    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 sys
readline = sys.stdin.buffer.readline


class SegmentTree:
    def __init__(self, N, func, I):
        self.N = N
        self.sz = 2**(N-1).bit_length()
        self.func = func
        self.I = I
        self.seg = [I] * (self.sz * 2)

    def assign(self, k, x):
        self.seg[k + self.sz] = x

    def build(self):
        for i in reversed(range(1, self.sz)):
            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 >>= 1
            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 & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)


def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = map(int, readline().split())
    seg = SegmentTree(N, gcd, 0)
    for i, n in enumerate(L):
        seg.assign(i, n)
    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 sys
readline = sys.stdin.buffer.readline


class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = 2**(N-1).bit_length()
        self.func = func
        self.I = I
        self.seg = [I] * (self.sz * 2)

    def assign(self, k, x):
        self.seg[k + self.sz] = x

    def build(self):
        for i in reversed(range(1, self.sz)):
            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 >>= 1
            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 & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)


def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    N = int(readline())
    L = map(int, readline().split())
    seg = SegmentTree(N, gcd, 0)
    for i, n in enumerate(L):
        seg.assign(i, n)
    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()