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.



Sample input:
3
7 6 8


Sample output:
2

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

# from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush
# from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
import math
# from itertools import product, accumulate, combinations, product
#import bisect
# import numpy as np
# from copy import deepcopy
#from collections import deque
# from decimal import Decimal
# from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())

class segtree:
    '''init_val : i-indexed (init_val[0] = self.bin[1])'''
    def __init__(self, n, init = 0, init_val=None):
        self.n = n
        self.init = init
        self.k = math.ceil(math.log2(n))
        self.add_val = 1 << self.k

        self.bins = [self.init] * (1 << (self.k + 1))
        if init_val != None:
            self.update_set(init_val)
        self.caliculate()

    def __getitem__(self, idx):  # return idx-value
        return self.bins[idx + self.add_val]

    def update_set(self, vals):
        for idx, i in enumerate(range(self.add_val, self.add_val * 2)):
            if len(vals) > idx:
                self.bins[i] = vals[idx]
            else:continue

    def compare(self, l, r):
        return math.gcd(l, r)

    def caliculate(self):
        k = self.k
        while k:
            for i in range(1<<k, 1<<(k+1)):
                if not i%2:
                    self.bins[i//2] = self.compare(self.bins[i], self.bins[i+1])
                else:continue
            k -= 1

    def update(self, idx, val, by=True):
        '''idx : 0-started index'''
        k = (1<<self.k) + idx
        if by:
            self.bins[k] += val
        else:
            self.bins[k] = val
        while k>1:
            self.bins[k // 2] = self.compare(self.bins[k // 2 * 2], self.bins[k // 2 * 2 + 1])
            k = k//2


    def eval(self, l, r):
        if l == r:
            return self.bins[self.add_val + l]
        ret = self.init
        l = (1 << self.k) + l
        r = (1 << self.k) + r
        #print(l, r)
        while True:
            #print(l, r)
            if r - l == 1:
                ret = self.compare(ret, self.bins[l])
                ret = self.compare(ret, self.bins[r])
                break
            elif l == r:
                ret = self.compare(ret, self.bins[l])
                break
            else:
                done = False
                if l % 2:
                    ret = self.compare(ret, self.bins[l])
                    l += 1
                    done = True
                if not r % 2:
                    ret = self.compare(ret, self.bins[r])
                    r -= 1
                    done = True
                if not done:
                    l = l // 2
                    r = r // 2
        #print(ret)
        return ret



def run():
    N, *A = mapread()
    t = segtree(N, init = 0, init_val = A)

    ans = 0
    for i in range(N):
        if i > 0:
            a = t.eval(0, i-1)
        else:
            a = 0
        if i < N-1:
            b = t.eval(i+1, N-1)
        else:
            b = 0
        ans = max(ans, math.gcd(a, b))
    print(ans)


if __name__ == "__main__":
    #print(math.gcd(0, 10))
    run()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
from collections import deque
from math import gcd
a_left=deque()

a_left.append(a[0])


a_right=deque()

a_right.append(a[-1])

for i in range(n-1):
    a_left.append(gcd(a_left[-1],a[i+1]))
    a_right.appendleft(gcd(a_right[0],a[n-i-2]))


a_right=list(a_right)
a_left=list(a_left)

count=max(a_left[-2],a_right[1])

for j in range(n-2):
    count=max(gcd(a_left[j],a_right[j+2]),count)
print(count)

Submission status: Accepted

Solution code:
import math
from collections import deque
N = int(input())
A = list(map(int,input().split()))

M = 0
L = deque([0])
R = deque([0])
for i in range(1,N+1):
    L.append(math.gcd(L[-1],A[i-1]))
    R.appendleft(math.gcd(R[0],A[N-i]))
for j in range(N):
    m = math.gcd(L[j],R[j+1])
    M = max(M,m)
print(M)

Submission status: Accepted

Solution code:
# 解説を参考に作成
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque

def gcd(a, b):
    """最大公約数"""
    a, b = (a, b) if a >= b else (b, a)
    if b == 0:
        return a
    return gcd(b, a % b)


# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, A):
    L = [0] * N
    L[0] = A[0]
    for i in range(1, N):
        L[i] = gcd(A[i], L[i - 1])
    R = [0] * N
    R[-1] = A[-1]
    for i in range(1, N):
        R[-(i + 1)] = gcd(A[-(i + 1)], R[-i])
    ans = 0
    for i in range(N):
        if i == 0:
            ans = max(ans, R[i + 1])
        elif i == N - 1:
            ans = max(ans, L[i - 1])
        else:
            ans = max(ans, gcd(L[i - 1], R[i + 1]))
    print(ans)


if __name__ == '__main__':
    # S = input()
    N = int(input())
    # N, M = map(int, input().split())
    A = [int(i) for i in input().split()]
    # B = [int(i) for i in input().split()]
    # AB = [[int(i) for i in input().split()] for _ in range(N)]
    solve(N, A)

    # # test
    # from random import randint
    # from func import random_str
    # solve()

Submission status: Accepted

Solution code:
from math import gcd
class SparseTable:
    def __init__(self,arr,N,op,e):
        self.A=arr
        self.N=N
        self.Unit=e
        self.Op=op
        self.K=N.bit_length()-1
        self.pow2=[1]
        for i in range(self.K):
            self.pow2.append(self.pow2[-1]*2)
        self.ST=[[self.Unit]*(self.K+1) for i in range(N)]
        for i in range(N):
            self.ST[i][0]=self.A[i]
        for i in reversed(range(N)):
            for k in range(1,self.K+1):
                if self.N<i+self.pow2[k]:
                    break
                self.ST[i][k]=self.Op(self.ST[i][k-1],self.ST[i+self.pow2[k-1]][k-1])
    def get(self,l,r):
        if l==r:
            return self.Unit
        x=r-l
        t=x.bit_length()-1
        return self.Op(self.ST[l][t],self.ST[r-self.pow2[t]][t])

N=int(input())

A=list(map(int,input().split()))
ST=SparseTable(A,N,gcd,0)
ans=1
for i in range(N):
    l,r=ST.get(0,i),ST.get(i+1,N)
    ans=max(ans,gcd(l,r))
print(ans)

Submission status: Accepted

Solution code:
from typing import Callable, Iterator, Optional, TypeVar

S = TypeVar("S")


class SegmentTree:
    """Segment Tree
    References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp
    """

    __slots__ = ["_e", "_op", "_n", "_size", "_tree"]

    def __init__(
        self,
        initial_values: Optional[Iterator[S]],
        n: int,
        e: S,
        op: Callable[[S, S], S],
    ) -> None:
        self._e = e
        self._op = op
        self._n = n
        self._size = 1 << (self._n - 1).bit_length()

        self._tree = [e] * 2 * self._size
        if initial_values is None:
            return

        for i, initial_values in enumerate(initial_values, self._size):
            self._tree[i] = initial_values
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def _update(self, k: int) -> None:
        """Update the value of a[k]."""
        self._tree[k] = self._op(self._tree[2 * k], self._tree[2 * k + 1])

    def set(self, k: int, x: S) -> None:
        """Assign x to a[k] in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        self._tree[k] = x
        while k:
            k >>= 1
            self._update(k)

    def get(self, k: int) -> S:
        """Return a[k] in O(1)."""
        assert 0 <= k < self._n
        return self._tree[k + self._size]

    def prod(self, l: int, r: int) -> S:
        """Return op(a[l], ..., a[r - 1]). Return e, if l == r.
        Complexity: O(log n)
        """
        assert 0 <= l <= r <= self._n

        sml, smr = self._e, self._e
        l += self._size
        r += self._size

        while l < r:
            if l & 1:
                sml = self._op(sml, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self._op(self._tree[r], smr)
            l >>= 1
            r >>= 1
        return self._op(sml, smr)

    def prod_all(self) -> S:
        """Return op(a[0], ..., a[n - 1]. Return e if n == 0.
        Complexity: O(1)
        """
        return self._tree[1]

    def max_right(self, l: int, f: Callable[[S], bool]) -> int:
        """
        Return an index r satisfying both:
            1. r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. r = n or f(op(a[l], a[l + 1], ..., a[r])) = false.

        If f is monotone, this is the maximum r satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= l <= self._n
        assert f(self._e)

        if l == self._n:
            return self._n

        l += self._size
        sm = self._e

        while True:
            while not l & 1:
                l >>= 1

            if not f(self._op(sm, self._tree[l])):
                while l < self._size:
                    l *= 2
                    if f(self._op(sm, self._tree[l])):
                        sm = self._op(sm, self._tree[l])
                        l += 1
                return l - self._size

            sm = self._op(sm, self._tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self._n

    def min_left(self, r: int, f: Callable[[S], bool]) -> int:
        """
        Return an index l satisfying both:
            1. l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. l = 0 or f(op(a[l - 1], a[l + 1], ..., a[r - 1])) = false.
        If f is monotone, this is the minimum l satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= r <= self._n
        assert f(self._e)

        if not r:
            return 0

        r += self._size
        sm = self._e

        while True:
            r -= 1
            while r > 1 and r & 1:
                r >>= 1

            if not f(self._op(self._tree[r], sm)):
                while r < self._size:
                    r = 2 * r + 1
                    if f(self._op(self._tree[r], sm)):
                        sm = self._op(self._tree[r], sm)
                        r -= 1
                return r + 1 - self._size

            if (r & -r) == r:
                break

        return 0


def staticrmq():
    # https://judge.yosupo.jp/problem/staticrmq
    import sys

    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline

    N, _ = map(int, readline().split())
    A = map(int, readline().split())
    LR = map(int, read().split())
    tree = SegmentTree(A, N, (10 ** 10) + 1, min)
    res = [tree.prod(l, r) for l, r in zip(*[iter(LR)] * 2)]
    print("\n".join(map(str, res)))


def practice2_j():
    # https://atcoder.jp/contests/practice2/tasks/practice2_j
    import sys

    readline = sys.stdin.readline

    N, Q = map(int, readline().split())
    A = map(int, readline().split())
    tree = SegmentTree(A, N, -1, max)
    res = []
    for _ in range(Q):
        t, x, y = map(int, readline().split())
        if t == 1:
            tree.set(x - 1, y)
        elif t == 2:
            res.append(tree.prod(x - 1, y))
        else:
            res.append(tree.max_right(x - 1, lambda n: n < y) + 1)
    print("\n".join(map(str, res)))


def dsl_2_a():
    # https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_A
    N, Q, *X = map(int, open(0).read().split())
    tree = SegmentTree(None, N, 2 ** 31 - 1, min)
    res = []
    for com, x, y in zip(*[iter(X)] * 3):
        if com:
            res.append(tree.prod(x, y + 1))
        else:
            tree.set(x, y)
    print("\n".join(map(str, res)))


def abc125_c():
    # https://atcoder.jp/contests/abc125/tasks/abc125_c
    from math import gcd

    N, *A = map(int, open(0).read().split())
    tree = SegmentTree(A, N, 0, gcd)
    res = max(gcd(tree.prod(0, i), tree.prod(i + 1, N)) for i in range(N))
    print(res)


if __name__ == "__main__":
    # staticrmq()
    # practice2_j()
    # dsl_2_a()
    abc125_c()

Submission status: Accepted

Solution code:
from math import gcd

class SegmentTree:
    """Segment Tree

    Attributes:
        n (int):       要素数
        num (int):     n以上の最小の2の累乗
        ide_ele (int): 単位元
            - RmQ(Range Minimum Query): inf
            - RMQ(Range Maximum Query): -1
            - RSQ(Range Sum Query):     0
            - RPQ(Range Product Query): 1
            - RGQ(Range GCD Query):     0
        seg (list):    要素の格納先
    """
    def __init__(self, a):
        """初期化 O(N)
        
        Args:
            a (list): 対象の配列
        """
        self.n = len(a)
        self.num = 2 ** (self.n - 1).bit_length()
        self.ide_ele = 0
        self.seg = [self.ide_ele] * (2*self.num-1)

        for i in range(self.n):
            self.seg[self.num+i-1] = a[i]    
        for i in range(self.num-2, -1, -1) :
            self.seg[i] = self.st_func(self.seg[2*i+1], self.seg[2*i+2])

    def query(self, l, r):
        """区間クエリの計算 O(logN)

        Args:
            l (int): 区間の左端
            r (int): 区間の右端
        
        Returns:
            int: [l, r)についての区間クエリ
        """
        if r <= l:
            return self.ide_ele
        
        l += self.num - 1
        r += self.num - 2
        res = self.ide_ele

        while r - l > 1:
            if l % 2 == 0:
                res = self.st_func(res, self.seg[l])
            if r % 2 == 1:
                res = self.st_func(res, self.seg[r])
                r -= 1
            l = l // 2
            r = (r - 1) // 2
        
        if l == r:
            res = self.st_func(res, self.seg[l])
        else:
            res = self.st_func(res, self.st_func(self.seg[l], self.seg[r]))
        
        return res

    def update(self, i, v):
        """値の更新 O(logN)

        Args:
            i (int): 更新対象のindex
            v (int): 更新値
        """
        i += self.num - 1
        self.seg[i] = v
        while i > 0:
            i = (i - 1) // 2
            self.seg[i] = self.st_func(self.seg[i*2+1], self.seg[i*2+2])
    
    def st_func(self, x, y):
        """問題に応じた処理

        Returns:
            int: 問題に応じた値
                - RmQ(Range Minimum Query): min(x, y)
                - RMQ(Range Maximum Query): max(x, y)
                - RSQ(Range Sum Query):     x + y
                - RPQ(Range Product Query): x * y
                - RGQ(Range GCD Query):     gcd(x, y)
        """
        return gcd(x, y)


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

st = SegmentTree(a)

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

print(res)

Submission status: Accepted

Solution code:
from math import gcd

# segfunc: 問題に応じて設定
def segfunc(x, y):
    return gcd(x, y)


# 配列aで初期化
def init(a):
    for i in range(n):
        seg[i+num-1] = a[i]    
    for i in range(num-2, -1, -1) :
        seg[i] = segfunc(seg[2*i+1], seg[2*i+2]) 


# a[k]の値をxに更新
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])


# [p, q)についてsegfuncを適用したものを返す
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(res, segfunc(seg[p], seg[q]))
    
    return res


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

ide_ele = 0
num = 2 ** (len(bin(n - 1)) - 2)
seg = [ide_ele] * 2 * num
init(a)

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

print(res)

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))
all_factor = [0 for _ in range(N)]

#%%
from math import gcd
from_right = [0 for _ in range(N)]
from_left = [0 for _ in range(N)]

from_right[-1] = As[-1]
from_left[0] = As[0]

for i in range(N-1):
    from_left[i+1] = gcd(from_left[i], As[i+1])
for i in list(range(N-1))[::-1]:
    from_right[i] = gcd(from_right[i+1], As[i])

answer = 1
for i in range(N):
    if i == 0:
        temp = from_right[1]
    elif i == N-1:
        temp = from_left[N-2]
    else:
        temp = gcd(from_left[i-1],from_right[i+1])
    
    if temp > answer:
        answer = temp
print(answer)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#C - GCD on Blackboard
import sys 
from math import gcd
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = [0] + list(map(int, readline().split()))
# L(i) := A1, A2, ..., Ai-1の最大公約数
# R(i) := Ai, Ai+1, ..., ANの最大公約数
L = [0]*(N+1)
L[0] = 0
R = [0]*(N+2)
R[N+1] = 0

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

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

Submission status: Accepted

Solution code:
def gcd(a,b):
    if a == 0 or b == 0:
        return max(a,b)
    return a if b==0 else gcd(b,a%b)
N = int(input())
A = list(map(int,input().split()))
rA = A[::-1]

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


RIGHT = [0]
g = rA[0]
for i in range(N):
    g = gcd(g,rA[i])
    RIGHT.append(g)


ans = 0
for i in range(1,N+1):
    ans = max(ans,gcd(LEFT[i-1],RIGHT[N-i]))
print(ans)

Submission status: Accepted

Solution code:
from math import *

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

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

ans = l[n-2]
r = a[n-1]
for i in range(n-2,0,-1):
  r = gcd(r, a[i+1])
  ans = max(ans, gcd(l[i-1], r))
ans = max(ans, gcd(r,a[1]))
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter
#from heapq import heappush, heappop
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ni()
A = na()
b = [0] * N
c = [0] * N
b[0] = A[0]
c[-1] = A[-1]
for i in range(N-1):
    b[i+1] = math.gcd(b[i], A[i+1])
    c[-(i+2)] = math.gcd(c[-(i+1)], A[-(i+2)])

ans = 1
ans = max(c[1], ans)
ans = max(b[-2], ans)
for i in range(1, N-1):
    ans = max(math.gcd(b[i-1], c[i+1]), ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = 0

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

L = [0]
R = 0

for i in range(N-1):
  L.append(gcd(A[i], L[i]))
for i in range(N):
  temp = gcd(L[N-i-1], R)
  R = gcd(R, A[N-i-1])
  if ans < temp:
    ans = temp
    
print(ans)

Submission status: Accepted

Solution code:
import math

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

def segfunc(x, y):
    return math.gcd(x,y)

def init(init_val):
    # set_val
    for i in range(n):
        seg[i+num-1] = init_val[i]
    # built
    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[2*k+1], seg[2*k+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

# identity element
ide_ele = 0

# num: n以上の最小の2のべき乗
num = 2**(n-1).bit_length()
seg = [ide_ele]*2*num

a=init(a)

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


print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
d={}
for i,j in enumerate(a):
    if i<2:
        k=1
        while 1:
            if k*k>j: break
            if j%k==0:
                if k in d:
                    d[k]+=1
                else:
                    d[k]=1
            if j%k==0 and k*k!=j:
                if j//k in d:
                    d[j//k]+=1
                else:
                    d[j//k]=1
            k+=1
    else:
        for k in d:
            if j%k==0:
                if k in d:
                    d[k]+=1
            elif j%k==0 and k*k!=j:
                if j//k in d:
                    d[j//k]+=1
#print(d)
ans=chk=0
for i in d:
    if d[i]>=n-1:
        ans=max(ans,i)
print(ans)

Submission status: Accepted

Solution code:
from math import *

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from math import gcd

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

    forward = [0] * (n+1)
    forward[0] = a[0]
    for i in range(n):
        forward[i+1] = gcd(forward[i], a[i])

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

    ans = max(forward[n-1], backward[1])
    for i in range(1, n-1):
        candidate = gcd(forward[i], backward[i+1])
        if ans < candidate:
            ans = candidate

    print(ans)

main()

Submission status: Accepted

Solution code:
from typing import Callable, List, Optional, Union

T = Union[int, str]


class SegmentTree:
    """Segment Tree"""

    __slots__ = ["e", "op", "modifying_op", "_n", "_size", "tree"]

    def __init__(
        self,
        a: List[T],
        e: T,
        op: Callable[[T, T], T],
        modifying_op: Optional[Callable[[T], T]] = None,
    ) -> None:
        self.e = e
        self.op = op
        self.modifying_op = modifying_op
        self._n = len(a)
        self._size = 1 << (self._n - 1).bit_length()

        if modifying_op:
            a = map(modifying_op, a)
        self.tree = [e] * self._size + a + [e] * (self._size - self._n)
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def _update(self, k: int) -> None:
        """Update the value of a[k]."""
        self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])

    def set(self, k: int, x: T) -> None:
        """Assign x to a[k] in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        if self.modifying_op:
            x = self.modifying_op(x)
        self.tree[k] = x
        while k:
            k >>= 1
            self._update(k)

    def get(self, k: int) -> T:
        """Return a[k] in O(1)."""
        assert 0 <= k < self._n
        return self.tree[k + self._size]

    def prod(self, l: int, r: int) -> T:
        """Return op(a[l], ..., a[r - 1]). Return e, if l == r.
        Complexity: O(log n)
        """
        assert 0 <= l <= r <= self._n

        sml, smr = self.e, self.e
        l += self._size
        r += self._size

        while l < r:
            if l & 1:
                sml = self.op(sml, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.tree[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def prod_all(self) -> T:
        """Return op(a[0], ..., a[n - 1]. Return e if n == 0.
        Complexity: O(1)
        """
        return self.tree[1]

    def max_right(self, l: int, f: Callable[[T], bool]) -> int:
        """
        Return an index r satisfying both:
            1. r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. r = n or f(op(a[l], a[l + 1], ..., a[r])) = false.

        If f is monotone, this is the maximum r satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= l <= self._n
        assert f(self.e)

        if l == self._n:
            return self._n

        l += self._size
        sm = self.e

        while True:
            while not l & 1:
                l >>= 1

            if not f(self.op(sm, self.tree[l])):
                while l < self._size:
                    l *= 2
                    if f(self.op(sm, self.tree[l])):
                        sm = self.op(sm, self.tree[l])
                        l += 1
                return l - self._size

            sm = self.op(sm, self.tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self._n

    def min_left(self, r: int, f: Callable[[T], bool]) -> int:
        """
        Return an index l satisfying both:
            1. l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            2. l = 0 or f(op(a[l - 1], a[l + 1], ..., a[r - 1])) = false.
        If f is monotone, this is the minimum l satisfying:
            f(op(a[l], a[l + 1], ..., a[r - 1])) = true.

        Complexity: O(log n)
        """
        assert 0 <= r <= self._n
        assert f(self.e)

        if not r:
            return 0

        r += self._size
        sm = self.e

        while True:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1

            if not f(self.op(self.tree[r], sm)):
                while r < self._size:
                    r = 2 * r + 1
                    if f(self.op(self.tree[r], sm)):
                        sm = self.op(self.tree[r], sm)
                        r -= 1
                return r + 1 - self._size

            if (r & -r) == r:
                break

        return 0


def practice2_j():
    # https://atcoder.jp/contests/practice2/tasks/practice2_j
    N, _, *AQ = map(int, open(0).read().split())
    A, Q = AQ[:N], AQ[N:]
    tree = SegmentTree(A, -1, max)
    res = []
    for t, x, y in zip(*[iter(Q)] * 3):
        if t == 1:
            tree.set(x - 1, y)
        elif t == 2:
            res.append(tree.prod(x - 1, y))
        else:
            res.append(tree.max_right(x - 1, lambda n: n < y) + 1)
    print("\n".join(map(str, res)))


def staticrmq():
    # https://judge.yosupo.jp/problem/staticrmq
    N, Q, *ALR = map(int, open(0).read().split())
    A, LR = ALR[:N], ALR[N:]
    tree = SegmentTree(A, (10 ** 10) + 1, min)
    res = [tree.prod(l, r) for l, r in zip(*[iter(LR)] * 2)]
    print("\n".join(map(str, res)))


def dsl_2_a():
    # https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_A
    N, Q, *X = map(int, open(0).read().split())
    tree = SegmentTree([2 ** 31 - 1] * N, 2 ** 31 - 1, min)
    res = []
    for com, x, y in zip(*[iter(X)] * 3):
        if com:
            res.append(tree.prod(x, y + 1))
        else:
            tree.set(x, y)
    print("\n".join(map(str, res)))


def abc125_c():
    # https://atcoder.jp/contests/abc125/tasks/abc125_c
    from math import gcd

    N, *A = map(int, open(0).read().split())
    tree = SegmentTree(A, 0, gcd)
    res = max(gcd(tree.prod(0, i), tree.prod(i + 1, N)) for i in range(N))
    print(res)


if __name__ == "__main__":
    # practice2_j()
    # staticrmq()
    # dsl_2_a()
    abc125_c()