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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson


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

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)

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

Solution (Python):
import math

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

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


ide_ele = 0


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)

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

ans=chk=0
for i in d:
    if d[i]>=n-1:
        ans=max(ans,i)
print(ans)

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

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

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

Solution (Python):
from typing import Callable, List, Union

T = Union[int, str]


class SegmentTree:
    """Segment Tree"""

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

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

        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
        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():
    
    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():
    
    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():
    
    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():
    
    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__":
    
    
    
    abc125_c()

Solution (Python):
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n = i_input()
    a = i_list()

    left = [0]
    right = [0]

    for i in range(n):
        left.append(gcd(left[i], a[i]))
        right.append(gcd(right[i], a[-(i+1)]))

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



if __name__=="__main__":
    main()

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

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

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

Solution (Python):
from math import gcd
from itertools import accumulate

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

l = list(accumulate(a, lambda x, y: gcd(x, y)))
r = list(accumulate(a[::-1], lambda x, y: gcd(x, y)))[::-1]
ans = max(r[1], l[-2])
for i in range(1, n-1):
    ans = max(ans, gcd(l[i-1], r[i+1]))
print(ans)

Solution (Python):
"""
問題文を言い換えると、「最大公約数が最大になるように数字を一つ書き換えろ」ということ。
さらに言い換えると、「最大公約数が最大になるように数字を一つ消せ」ということ。
単純な線形探索でできるか？→NO

最大公約数を小さくする要因となっている数字を一つ消す。
どういう数字が最大公約数を小さくする要因になっているか？
他の数字と共通する素因数が少ない、小さい、次数が小さい。ただ、この3つを総合的に判断するのは難しすぎる。
素因数分解はやめて、単純に約数で探せばよいか。
各Aの約数を昇順で列挙しておく。
まずA1は必ず残すと仮定して、A1の約数の大きい方から順番に、ほかのAの約数になるかどうかを調べる。
その約数を含んでいないAが一つだけ存在するとき、そのAを消せば、その約数が最大公約数となる。

次に、A1を消す場合の最大公約数も求めて、A1を含める場合の最大公約数と比較して大きい方を採用する。
"""

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


yakusu = []

a = A[0]
d = 1
while d*d < a:
    if a % d == 0:
        yakusu.append(d)
        yakusu.append(a//d)
    d += 1
if d*d == a:
    yakusu.append(d)
yakusu.sort(reverse=True)

ans = 1
for v in yakusu:
    cnt = 0
    for i in range(1,N):
        if A[i]%v != 0:
            cnt += 1
    if cnt <= 1:
        ans = v
        break


import math
g = A[1]
for i in range(2,N):
    g = math.gcd(g,A[i])

ans = max(ans,g)

print(ans)

Solution (Python):
from math import gcd


N, *A = map(int, open(0).read().split())
acc_l = [0]
acc_r = [0]
for i in range(N):
    acc_l.append(gcd(acc_l[-1], A[i]))
    acc_r.append(gcd(acc_r[-1], A[N - i - 1]))

ans = 0
for i in range(N):
    ans = max(ans, gcd(acc_l[i], acc_r[N - i - 1]))
print(ans)

Solution (Python):
from math import gcd
N = int(input())
A = list(map(int, input().split()))
B = [0 for i in range(N)]
C = [0 for i in range(N)]
B[0] = A[0]
C[0] = A[N - 1]
for i in range(1, N):
    B[i] = gcd(B[i - 1], A[i])
    C[i] = gcd(C[i - 1], A[N - i - 1])


ans = 0
for i in range(N):
    if i != 0 and i != N - 1:
        ans = max(ans, gcd(B[i - 1], C[N - i - 2]))
    elif i == 0:
        ans = max(ans, C[N - 2])
    else:
        ans = max(ans, B[N - 2])

print(ans)

Solution (Python):
from math import gcd

n, *a = map(int, open(0).read().split())

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

Solution (Python):

from math import gcd
INF = 10**9+1
class SegTree:
    def __init__(self, vals, seg_f, ide_ele):
        n = len(vals)
        self.seg_f = seg_f
        self.ide_ele = ide_ele
        self.leaf_n = 1 << (n-1).bit_length()
        self.tree = [ide_ele]*(2*self.leaf_n-1)
        for i in range(n):  
            self.tree[i+self.leaf_n-1] = vals[i]
        for i in range(self.leaf_n-2, -1, -1):  
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    def update(self, i, x):
        i += (self.leaf_n-1)
        self.tree[i] = x
        while i > 0:
            i = (i-1)//2
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    
    def query(self, l, r):
        v_l = self.ide_ele
        v_r = self.ide_ele
        l += (self.leaf_n-1)
        r += (self.leaf_n-1)
        while l < r:
            if l&1 == 0:
                v_l = self.seg_f(v_l, self.tree[l])
            if r&1 == 0:
                v_r = self.seg_f(v_r, self.tree[r-1])
                r -= 1
            l >>= 1
            r >>= 1
        return self.seg_f(v_l ,v_r)


def gcd2(a,b):
    if a >= INF: return b
    elif b >= INF: return a
    else: return gcd(a,b)



n = int(input())
al = list(map(int, input().split()))
st = SegTree(al,gcd2,INF)
ans = 0
for i in range(n):
    if i != 0:
        st.update(i-1,al[i-1])
    st.update(i,INF)
    v = st.query(0,n)
    ans = max(ans,v)


print(ans)

Solution (Python):
import math

def main():
    N = int(input())
    A = list(map(int, input().split()))
    if N == 2:
        print(max(A))
        exit()
    l_gcd = [A[0]]
    for a in A[1:N-1]:
        l_gcd.append(math.gcd(l_gcd[-1], a))
    r_gcd = [A[-1]]
    for a in list(reversed(A))[1:N-1]:
        r_gcd.append(math.gcd(r_gcd[-1], a))

    ans = 1
    for i in range(N):
        if i == 0:
            v = r_gcd[-1]
        elif i == N-1:
            v = l_gcd[-1]
        else:
            v = math.gcd(l_gcd[i-1], r_gcd[N-i-2])
        if v > ans:
            ans = v
    print(ans)


if __name__ == '__main__':
    main()

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

pref = [0]; suff = [0]

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

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

suff.reverse()

ans = pref[-1]

for i in range(len(pref)-1):
    ans = max(ans, gcd(pref[i], suff[i+1]))

print(ans)

Solution (Python):
def gcd(a, b):
    if a < b:
        return gcd(b, a)
    while b > 0:
        a, b = b, a % b
    return a

n = int(input())
a = list(map(int, input().split()))
l = a[:]
r = a[:]

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

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

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



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

Solution (Python):

from math import gcd

INF = 10**10
class SegTree:
    def __init__(self, vals, seg_f, ide_ele):
        n = len(vals)
        self.seg_f = seg_f
        self.ide_ele = ide_ele
        self.leaf_n = 1 << (n-1).bit_length()
        self.tree = [ide_ele]*(2*self.leaf_n-1)
        for i in range(n):  
            self.tree[i+self.leaf_n-1] = vals[i]
        for i in range(self.leaf_n-2, -1, -1):  
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    def update(self, i, x):
        i += (self.leaf_n-1)
        self.tree[i] = x
        while i > 0:
            i = (i-1)//2
            self.tree[i] = self.seg_f(self.tree[2*i+1], self.tree[2*i+2])

    
    def query(self, l, r):
        v_l = self.ide_ele
        v_r = self.ide_ele
        l += (self.leaf_n-1)
        r += (self.leaf_n-1)
        while l < r:
            if l&1 == 0:
                v_l = self.seg_f(v_l, self.tree[l])
            if r&1 == 0:
                v_r = self.seg_f(v_r, self.tree[r-1])
                r -= 1
            l >>= 1
            r >>= 1
        return self.seg_f(v_l ,v_r)

def gcd2(a,b):
    if a == INF:
        return b
    elif b == INF:
        return a
    else:
        return gcd(a,b)


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

st = SegTree(al,gcd2,INF)

ans = 0
for i in range(n):
    if i > 0: st.update(i-1,al[i-1])
    st.update(i,INF)
    c_gcd = st.query(0,n)
    
    ans = max(ans,c_gcd)

print(ans)

Solution (Python):
from itertools import accumulate
from math import gcd

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

l = list(accumulate(A[:-1], gcd, initial=0))
r = list(accumulate(A[::-1], gcd, initial=0))
print(max(gcd(l[i], r[N-i-1]) for i in range(N)))

Solution (Python):
from math import gcd



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



ide_ele = 0


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """

    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


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

seg = SegTree(A, segfunc, ide_ele)

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

print(mx)

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

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

gcd_from_left = [0]*N 
gcd_from_right = [0]*N
 
for i in range(1,N):
  gcd_from_left[i] = gcd(A[i-1],gcd_from_left[i-1])
  gcd_from_right[N-1-i] = gcd(A[N-i],gcd_from_right[N-i])
  
ans = 0
 
for a,b in zip(gcd_from_left, gcd_from_right):
  x = gcd(a,b)
  if ans < x:
    ans = x
    
print(ans)

Solution (Python):

from functools import *
from math import *

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

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

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

for i in range(n):
    g = gcd(lgcd[i], rgcd[i])
    gcds.append(g)

print(max(gcds))

Solution (Python):
from math import gcd

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

A = [0] + A + [0]


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

R = [A[-2]]
tempR = A[-2]
for i in range(1, N):
    tempR = gcd(tempR, A[-i-2])
    R.append(tempR)
R = list(reversed(R)) + [0]

ans = []
for i in range(N):
    result = gcd(L[i], R[i+1])
    ans.append(result)

print(max(ans))

Solution (Python):
from math import gcd

class SegTree():
    def segfunc(self, x, y):
        return gcd(x, y)

    def __init__(self, ide, init_val):
        n = len(init_val)
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[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, idx, val):
        idx += self.num-1
        self.seg[idx] = val
        while idx:
            idx = (idx-1)//2
            self.seg[idx] = self.segfunc(self.seg[idx*2+1], self.seg[idx*2+2])
    def query(self, begin, end):
        if end <= begin:
            return self.ide_ele
        begin += self.num-1
        end += self.num-2
        res = self.ide_ele
        while begin + 1 < end:
            if begin&1 == 0:
                res = self.segfunc(res, self.seg[begin])
            if end&1 == 1:
                res = self.segfunc(res, self.seg[end])
                end -= 1
            begin = begin//2
            end = (end-1)//2
        if begin == end:
            res = self.segfunc(res, self.seg[begin])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[begin]), self.seg[end])
        return res

def main():
    n = int(input())
    a = list(map(int, input().split()))
    seg = SegTree(0, a)
    ans = 1
    for i in range(n):
        ans = max(ans, gcd(seg.query(0, i), seg.query(i+1, n)))
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

N = ri()
A = rl()

class SegTree:
	def __init__(self, n, f=min, v=float('inf')):
		self.n = n
		self.f = f
		self.v = v
		self.nums = [v] * (2*n)
		
	def init(self, seq):
		n, f, nums = self.n, self.f, self.nums
		assert len(seq) == n, 'seq size error'
		for i, x in enumerate(seq):
			nums[i+n] = x
		for i in range(n-1, 0, -1):
			nums[i] = f(nums[i<<1], nums[i<<1|1])

	def update(self, i, x):
		n, f, nums = self.n, self.f, self.nums
		i += n
		nums[i] = x
		while i > 1:
			i >>= 1
			nums[i] = f(nums[i<<1], nums[i<<1|1]) 
	
	def query(self, l, r): 
		n, f, v, nums = self.n, self.f, self.v, self.nums
		l, r = l+n, r+n
		vl, vr = v, v
		while l < r:
			if l & 1:
				vl = f(vl, nums[l])
				l += 1
			if r & 1:
				r -= 1
				vr = f(nums[r], vr)
			l, r = l>>1, r>>1
		return f(vl, vr)

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

st = SegTree(N, f=gcd, v=0)
st.init(A)

ans = -1
for i in range(N):
	g = gcd(st.query(0, i), st.query(i+1, N))
	ans = max(g, ans)
print(ans)