Problem: 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.

Submission attempts (in order):
import sys
# import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
# from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
# from itertools import permutations, combinations, product, accumulate, groupby

# from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []; mod = 10 ** 9 + 7
# dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n = i()
a = wi()

value = [] 
N = 0 

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

def update(i, x):
    
    i += N - 1  
    value[i] = x
    while i > 0:
        i = (i - 1) / 2  
        value[i] = min(value[i * 2 + 1], value[i * 2 + 2])  


#define INF 2147483647 // 2^31-1
INF = float("INF")
def query(a, b, k, l, r) :
    
    
    if r <= a or b <= l:
        
        return 0
    if a <= l and r <= b:
        
        return value[k]
    else:
        
        c1 = query(a, b, 2 * k + 1, l, (l + r) // 2)  
        c2 = query(a, b, 2 * k + 2, (l + r) // 2, r)  
        
        return gcd(c1, c2)



value = [] 
N = 0 

if __name__ == '__main__':
    N = 1
    while N < n:
        N *= 2  を計算（n以上の最小の2冪数）

    value = [0] * (2 * N - 1)
    for i in reversed(range(2 * N - 1)):
        if N - 1 <= i < 2 * N - 1:
            if N - 1 <= i < N - 1 + n:
                value[i] = a[i - (N - 1)]
            else:
                value[i] = 0
        else:
            value[i] = gcd(value[2 * i + 1], value[2 * i + 2])

    for i in range(n):#query(,,0,0,N)
        if i == 0:
            ansli.append(query(1, n, 0, 0, N))
        elif i == n - 1:
            ansli.append(query(0, n - 1, 0, 0, N))
        else:
            ansli.append(gcd(query(0, i, 0, 0, N), query(i + 1, n, 0, 0, N)))
print(max(ansli))

import sys
# import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
# from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
# from itertools import permutations, combinations, product, accumulate, groupby

# from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)

# dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

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

l_gcd = [a[0]]
r_gcd = [a[-1]]
kl = a[0]
kr = a[-1]
for i in range(n - 2):
    kl = gcd(kl, a[i + 1])
    l_gcd.append(kl)
    kr = gcd(kr, a[-(i + 2)])
    r_gcd.append(kr)

ansli = []
for i in range(n):
    if i == 0:
        ansli.append(r_gcd[-1])
    elif i == n - 1:
        ansli.append(l_gcd[-1])
    else:
        ansli.append(gcd(l_gcd[i - 1], r_gcd[-(i + 1)]))

print(max(ansli))

Verdicts: Time Limit Exceeded

Accepted