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,fractions
input = sys.stdin.readline
class segment_tree:
    '''
    init_val(int): 初期化値
    Input(array):  入力
    '''
    def __init__(self, init_val, Input):
        
        n=len(Input)
        self.init_val = init_val
        self.num = 2 ** (n - 1).bit_length()
        self.seg = [init_val] * 2 * self.num
        for i in range(n):
            self.seg[i + self.num - 1] = Input[i]
        for i in range(self.num - 2, -1, -1):
            self.seg[i]=self._segfunc(self.seg[2*i+1],self.seg[2*i+2])
    def _segfunc(self, left, right):
        '''
        ここに求めたい関数を入れる
        ex)最小値問題→min, 
        left:左の子
        right:右の子
        '''
        res=fractions.gcd(left,right)
        return res
    def update(self, k, x):
        '''
        k番目の値をxに書き換える
        '''
        k += self.num - 1
        self.seg[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.seg[k] = self._segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])
    def query(self, p, q):
        '''
        区間[p,q)の目的の値を取り出す
        '''
        if q <= p:
            return self.init_val
        p += self.num - 1
        q += self.num - 2
        res = self.init_val
        while q - p > 1:
            if p % 2 == 0: 
                res = self._segfunc(res, self.seg[p])
            if q % 2 == 1:
                res = self._segfunc(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        res = self._segfunc(res, self.seg[p])
        res = self._segfunc(res, self.seg[q])
        return res
INF = 10 ** 10
n=int(input())
a=list(map(int,input().split()))


dp = segment_tree(0, a)
ans=-1
for i in range(n):
  ans=max(ans,fractions.gcd(dp.query(0,i),dp.query(i+1,n)))
print(ans)

Solution (Python):

from fractions import gcd
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


class SegmentTree:
    
    def __init__(self, n, initial=0):
        """
        n: 配列の大きさ
        initial: 単位元 (RMQでは大きな値)
        """
        self.offset = 2**(n-1).bit_length()  
        self.initial = initial
        self.seg = [self.initial] * (2 * self.offset)
        

    def build(self, A):
        """
        A: 処理したい配列
        """
        for i, a in enumerate(A, start=self.offset):
            self.seg[i] = a
        for i in range(self.offset-1,0,-1):
            self.seg[i] = gcd(self.seg[i<<1] ,self.seg[(i<<1)+1])

            
    def update(self, k, a):
        """
        k番目の値をaに変更
        """
        k += self.offset
        self.seg[k] = a
        while k:
            k >>= 1
            self.seg[k] = gcd(self.seg[k<<1], self.seg[(k<<1)+1])

            
    def query(self, a, b):
        """
        区間[a, b)に対して最小公倍数を求める
        """
        a += self.offset
        b += self.offset - 1 
        res = self.initial
        while a < b:
            if a & 1:  
                res = gcd(res, self.seg[a])
                a += 1
            if not b & 1:  
                res = gcd(res, self.seg[b])
                b -= 1
            a >>= 1
            b >>= 1
        
        if a == b:
            res = gcd(res, self.seg[a])
        
        return res


if __name__ == "__main__":
    N = int(readline())
    A = [int(i) for i in readline().split()]
    seg = SegmentTree(N)
    seg.build(A)

    ans = seg.query(1, N)
    for i in range(N-2):
        tmp = gcd(seg.query(0, i+1), seg.query(i+2, N))
        ans = max(ans, tmp)
    ans = max(ans, seg.query(0, N-1))

    print(ans)

Solution (Python):


from fractions import gcd
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


class SegmentTree:
    
    def __init__(self, n, initial=0):
        """
        n: 配列の大きさ
        initial: 単位元 (RMQでは大きな値)
        """
        self.offset = 2**(n-1).bit_length()  
        self.initial = initial
        self.seg = [self.initial] * (2 * self.offset)
        

    def build(self, A):
        """
        A: 処理したい配列
        """
        for i, a in enumerate(A, start=self.offset):
            self.seg[i] = a
        for i in range(self.offset-1,0,-1):
            self.seg[i] = gcd(self.seg[i<<1] ,self.seg[(i<<1)+1])

            
    def update(self, k, a):
        """
        k番目の値をaに変更
        """
        k += self.offset
        self.seg[k] = a
        while k:
            k >>= 1
            self.seg[k] = gcd(self.seg[k<<1], self.seg[(k<<1)+1])

            
    def query(self, a, b):
        """
        区間[a, b)に対して最小公倍数を求める
        """
        a += self.offset
        b += self.offset - 1 
        res = self.initial
        while a < b:
            if a & 1:  
                res = gcd(res, self.seg[a])
                a += 1
            if not b & 1:  
                res = gcd(res, self.seg[b])
                b -= 1
            a >>= 1
            b >>= 1
        
        if a == b:
            res = gcd(res, self.seg[a])
        
        return res


if __name__ == "__main__":
    N = int(readline())
    A = [int(i) for i in readline().split()]
    seg = SegmentTree(N)
    seg.build(A)

    ans = seg.query(1, N)
    for i in range(N-2):
        tmp = gcd(seg.query(0, i+1), seg.query(i+2, N))
        ans = max(ans, tmp)
    ans = max(ans, seg.query(0, N-1))

    print(ans)

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


class SegmentTree:
    
    def __init__(self, n, initial=0):
        """
        n: 配列の大きさ
        initial: 単位元 (RMQでは大きな値)
        """
        self.offset = 2**(n-1).bit_length()  
        self.initial = initial
        self.seg = [self.initial] * (2 * self.offset)
        

    def build(self, A):
        """
        A: 処理したい配列
        """
        for i, a in enumerate(A, start=self.offset):
            self.seg[i] = a
        for i in range(self.offset-1,0,-1):
            self.seg[i] = gcd(self.seg[i<<1] ,self.seg[(i<<1)+1])

            
    def update(self, k, a):
        """
        k番目の値をaに変更
        """
        k += self.offset
        self.seg[k] = a
        while k:
            k >>= 1
            self.seg[k] = gcd(self.seg[k<<1], self.seg[(k<<1)+1])

            
    def query(self, a, b):
        """
        区間[a, b)に対して最小公倍数を求める
        """
        a += self.offset
        b += self.offset - 1 
        res = self.initial
        while a < b:
            if a & 1:  
                res = gcd(res, self.seg[a])
                a += 1
            if not b & 1:  
                res = gcd(res, self.seg[b])
                b -= 1
            a >>= 1
            b >>= 1
        
        if a == b:
            res = gcd(res, self.seg[a])
        
        return res


if __name__ == "__main__":
    N = int(readline())
    A = [int(i) for i in readline().split()]
    seg = SegmentTree(N)
    seg.build(A)

    ans = seg.query(1, N)
    for i in range(N-2):
        tmp = gcd(seg.query(0, i+1), seg.query(i+2, N))
        ans = max(ans, tmp)
    ans = max(ans, seg.query(0, N-1))

    print(ans)

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

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

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

R.reverse()

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

print(ans)

Solution (Python):
"""
AtCoder Beginner Contest 125  C - GCD on Blackboard

配列中の数字を一つ好きな値に書き換えて最大公約数を計算するときの最大値を求める
・書き換える→取り除くと考えてよい。
・全体のGCD = GCD(前半のGCD, 後半のGCD) のように、分割したり順番を入れ替えたりしても結果は変わらない。
なので、左からの累積GCDと、右からの累積GCDをあらかじめとっておくことで、要素を一個除いたときの全体のGCDも求められる。　

区間に対する処理 -> セグメント木いけるやん
"""
class SegmentTree:
    
    def __init__(self, lst, ide_ele, segfunc):
        self.ide_ele = ide_ele
        self.func = segfunc
        
        self.size = 2**(len(lst) - 1).bit_length()
        self.seg_lst = [self.ide_ele] * 2 * self.size

        """
        値を詰めていく
        ノードiの親：(i-1) // 2
        ノードiの子：2*i+1 と　2*i+2

        """
        for i in range(len(lst)):
            self.seg_lst[i + self.size - 1] = lst[i]

        
        
        for i in range(self.size-2, -1, -1):
            
            self.seg_lst[i] = self.func(self.seg_lst[2*i + 1], self.seg_lst[2*i + 2])

    def update(self, i, num):
        
        i += self.size - 1
        self.seg_lst[i] = num
        while i:
            
            i = (i - 1) // 2
            self.seg_lst[i] = self.func(self.seg_lst[2*i + 1], self.seg_lst[2*i + 2])

    def query(self, l, r):
        
        if r <= l:
            return self.ide_ele

        
        l += self.size - 1
        
        r += self.size - 2
        ret = self.ide_ele
        
        while r - l > 1:
            
            if l & 1 == 0:
                
                ret = self.func(ret, self.seg_lst[l])
            
            if r & 1 == 1:
                
                ret = self.func(ret, self.seg_lst[r])
                r -= 1

            
            l = l // 2
            r = (r - 1) // 2

        
        if l == r:
            ret = self.func(ret, self.seg_lst[l])
        else:
            ret = self.func(self.func(ret, self.seg_lst[l]), self.seg_lst[r])
        
        return ret

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

seg_tree = SegmentTree(A, 0, gcd)

ans = -1

for i in range(N):
    
    ans = max(ans, gcd(seg_tree.query(0, i), seg_tree.query(i+1, N)))

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)

ans = 0
for i in range(n):
    ans = max(ru.fold(i), ans)
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)

ans = 0
for i in range(n):
    ans = max(ru.fold(i), ans)
print(ans)

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

L = {}
R = {}

L[0] = A[0]

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

R[n-1] = A[n-1]

for i in range(n-1):
  R[n-2-i] = gcd(R[n-1-i], A[n-2-i])
  
  
max_gcd = 0
for i in range(1, n-1):
  max_gcd = max(gcd(L[i-1], R[i+1]), max_gcd)
  
max_gcd = max((max_gcd, L[n-2], R[1]))
print(max_gcd)

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)

def ruiseki_lr(array):
    """左右からの畳み込みをそれぞれ計算する
    left[p]  := 区間[0, p)の畳み込み
    right[p] := 区間[p, n)の畳み込み
    """
    op = lambda a, b: gcd(a, b)
    e = 0

    n = len(array)
    left = [e] * (n + 1)
    right = [e] * (n + 1)

    for i in range(n):
        left[i + 1] = op(left[i], array[i])
    for i in reversed(range(n)):
        right[i] = op(right[i + 1], array[i])

    return left, right



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

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

Solution (Python):





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


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

    g = A[0]
    L = [g]
    for i in range(N - 1):
        g = gcd(g, A[i + 1])
        L.append(g)

    g = A[N - 1]
    R = [g]
    for i in range(N - 1):
        g = gcd(g, A[N - 2 - i])
        R.append(g)

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

    print(result)


if __name__ == "__main__":
    main()

Solution (Python):


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

def gcd_all(lst):
    g = gcd(lst[0], lst[1])
    for e in lst[2:]:
        g = gcd(g, e)
    return g


def submit():
    n = int(input())
    alist = list(map(int, input().split()))

    if n == 2:
        print(max(alist))
    else:
        
        gcd_left = [alist[0]]
        for a in alist[1:]:
            gcd_left.append(gcd(gcd_left[-1], a))
        
        
        gcd_right = [alist[-1]]
        for a in reversed(alist[:-1]):
            gcd_right.append(gcd(gcd_right[-1], a))
        gcd_right = gcd_right[::-1]

        gcd_max = 0
        for i in range(n):
            if i == 0:
                gcd_i = gcd_right[i + 1]
            elif i == n - 1:
                gcd_i = gcd_left[i - 1]
            else:
                gcd_i = gcd(gcd_left[i - 1], gcd_right[i + 1])

            if gcd_max < gcd_i:
                gcd_max = gcd_i

        print(gcd_max)


if __name__ == "__main__":
    submit()

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]

import fractions
rgcd = [0]
lgcd = [0]
for i in range(N) :
    rgcd.append(fractions.gcd(rgcd[i], A[i]))
for i in range(N) :
    lgcd.append(fractions.gcd(lgcd[i], A[-1-i]))

lgcd.reverse()
ans = []
for i in range(N) :
    ans.append(fractions.gcd(rgcd[i], lgcd[i+1]))

print(max(ans))

Solution (Python):
from fractions import gcd

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

gcdl = [1]*N
gcdl[0] = A[0]

gcdr = [1]*N
gcdr[-1] = A[-1]

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

res = max(gcdl[N-2], gcdr[1])

for i in range(1, N-1):
    res = max(gcd(gcdl[i-1], gcdr[i+1]), res)

print(res)

Solution (Python):
from fractions import gcd

class SegTree:
    def __init__(self, N, A, f, e):
        """
        N: A の要素数
        A: セグ木に乗せたい配列
        f: 二項演算 (モノイドじゃなきゃだめ)
        e: f の単位元
        """
        n = 2**(N-1).bit_length() 
        c = [e] * (2*n)

        for i in range(N):
            c[i+n] = A[i] 
        
        for i in range(n-1, 0, -1):
            c[i] = f(c[i<<1|0], c[i<<1|1]) 
        
        self.n = n 
        self.c = c 
        self.e = e
        self.f = f
    
    def update(self, k, x):
        k += self.n
        self.c[k] = x 

        
        while k > 1:
            k >>= 1
            self.c[k] = self.f(self.c[k<<1|0], self.c[k<<1|1])

    def query(self, l, r):
        res = self.e
        l += self.n; r += self.n 

        while l < r: 
            if l & 1: 
                res = self.f(res, self.c[l]) 
                l += 1 

            if r & 1: 
                r -= 1 
                res = self.f(res, self.c[r]) 

            l >>= 1; r >>= 1 
        
        return res

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

seg = SegTree(N, A, gcd, 0)

res = 0
for i in range(N):
    res = max(res, gcd(seg.query(0, i), seg.query(i+1, N)))

print(res)

Solution (Python):
from fractions import gcd


class SegmentTree:
    def __init__(self, n, init_value, ide_ele):
        self.num = 2 ** (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.seg = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.seg[i + self.num - 1] = init_value[i]
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])
    
    def update(self, _k, x):
        k = _k + self.num - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])
    
    def query(self, _p, _q):
        p = _p
        q = _q
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while 1 < q - p:
            if p & 1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q & 1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res
    
    @staticmethod
    def segfunc(a, b):
        return gcd(a, b)


def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    seg_tree = SegmentTree(N, A, 0)
    ans = -1
    for i in range(N):
        ans = max(ans, gcd(seg_tree.query(0, i), seg_tree.query(i + 1, N)))
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
from fractions import gcd

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

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

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

ans = 0

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

Solution (Python):




class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 0:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)
    


def AOJ_DSL_2_A():
    n, q = map(int, input().split())
    e = (1 << 31) - 1
    A = [e] * n
    seg = SegmentTree(A, min, e)

    for i in range(q):
        t, x, y = map(int, input().split())
        if t == 0:
            seg.update(x, y)
        else:
            print(seg.get(x, y + 1))



def AOJ_DSL_2_B():
    from operator import add
    import sys
    n, q = map(int, input().split())
    e = 0
    A = [e] * n
    seg = SegmentTree(A, add, e)
    
    query = sys.stdin.readlines()
    for i in range(q):
        t, x, y = map(int, query[i].split())
        x -= 1
        if t == 0:
            A[x] += y
            seg.update(x, A[x])
        else:
            y -= 1
            print(seg.get(x, y + 1))


def ABC125_C():
    from fractions import gcd
    N = int(input())
    A = list(map(int, input().split()))
    
    seg = SegmentTree(A, gcd, 0)
    ans = 0
    for i in range(N):
        ans = max(ans, gcd(seg.get(0, i), seg.get(i + 1, N)))
    print(ans)




ABC125_C()

Solution (Python):




class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n - 1)
        for i in range(len(A)):
            self.__node[i + n - 1] = A[i]
        for i in range(n - 2, -1, -1):
            self.__node[i] = self.__dot(self.__node[2 * i + 1], self.__node[2 * i + 2])
    
    def update(self, i, c):
        i += self.__n - 1
        node = self.__node
        node[i] = c
        while i > 0:
            i = (i - 1) // 2
            node[i] = self.__dot(node[2 * i + 1], node[2 * i + 2])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n - 1
        r += self.__n - 1
        while (l < r):
            if (l % 2 == 0):
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l = (l - 1) // 2
            if (r % 2 == 0):
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r = (r - 1) // 2
        return self.__dot(vl, vr)
    


def AOJ_DSL_2_A():
    n, q = map(int, input().split())
    e = (1 << 31) - 1
    A = [e] * n
    seg = SegmentTree(A, min, e)

    for i in range(q):
        t, x, y = map(int, input().split())
        if t == 0:
            seg.update(x, y)
        else:
            print(seg.get(x, y + 1))



def AOJ_DSL_2_B():
    from operator import add
    import sys
    n, q = map(int, input().split())
    e = 0
    A = [e] * n
    seg = SegmentTree(A, add, e)
    
    query = sys.stdin.readlines()
    for i in range(q):
        t, x, y = map(int, query[i].split())
        x -= 1
        if t == 0:
            A[x] += y
            seg.update(x, A[x])
        else:
            y -= 1
            print(seg.get(x, y + 1))


def ABC125_C():
    from fractions import gcd
    N = int(input())
    A = list(map(int, input().split()))
    
    seg = SegmentTree(A, gcd, 0)
    ans = 0
    for i in range(N):
        ans = max(ans, gcd(seg.get(0, i), seg.get(i + 1, N)))
    print(ans)



ABC125_C()

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

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)

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)

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

def main():
    n=int(input())
    a=list(map(int,input().split()))
    f,b=[0]*(n+2),[0]*(n+2)
    f[1],b[n]=a[0],a[-1]
    for i in range(2,n+1):
        f[i],b[n-i+1]=gcd(a[i-1],f[i-1]),gcd(a[n-i],b[n-i+2])
    ans=0
    for i in range(1,n+1):
      ans=max(ans,gcd(f[i-1],b[i+1]))
    print(ans)
    
if __name__ == '__main__':
    main()

Solution (Python):
import fractions
num = int(input())
numarray = [int(i) for i in input().split()]

result_f = numarray[:] + [0]
result_t = [0] + numarray[:]
for i in range(num):
    result_f[num-i-1] = fractions.gcd(result_f[num-i], numarray[num-i-1])
    result_t[i+1] = fractions.gcd(result_t[i], result_t[i+1])

gcd_result = []
for i in range(num):
    gcd_result.append(fractions.gcd(result_t[i], result_f[i+1]))

print(max(gcd_result))

Solution (Python):
def main():
  import sys
  import fractions
  input = sys.stdin.readline
  n=int(input())
  a=list(map(int,input().split()))
  l,r=[0]*(n-1),[0]*(n-1)
  for i in range(n-1):
    l[i]=fractions.gcd(l[i-1],a[i]) 
    r[i]=fractions.gcd(r[i-1],a[n-1-i])
  x=[0]*n
  for i in range(n):
    if i==0:
      x[i]=r[-1]
    elif i==(n-1):
      x[i]=l[-1]
    else:
      x[i]=fractions.gcd(l[i-1],r[n-2-i])
  print(max(x)) 
if __name__=='__main__':
  main()

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):
n = int(input())
a = list(map(int, input().split()))

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

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

ans = max(gl[n-2], gr[n-2])
for i in range(1, n-1):
    ans = max(ans, gcd(gl[i-1], gr[n-2-i]))

print(ans)

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

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

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


import fractions


left=[0 for i in range(n)]
right=[0 for i in range(n)]
left[0]=al[0]
right[n-1]=al[n-1]

for i in range(1,n):
    left[i]=(fractions.gcd(al[i],left[i-1]))

for i in range(n-2,-1,-1):
    right[i]=fractions.gcd(al[i],right[i+1])
    
ansl=[]

ansl.append(right[1])

ansl.append(left[n-2])

for i in range(1,n-1):
    ansl.append(fractions.gcd(left[i-1],right[i+1]))
print(max(ansl))

Solution (Python):

import fractions

n = int(input().rstrip())
numbers = [int(i) for i in input().rstrip().split(" ")]

l_list = [0 for i in range(n)]
l_list[0] = numbers[0]
for i in range(1, n):
    l_list[i] = fractions.gcd(l_list[i-1], numbers[i])

r_list = [0 for i in range(n)]
r_list[n-1] = numbers[n-1]
for i in reversed(range(0, n - 1)):
    r_list[i] = fractions.gcd(r_list[i+1], numbers[i])

ans = 0
for i in range(n):
    l = 0
    if i > 0:
        l = l_list[i - 1]
    r = 0
    if i < n - 1:
        r = r_list[i + 1]
    if l == 0:
        l = r
    if r == 0:
        r = l
    ans = max(ans, fractions.gcd(l, r))
print(ans)

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):
from fractions import gcd

n = int(input())
a = [int(i) for i in input().split()]

gcd_to = [0] + a[:]
gcd_from = a[:] + [0]
for i in range(1, n+1):
    gcd_to[i] = gcd(gcd_to[i-1], gcd_to[i])
    gcd_from[n-i] = gcd(gcd_from[n-i+1], a[n-i])

gcd_exclude = []
for i in range(n):
    gcd_exclude.append(gcd(gcd_to[i], gcd_from[i+1]))

print(max(gcd_exclude))

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):
from fractions import gcd
n = int(input())
A = list(map(int, input().split()))
ans = 0
l = [A[0]]
r = [A[n-1]]
for i in range(1, n):
    l.append(gcd(l[i-1], A[i]))
    r.append(gcd(r[i-1], A[n-i-1]))
r.reverse()

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

print(ans)

Solution (Python):
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
Asort = sorted(A)[:: -1]
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])
	R[i] = gcd(R[i - 1], A[N - 1 - i])
ans = max(L[N - 2], R[N - 2])
for j in range(1, N - 1):
	ans = max(ans, gcd(L[j - 1], R[N - j - 2]))
print(ans)