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: Runtime Error

Solution code:
#from fractions import gcd
"""
def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)
"""
def gcd(a,b):
    if b==0:
        a,b=b,a
    r=a%b
    while r!=0:
        a=b
        b=r
        r=a%b
    return b
class SegTree():
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.func = function
        self.basement = basement
        self.seg = [basement]*2**(self.K+1)#basementで初期化
 
        for i in range(self.n):
            self.seg[i+2**self.K-1] = lists[i]
 
        for i in range(2**(self.K)-2, -1, -1):
            self.seg[i] = self.func(self.seg[2*i+1], self.seg[2*i+2])
 
    def update(self, k, value):
        # 0-indexでa[k]の値をvalueに変更
        k += 2**self.K-1
        self.seg[k] = value
        while k:
            k = (k-1)//2
            self.seg[k] = self.func(self.seg[k*2+1], self.seg[k*2+2])
 
    def query(self, p, q):
        # 0-indexで[p,q)の値を取得する
        if q <= p:
            return self.basement
        num = 2**self.K
        p += num-1
        q += num-2
        res = self.basement
        while q-p > 1:
            if p & 1 == 0:
                res = self.func(res, self.seg[p])
            if q & 1 == 1:
                res = self.func(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.func(res, self.seg[p])
        else:
            res = self.func(self.func(res, self.seg[p]), self.seg[q])
        return res
 

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

Submission status: Runtime Error

Solution code:
#from fractions import gcd
"""
def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)
"""
def gcd(a,b):
    r=a%b
    while r!=0:
        a=b
        b=r
        r=a%b
    return b
class SegTree():
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.func = function
        self.basement = basement
        self.seg = [basement]*2**(self.K+1)#basementで初期化
 
        for i in range(self.n):
            self.seg[i+2**self.K-1] = lists[i]
 
        for i in range(2**(self.K)-2, -1, -1):
            self.seg[i] = self.func(self.seg[2*i+1], self.seg[2*i+2])
 
    def update(self, k, value):
        # 0-indexでa[k]の値をvalueに変更
        k += 2**self.K-1
        self.seg[k] = value
        while k:
            k = (k-1)//2
            self.seg[k] = self.func(self.seg[k*2+1], self.seg[k*2+2])
 
    def query(self, p, q):
        # 0-indexで[p,q)の値を取得する
        if q <= p:
            return self.basement
        num = 2**self.K
        p += num-1
        q += num-2
        res = self.basement
        while q-p > 1:
            if p & 1 == 0:
                res = self.func(res, self.seg[p])
            if q & 1 == 1:
                res = self.func(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.func(res, self.seg[p])
        else:
            res = self.func(self.func(res, self.seg[p]), self.seg[q])
        return res
 

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

Submission status: Runtime Error

Solution code:
# セグメント木。区間における要素の取得をO(logN)で行うことが可能である。
class SegTree():
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.func = function
        self.basement = basement
        self.seg = [basement]*2**(self.K+1)

        for i in range(self.n):
            self.seg[i+2**self.K-1] = lists[i]

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

    def update(self, k, value):
        # 0-indexでa[k]の値をvalueに変更
        k += 2**self.K-1
        self.seg[k] = value
        while k:
            k = (k-1)//2
            self.seg[k] = self.func(self.seg[k*2+1], self.seg[k*2+2])

    def query(self, p, q):
        # 0-indexで[p,q)の値を取得する
        if q <= p:
            return self.basement
        num = 2**self.K
        p += num-1
        q += num-2
        res = self.basement
        while q-p > 1:
            if p & 1 == 0:
                res = self.func(res, self.seg[p])
            if q & 1 == 1:
                res = self.func(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.func(res, self.seg[p])
        else:
            res = self.func(self.func(res, self.seg[p]), self.seg[q])
        return res


#gcd on blackboard
#セグ木（区間gcd) verify
from math import gcd
N=int(input())
A=list(map(int,input().split()))
seg=SegTree(A,gcd,0)
ans=1
for i in range(-1,N):
    v=gcd(seg.query(0,i),seg.query(i+1,N))
    ans=max(v,ans)
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections,math
sys.setrecursionlimit(1000000)
INF = float("inf")

N = int(sys.stdin.readline())
A = tuple(map(int,sys.stdin.readline().split())) # single line with multi param

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

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

#print(left,right)
#print(left[1],right[1],left[-2],right[-2])
if min(left[1],right[1])==min(left[-2],right[-2]):
    print(math.gcd(left[1],right[-2]))
else:
    print(max(min(left[1],right[1]),min(left[-2],right[-2])))
# ret = 0
# for i in range(N):
#     print(left[i],right[i+1])
#     ret = max(ret,min(left[i],right[i+1]))
#print(ret)

Submission status: Runtime Error

Solution code:
from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
b=[]
if n==2:
  print(max(a))

else:
  for i in range(n-1):
    x=a[i]
    y=a[i+1]
    b+=list(gcd(x,y))
  b+=list(gcd(a[0],a[-1]))
  b.sort()
  print(b[2])

Submission status: Runtime Error

Solution code:
from math import gcd
n=int(input())
a=list(map(int,input().split()))
b=[]
if n==2:
  print(max(a))

else:
  for i in range(n-1):
    x=a[i]
    y=a[i+1]
    b+=list(gcd(x,y))
  b+=list(gcd(a[0],a[-1]))
  b.sort()
  print(b[2])

Submission status: Runtime Error

Solution code:
from math import gcd
n=int(input())
a=list(map(int,input().split()))
b=[]
if n==2:
  print(max(a))

else:
  for i in range(n):
    x=a[i]
    y=a[i-1]
    b+=list(gcd(x,y))
  b.sort()
  print(b[2])

Submission status: Runtime Error

Solution code:
from math import gcd
n=int(input())
a=list(map(int,input().split()))
b=[]
if n==2:
  print(max(a))

else:
  for i in range(n):
    x=a[i]
    y=a[i-1]
    b+=[gcd(x,y)]
  b.sort()
  print(b[2])

Submission status: Runtime Error

Solution code:
from math import gcd
n=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(n):
  b+=gcd(a[i],a[i-1])
b.sort()
print(b[2])

Submission status: Runtime Error

Solution code:

def factorization(n):
    pf_cnt = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i == 0:
            cnt = 0
            while temp%i == 0:
                cnt += 1
                temp //= i
            pf_cnt[i] = cnt

    if temp != 1: pf_cnt[temp] = 1
    if not pf_cnt: pf_cnt[n] = 1
    return pf_cnt


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

    # al_fac = [0]*n
    for i, a in enumerate(al):
        fac = factorization(a)
        # al_fac[i] = fac

    gcd_l = [1]*n
    gcd_r = [1]*n

    gcd_l[0] = al_fac[0]
    gcd_r[-1] = al_fac[-1]

    for i in range(1,n):
        next_l = al_fac[i]
        next_l_gcd = {1:1}
        for prime,cnt in next_l.items():
            if prime in gcd_l[i-1]:
                next_l_gcd[prime] = min(cnt, gcd_l[i-1][prime])
        gcd_l[i] = next_l_gcd

        next_r = al_fac[n-i-1]
        next_r_gcd = {1:1}
        for prime,cnt in next_r.items():
            if prime in gcd_r[n-i]:
                next_r_gcd[prime] = min(cnt, gcd_r[n-i][prime])
        gcd_r[n-i-1] = next_r_gcd

    ans = 1
    for i in range(1,n-1):
        curr_gcd = 1
        for prime,cnt in gcd_l[i-1].items():
            if prime in gcd_r[i+1]:
                min_cnt = min(cnt, gcd_r[i+1][prime])
                curr_gcd *= prime**min_cnt
        ans = max(ans, curr_gcd)


    # i = 0
    curr_gcd = 1
    for prime,cnt in gcd_r[1].items():
        curr_gcd *= (prime**cnt)
    ans = max(ans, curr_gcd)

    # i = n-1
    curr_gcd = 1
    for prime,cnt in gcd_l[n-2].items():
        curr_gcd *= (prime**cnt)
    ans = max(ans, curr_gcd)

    # print(al_fac)
    # print(gcd_l)
    # print(gcd_r)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:

def factorization(n):
    pf_cnt = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i == 0:
            cnt = 0
            while temp%i == 0:
                cnt += 1
                temp //= i
            pf_cnt[i] = cnt

    if temp != 1: pf_cnt[temp] = 1
    if not pf_cnt: pf_cnt[n] = 1

    return pf_cnt


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

al_fac = []
for a in al:
    fac = factorization(a)
    al_fac.append(fac)

gcd_l = [1]*n
gcd_r = [1]*n

gcd_l[0] = al_fac[0]
gcd_r[-1] = al_fac[-1]

for i in range(1,n):
    next_l = al_fac[i]
    next_l_gcd = {}
    for prime,cnt in next_l.items():
        if prime in al_fac[i-1]:
            next_l_gcd[prime] = min(cnt, al_fac[i-1][prime])
    gcd_l[i] = next_l_gcd

    next_r = al_fac[n-i-1]
    next_r_gcd = {}
    for prime,cnt in next_r.items():
        if prime in al_fac[n-i]:
            next_r_gcd[prime] = min(cnt, al_fac[n-i][prime])
    gcd_r[n-i-1] = next_r_gcd

    ans = 1
    for i in range(1,n-1):
        curr_gcd = 1
        for prime,cnt in gcd_l[i-1].items():
            if prime in gcd_r[i+1]:
                min_cnt = min(cnt, gcd_r[i+1][prime])
                curr_gcd *= prime**min_cnt
        ans = max(ans, curr_gcd)
    
    # i = 0
    curr_gcd = 1
    for prime,cnt in gcd_r[1].items():
        curr_gcd *= (prime**cnt)
    ans = max(ans, curr_gcd)

    # i = n-1
    curr_gcd = 1
    for prime,cnt in gcd_l[n-2].items():
        curr_gcd *= (prime**cnt)
    ans = max(ans, curr_gcd)

# print(al_fac)
# print(gcd_l)
# print(gcd_r)
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
import math
from functools import reduce
import copy

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

N=int(input())
AList=list(map(int, input().split()))
SubList=AList.copy()
ANS=0
for i in range(N):
    AList=SubList.copy()
    del AList[i]
    ANS=max(gcd_list(AList),ANS)
print(ANS)

Submission status: Runtime Error

Solution code:
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N = I()
A = LI()

from functions import gcd

L = [0]*N  # L[i] = A[0]からA[i]までの最大公約数
R = [0]*N  # R[i] = A[i]からA[N-1]までの最大公約数

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

a = max(L[N-1],R[1])

if N == 2:
    print(a)
else:
    print(max(a,max(gcd(L[i],R[i+2]) for i in range(N-2))))

Submission status: Runtime Error

Solution code:
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N = I()
A = LI()

from math import gcd

L = [0]*N  # L[i] = A[0]からA[i]までの最大公約数
R = [0]*N  # R[i] = A[i]からA[N-1]までの最大公約数

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

a = max(L[N-1],R[1])

if N == 2:
    print(a)
else:
    print(max(a,max(gcd(L[i],R[i+2]) for i in range(N-2))))

Submission status: Runtime Error

Solution code:
import math

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

if N ==2:
    print(max(arr[0],arr[1]))
    exit()

if N ==3:
    print(max(math.gcd(arr[0],arr[1]),math.gcd(arr[0],arr[2]),math.gcd(arr[1],arr[2])))
    exit()
ura_arr = arr[::-1]
left_gcd =[arr[0]]
right_gcd =[arr[-1]]

for i in range(1,N):
    left_gcd.append(math.gcd(left_gcd[-1],arr[i]))
    right_gcd.append(math.gcd(right_gcd[-1],arr[-1-i]))

ans = max(left_gcd[-2],right_gcd[-2])
for i in range(N-2):
    ans = max(ans,math.gcd(left_gcd[i],right_gcd[-1*(i+2)]))

print(ans)

Submission status: Runtime Error

Solution code:
import math

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

if N ==3:
    print(max(math.gcd(arr[0],arr[1]),math.gcd(arr[0],arr[2]),math.gcd(arr[1],arr[2])))
    exit()
ura_arr = arr[::-1]
left_gcd =[arr[0]]
right_gcd =[arr[-1]]

for i in range(1,N):
    left_gcd.append(math.gcd(left_gcd[-1],arr[i]))
    right_gcd.append(math.gcd(right_gcd[-1],arr[-1-i]))

print(left_gcd,right_gcd)

ans = max(left_gcd[-2],right_gcd[-2])

for i in range(N-2):
    ans = max(ans,math.gcd(left_gcd[i],right_gcd[-1*(i+2)]))

print(ans)

Submission status: Runtime Error

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

import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

ans = 0

for i in range(N):
    if ans == 0:
        ans = gcd_list([*A[:i], *A[i+1:]])
        
    elif gcd_list([*A[:i], *A[i+1:]]) > ans:
        ans = gcd_list([*A[:i], *A[i+1:]])
        break
        
print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd
class SegmentTree(object):
    def __init__(self, sequence, function, identity):
        N = len(sequence)
        self.length = (1 << (N - 1)).bit_length()
        self.data = [identity] * (self.length << 1)
        self.function = function
        self.identity = identity
        for i in range(N):
            self.data[i + self.length - 1] = sequence[i]
        for i in range(self.length - 2, -1, -1) :
            self.data[i] = self.function(self.data[(i << 1) + 1], self.data[(i << 1) + 2])

    def update(self, idx, x):
        idx += self.length - 1
        self.data[idx] = x
        while idx:
            idx = (idx - 1) >> 1
            self.data[idx] = self.function(self.data[(idx << 1) + 1], self.data[(idx << 1) + 2])

    def query(self, p, q):
        if q <= p:
            return self.identity
        p += self.length - 1
        q += self.length - 2
        res = self.identity
        while q - p > 1:
            if not p & 1:
                res = self.function(res, self.data[p])
            if q & 1:
                res = self.function(res, self.data[q])
                q -= 1
            p >>= 1
            q = (q - 1) >> 1
        return self.function(res, self.data[p]) if p == q else self.function(self.function(res, self.data[p]), self.data[q])

N, *A = map(int, open(0).read().split())
seg_tree = SegmentTree(A, gcd, 0)
ans = 0
for i in range(N):
    seg_tree.update(i, 0)
    ans = max(ans, seg_tree.query(0, N))
    seg_tree.update(i, A[i])
print(ans)

Submission status: Runtime Error

Solution code:
import fractions

n = int(input())
a = list(map(int, input().split()))
b = a[::-1]

left = [0, a[0]]
right = [0, b[0]]
l = a[0]
r = b[0]
for i in range(1, n):
    l = fractions.gcd(l, a[i])
    r = fractions.gcd(r, b[i])
    left.append(l)
    right.append(r)

gcd_max = 0
for i in range(n+1):
    gcd_tmp = gcd(left[i], right[n-i-1])
    if gcd_tmp > gcd_max:
        gcd_max = gcd_tmp

print(gcd_max)

Submission status: Runtime Error

Solution code:
from math import gcd

n = int(input())
a = list(map(int, input().split()))
b = a[::-1]

left = [0, a[0]]
right = [0, b[0]]
l = a[0]
r = b[0]
for i in range(1, n):
    l = gcd(l, a[i])
    r = gcd(r, b[i])
    left.append(l)
    right.append(r)

gcd_max = 0
for i in range(n+1):
    gcd_tmp = gcd(left[i], right[n-i-1])
    if gcd_tmp > gcd_max:
        gcd_max = gcd_tmp

print(gcd_max)

Submission status: Runtime Error

Solution code:
import sys
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
pref,suf = [0]*(n+2),[0]*(n+2)
pref[1] = a[0]
for i in range(2,n+1):
    pref[i] = gcd(pref[i-1],a[i-1])
suf[n] = a[n-1]
for i in range(n-1,0,-1):
    suf[i] = gcd(suf[i+1],a[i-1])
ans = max(suf[2],pref[n-1])
for i in range(2,n):
    ans = max(ans,gcd(pref[i-1],suf[i+1]))
print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd

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

L = [-1] * (N-1)
L[0] = A[0]
R = [-1] * (N-1)
R[0] = A[-1]

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

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

ans = max(ans, L[N-2])
ans = max(ans, R[N-2])
print(ans)

Submission status: Runtime Error

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

import math
magcd = 0
for i in range(N):
  a = 0
  for j in range(i):
    a = math.gcd(a,A[j])
  b = 0
  for k in range(i+1,N):
    b = math.gcd(b,A[k])
  ggc = math.gcd(a,b)
  if ggc > magcd:
    magcd = ggc
print(magcd)

Submission status: Runtime Error

Solution code:
import fractions
from functools import reduce
n=int(input())
a=list(map(int,input().split()))
g=1
a=sorted(a)

def gcd(numbers):
    return reduce(fractions.gcd,numbers)

for i in range(n):
    b=a.copy()
    b.pop(a[i])
    if min(b)<g:
        pass
    else:
        if g < gcd(b):
            g = gcd(b)
print(g)

Submission status: Runtime Error

Solution code:
from math import gcd
n = int(input())
a = list(map(int,input().split()))
left = []
right = []

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

Submission status: Runtime Error

Solution code:
from fractions import gcd
from functools import reduce
n = int(input())
a = list(map(int, input().split()))
def prime(k):
    for divisor in range(2, math.floor(math.sqrt(k))+1):
        if k % divisor == 0:
            return False
    return True


def _gcd(numbers):
    return reduce(gcd, numbers)


prime_count = 0
data = []
for i in range(n):
    if prime(a[i]):
        prime_count += 1
        if prime_count >= 2:
            print(1)
            exit()
    else:
        data.append(a[i])

if prime_count == 1:
    ans = _gcd(data)
else:
    data.sort()
    ans = 0
    for i in range(n):
        p = _gcd(data[:i]+data[i+1:])
        if p > ans:
            ans = p

print(ans)

Submission status: Runtime Error

Solution code:
import math
N = int(input())
A = [int(i) for i in input().split()]

'''
'init(a)': 配列aで初期化。O(N)
'update(k,x)': a[k]をxに変更 O(logN)
'query(p,q)': [p,q)について "segfunc" したものを返す O(logN)
'ide_ele' : 単位元。
'''


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[k*2+1], seg[k*2+2])


def query(p, q):
    if q <= p:
        return ide_ele
    p += num-1
    q += num-2
    res = ide_ele
    while q-p > 1:
        if p & 1 == 0:
            res = segfunc(res, seg[p])
        if q & 1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(segfunc(res, seg[p]), seg[q])
    return res


#####単位元######
ide_ele = A[-1]

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

init(A)

# print(query(0, 2))

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

Submission status: Runtime Error

Solution code:
from math import gcd

# 配列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] = gcd(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] = gcd(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 = gcd(res, seg[p])
        if q & 1 == 1:
            res = gcd(res, seg[q])
            q -= 1
        p = p // 2
        q = (q - 1) // 2
    if p == q:
        res = gcd(res, seg[p])
    else:
        res = gcd(gcd(res, 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: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
import fractions
import collections
 
gcd_s = []
for i in range(n):
    tem_arr = []
    if i != 0:
        tem_arr += a[:i]
    if i != n-1:
        tem_arr += a[i+1:]
    tem_arr = collections.deque(tem_arr)
    tem_gcd_l = tem_arr.popleft()
    tem_gcd_r = tem_arr.pop()
    while len(tem_arr) > 0:
        tem_l = tem_arr.popleft()
        tem_gcd_l = fractions.gcd(tem_gcd_l, tem_l)
        if len(tem_arr) != 0:
            tem_r = tem_arr.pop()
            tem_gcd_r = fractions.gcd(tem_gcd_r, tem_r)

    gcd_s.append(fractions.gcd(tem_gcd_l, tem_gcd_r))

print(max(gcd_s))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import functools
import math
N = int(input())
A = list(map(int,input().split()))
result = [0]*N
tmp = 0
for i in range(N):
  tmp = A.pop(i)
  result[i] = functools.reduce(math.gcd, A)
  A.insert(i,tmp)

print(max(result))

Submission status: Runtime Error

Solution code:
import fractions

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

used={}
unused={}

def gcd(x,y):
    if x==-1 or y==-1:
        return max(x,y)
    return fractions.gcd(x,y)

def rec(i,x,f):
    if i+1==N:
        return x
    
    if f==1 and used.get(x,-2)>-2:
        return used[x]
    if f==0 and unused.get(x,-2)>-2:
        return unused[x]
    
    if f==0:
        unused[x]=rec(i+1,gcd(x,A[i+1]),0)
        used[x]=rec(i+1,x,1)
        return max(unused[x],used[x])
    else:
        used[x]=rec(i+1,gcd(x,A[i+1]),1)
        return used[x]


print(rec(-1,-1,0))

Submission status: Runtime Error

Solution code:
import fractions

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

used={}
unused={}

def gcd(x,y):
    if x==-1 or y==-1:
        return max(x,y)
    return fractions.gcd(x,y)

def rec(i,x,f):
    if i+1==N and f==1:
        return x
    elif i+1==N and f==0:
        return -1
    
    if f==1 and used.get(x,-2)>-2:
        return used[x]
    if f==0 and unused.get(x,-2)>-2:
        return unused[x]
    
    if f==0:
        unused[x]=rec(i+1,gcd(x,A[i+1]),0)
        used[x]=rec(i+1,x,1)
        return max(unused[x],used[x])
    else:
        used[x]=rec(i+1,gcd(x,A[i+1]),1)
        return used[x]


print(rec(-1,-1,0))

Submission status: Runtime Error

Solution code:
import fractions

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

used={}
unused={}

def gcd(x,y):
    if x==-1 or y==-1:
        return max(x,y)
    return fractions.gcd(x,y)

def rec(i,x,f):
    if i+1==N and f==1:
        return x
    elif i+1==N and f==0:
        return -1
    
    if f==1 and used.get(x,-1)>0:
        return used[x]
    if f==0 and unused.get(x,-1)>0:
        return unused[x]
    
    if f==0:
        unused[x]=rec(i+1,gcd(x,A[i+1]),0)
        used[x]=rec(i+1,x,1)
        return max(unused[x],used[x])
    else:
        used[x]=rec(i+1,gcd(x,A[i+1]),1)
        return used[x]


print(rec(-1,-1,0))

Submission status: Runtime Error

Solution code:
import math

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

used={}
unused={}

def gcd(x,y):
    if x==-1 or y==-1:
        return max(x,y)
    return math.gcd(x,y)

def rec(i,x,f):
    if i+1==N and f==1:
        return x
    elif i+1==N and f==0:
        return -1
    
    if f==1 and used.get(x,-1)>0:
        return used[x]
    if f==0 and unused.get(x,-1)>0:
        return unused[x]
    
    if f==0:
        unused[x]=rec(i+1,gcd(x,A[i+1]),0)
        used[x]=rec(i+1,x,1)
        return max(unused[x],used[x])
    else:
        used[x]=rec(i+1,gcd(x,A[i+1]),1)
        return used[x]


print(rec(-1,-1,0))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from fractions import gcd
from functools import reduce

n = int(input())
a = list(set(map(int, input().split())))
n = len(a)
#a = [746130, 1385670, 4849845, 881790, 3233230, 1939938, 570570, 510510]
#a = [7,6,8]
#n = len(a)
max_value = 0
for i in range(n):
    memo = a.pop(0)
    x = reduce(gcd, a)
    if x > max_value:
        max_value = x
    a.append(memo)
print(max_value)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(set(map(int, input().split())))
n = len(a)
#a = [746130, 1385670, 4849845, 881790, 3233230, 1939938, 570570, 510510]
#a = [7,6,8]
#n = len(a)
max_value = 0
for i in range(n):
    memo = a.pop(0)
    x = reduce(gcd, a)
    if x > max_value:
        max_value = x
    a.append(memo)
print(max_value)

Submission status: Runtime Error

Solution code:
from fractions import gcd
from functools import reduce

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

#a = [746130, 1385670, 4849845, 881790, 3233230, 1939938, 570570, 510510]
#a = [7,6,8]
#n = len(a)
max_value = 0
for i in range(n):
    memo = a.pop(0)
    x = reduce(gcd, b)
    if x > max_value:
        max_value = x
    a.append(memo)
print(max_value)

Submission status: Runtime Error

Solution code:
from math import gcd
from functools import reduce

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

#a = [746130, 1385670, 4849845, 881790, 3233230, 1939938, 570570, 510510]
#a = [7,6,8]
#n = len(a)
max_value = 0
for i in range(n):
    b = a.copy()
    b.pop(i)
    x = reduce(gcd, b)
    if x > max_value:
        max_value = x
        max_pos = i
print(max_value)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import fractions
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

from itertools import permutations
from math import factorial, hypot

N = getN()
A = getList()

course = []
x1 = A[0]
for i in A:
    x2 = i
    opt = math.gcd(x1, x2)
    course.append(opt)
    x1 = opt

reverse = []
y1 = A[-1]
for i in A[::-1]:
    y2 = i
    opt = math.gcd(y1, y2)
    reverse.append(opt)
    y1 = opt
reverse.sort()

ans = 0
for i in range(N):
    res = 0
    if i == 0:
        res = reverse[1]
    elif i == N - 1:
        res = course[-2]
    else:
        res = math.gcd(course[i - 1], reverse[i + 1])
    ans = max(ans, res)
print(ans)

Submission status: Runtime Error

Solution code:
"""半分くらいWA"""
# 最大公約数(mathは3.5以降) 
from functools import reduce
import fractions #(2020-0405  fractions→math)
def lcm_base(x, y):
    return  fractions.gcd(x, y) # 「//」はフロートにせずにintにする
def lcm_list(numbers):
    return reduce(lcm_base, numbers)
def lcm_fukusu(*numbers):
    return reduce(lcm_base, numbers)

# 初期入力
import numpy as np
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))

#Aの隣り合う要素の最大公約数
ans =[]
if N==2:
    ans =max(A)
    print(ans)
    exit()
else:
    for i in range(N-1):
        ans.append(lcm_fukusu(A[i],A[i+1]))
    ans.append(lcm_fukusu(A[0],A[-1])) #len(A) ==3の時必要
    ans =list(set(ans))
    ans.sort()

if len(ans) ==1:
    print(ans[0])
elif len(ans) ==2:
    print(ans[1])
else:
    ans1=[]
    for i in ans[1:3]:
        aa= np.count_nonzero(np.array(A) %i ==0) #iで割り切れる要素を数える
        if aa >=N-1:
            ans1.append(i)
    ans =max(ans1)
    print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
arr = sorted(map(int, input().split()))
surplus = [i%arr[0] == 0 for i in arr]
r = arr[0]
while not all([i%r == 0 for i in arr]):
  arr = [i % r for i in arr[1:]]
  arr.append(r)
  r = arr[0]
print(arr[-2])

Submission status: Runtime Error

Solution code:
n = int(input())
As = list(map(int, input().split()))
from math import gcd
# 左からの累積GCDと
g = As[0]
left = []
for a in As:
    g = gcd(g, a)
    left.append(g)
# 右からの累積GCD
As_r = As[::-1]
g_r = As_r[0]
right = []    
for a in As_r:
    g_r = gcd(g_r, a)
    right.append(g_r)
    
l = left
r = right[::-1]
ans = 0
for i in range(n):
    if i == 0:
        ans = max(ans, r[1])
    elif i == n-1:
        ans = max(ans, l[n-2])
    else:     
        g = gcd(l[i-1],r[i+1])
        ans = max(ans, g)
print(ans)