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


def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass #sortされていない


li = divisor(max_a)
li.sort(reverse=True)
#print(li)
ans = 0
for i in li:
    gcd = []
    for j in range(n):
        gcd.append(math.gcd(i, a[j]))
    if gcd.count(i) >= n-1 and ans < i:
        ans = i
print(ans)

Submission status: Runtime Error

Solution code:
# ==================== gcd   最大公約数
#from fractions import gcd
from math import gcd

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

l=[0]*(n+1)
r=[0]*(n+1)

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

mimax=1
for i in range(n):
    mi=gcd(l[i],r[i+1])
    mimax=max(mi,mimax)
   
print(mimax)

Submission status: Runtime Error

Solution code:
import math

n = int(input())
a = list(map(int, input().split()))
g1 = 10**9
gi1 = -1
g2 = 10**9
gi2 = -1

if n == 2:
    print(max(a))
    exit()

for i in range(n - 1):
    b = math.gcd(a[i], a[i + 1])
    if b < g1:
        g1 = b
        gi1 = i

for i in range(n - 2):
    b = math.gcd(a[i], a[i + 2])
    if b < g2:
        g2 = b
        gi2 = i

if g1 == g2:
    if gi1 == gi2:
        a[gi1] = a[gi1 + 1]
elif gi1 == gi2 + 2:
    a[gi1] = a[gi1 - 1]
elif g1 < g2:
    a[gi1 + 1] = a[gi1]

g1 = 10**9

for i in range(n - 1):
    b = math.gcd(a[i], a[i + 1])
    if b < g1:
        g1 = b
        gi1 = i

print(g1)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    segfunc = gcd

    def init(arr):
        # 0-index/上段の分ズラす
        for i in range(n):
            seg[i+num-1]=arr[i]
        # 上段の分を右から埋めていく
        for i in range(num-2,-1,-1) :
            seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
        
    def update(k,x):
        # 元の配列のindex→seg木上のindex
        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

    n = int(input())
    A = tuple(map(int, input().split()))

    # 単位元
    ide_ele = 0

    # num:n以上の最小の2のべき乗
    # n:5~8のときnum=8なので3が入ってほしいから-1
    num =2**((n-1).bit_length())

    # セグ木初期化
    seg=[ide_ele]*2*num
    init(A)

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def make_divisors(n: int):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    return divisors

m = [0] * (N+1)
for i in range(N):
    divisors = make_divisors(A[i])
    for d in divisors:
        m[d] += 1

ans = 1
for i in range(N+1):
    if (N-1) <= m[i] and ans < m[i]:
        ans = m[i]

print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd

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

L = [0] * (N+1)
R = [0] * (N+2)

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

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

print(ans)

Submission status: Runtime Error

Solution code:
import math
N=int(input())
A=list(map(int,input().split()))
A.append(A[0])
ans=0
for i in range(N):
    val=math.gcd(A[i],A[i+1])
    ans=max(ans,val)
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
v = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

v.sort()
c.sort()

maximum = 0
profit = []
for i in range(len(v)):
    tmp = v[i] - c[i]
    if tmp > 0:
        maximum += tmp
    tmp = 0

print(maximum)

Submission status: Runtime Error

Solution code:
from function import gcd
N = int(input())
A = list(map(int, input().split()))
L = [0]
R = [0]
M = []
maximum = 0
for n in range(N):
    L.append(gcd(A[n], L[-1]))
    R.append(gcd(A[-n-1], R[-1]))
R.reverse()
for n in range(N):
    M.append(gcd(L[n], R[n+1]))
for n in range(N):
    maximum = max(maximum, M[n])
print(maximum)

Submission status: Runtime Error

Solution code:
from math import gcd
N = int(input())
A = list(map(int, input().split()))
L = [0]
R = [0]
M = []
maximum = 0
for n in range(N):
    L.append(gcd(A[n], L[-1]))
    R.append(gcd(A[-n-1], R[-1]))
R.reverse()
for n in range(N):
    M.append(gcd(L[n], R[n+1]))
for n in range(N):
    maximum = max(maximum, M[n])
print(maximum)

Submission status: Runtime Error

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

import math
l=[0]
r=[0]
for i in range(n-1):
  l.append(math.gcd(l[i],a[i]))
  r.append(math.gcd(r[i],a[n-i-1]))
m=[]
for i in range(n):
  m.append(math.gcd(l[i],r[n-i-1]))
print(max(m))

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

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

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

ans = -1
for i in range(N):
    target = lst[:i] + lst[i+1:]
    val = gcd_list(target)
    if val > ans:
        ans = val
print(ans)

Submission status: Runtime Error

Solution code:
import fractions
n = int(input())
a = list(map(int, input().split()))
s = [0]
small = 10**9
c = 0
for i in range(n-1):
    s.append(fractions.gcd(a[i], a[i+1]))
    if fractions.gcd(a[i], a[i+1]) <= small:
        small = fractions.gcd(a[i], a[i+1])
        c = i+1
s.append(fractions.gcd(a[n-1], a[0]))
if fractions.gcd(a[n-1], a[0]) <= small:
    small = fractions.gcd(a[n-1], a[0])
    c = n
if c != 1 and c != n:
    if s[c-1] > s[c+1]:
        d = c+1
    else:
        d = c-1
if c == 1:
    if s[n] > s[2]:
        d = 2
    else:
        d = n
if c == n:
    if s[n-1] > s[1]:
        d = 1
    else:
        d = n-1
del s[c]
del s[d]
del s[0]
if n == 2:
    ans = max(a)
else:
    ans = min(s)
print(ans)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
a = list(map(int, input().split()))
s = [0]
small = 10**9
c = 0
for i in range(n-1):
    s.append(math.gcd(a[i], a[i+1]))
    if math.gcd(a[i], a[i+1]) <= small:
        small = math.gcd(a[i], a[i+1])
        c = i+1
s.append(math.gcd(a[n-1], a[0]))
if math.gcd(a[n-1], a[0]) <= small:
    small = math.gcd(a[n-1], a[0])
    c = n
if c != 1 and c != n:
    if s[c-1] > s[c+1]:
        d = c+1
    else:
        d = c-1
if c == 1:
    if s[n] > s[2]:
        d = 2
    else:
        d = n
if c == n:
    if s[n-1] > s[1]:
        d = 1
    else:
        d = n-1
del s[c]
del s[d]
del s[0]
if n == 2:
    ans = max(a)
else:
    ans = min(s)
print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd
N = int(input())
As = list(map(int, input().split()))

lis = [0]*N
ans = 0
for k in range(N):
    g = 10**20
    for i in range(N-1):
        if i==k: continue
        for j in range(i+1, N):
            if j==k: continue
            g = min(gcd(As[i], As[j]), g)
    ans = max(ans, g)
if N==2:
    print(max(As))
else:
    print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd
N = int(input())
As = list(map(int, input().split()))

lis = [0]*N
ans = 0
for k in range(N):
    g = 10**20
    for i in range(N-1):
        if i==k: continue
        for j in range(i+1, N):
            if j==k: continue
            g = min(gcd(As[i], As[j]), g)
    ans = max(ans, g)
if N==2:
    print(max(As))
else:
    print(ans)

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
N=int(input())
A=list(map(int,input().split()))
ans=1
def gcd_list(numbers):
    return reduce(math.gcd, numbers)
for i in range(N-1):
    A_c = A.copy()
    del A_c[i]
    g = gcd_list(A_c)
    if ans<=g:
        ans=g
print(ans)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from math import gcd

n = int(readline())
a = list(map(int, readline().split()))
b = a[::-1]
cumsum_m = [0] * (n - 1)
cumsum_p = [0] * (n - 1)
cumsum_m[0] = b[0]
cumsum_p[0] = a[0]
for i in range(1, n - 1):
    cumsum_p[i] = gcd(cumsum_p[i - 1], a[i])
    cumsum_m[i] = gcd(cumsum_m[i - 1], b[i])
ans = max(cumsum_m.pop(), cumsum_p.pop())
for p, m in zip(cumsum_p, cumsum_m[::-1]):
    v = gcd(p, m)
    if ans < v:
        ans = v
print(ans)

Submission status: Runtime Error

Solution code:
from numba import jit
import numpy as np

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

@jit
def main2(N,A):
    if N == 2:
        return max(A)
    else:
        max_ = -1
        for i in range(N):
            L = 0
            R = 0

            for j in range(N):
                if i == j: continue
                if j < i:
                    L = gcd(L, A[j])
                else:
                    R = gcd(R, A[j])
            tmp = gcd(L,R)
            if tmp > max_:
                max_ = tmp
        return max_

N = int(input())
A = np.array([int(i) for i in input().split(" ")])
print(main2(N,A))

Submission status: Runtime Error

Solution code:
import fractions

def gcd(l):
    if len(l) > 2:
        return fractions.gcd(l[0], gcd(l[1:]))
    elif len(l) == 1:
        return l[0]
    else:
        return fractions.gcd(l[0], l[1])

n = int(input())
a = [int(i) for i in input().split()]
g = gcd(a)
b = []
for i in a:
    b.append(i//g)

for i in range(1, n):
    if fractions.gcd(b[0], b[i]) == 1:
        x = i
        break

s = b[:]
b.pop(0)
s.pop(i)
print(max(gcd(b), gcd(s)) * g)

Submission status: Runtime Error

Solution code:
import math

def gcd(l):
    if len(l) > 2:
        return math.gcd(l[0], gcd(l[1:]))
    elif len(l) == 1:
        return l[0]
    else:
        return math.gcd(l[0], l[1])

n = int(input())
a = [int(i) for i in input().split()]
g = gcd(a)
b = []
for i in a:
    b.append(i//g)

for i in range(1, n):
    if math.gcd(b[0], b[i]) == 1:
        x = i
        break

s = b[:]
b.pop(0)
s.pop(i)
print(max(gcd(b), gcd(s)) * g)

Submission status: Runtime Error

Solution code:
def main():
    import sys 
    from fractions import gcd 
    input = sys.stdin.readline 

    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] = gcd(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] = gcd(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 = gcd(res, seg[p])
            if q & 1 == 1:
                res = gcd(res, seg[q])
                q -= 1
            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 = tuple(map(int, input().split())
    ide_ele = 0
    num = 2**(n-1).bit_length()
    seg = [ide_ele]*2*num
    init(a)    
                
    ans = -1
    for i in range(n):
        ans = max(ans, gcd(query(0,i), query(i+1,n)))
    print(ans) 

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

left = [0]*(n-1)
right = [0]*(n-1)
from fractions import gcd
for i in range(1,n-1):
  left[i] = gcd(left[i-1],a[i-1])
  right[n-i-1] = gcd(right[n-i],a[n-i])

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

Submission status: Runtime Error

Solution code:
from math import gcd

X = int(input())

line = input()
numbers = [int(n) for n in line.split()]

left_list = [0]*(X+1)
right_list = [0]*(X+1)
for i in range(X):
    left_list[i+1] = gcd(left_list[i], numbers[i])
    right_list[X-1-i] = gcd(right_list[X-i], numbers[X-1-i])
predicted_value = max([gcd(left_list[i], right_list[i+1]) for i in range(X)])


print(predicted_value)

Submission status: Runtime Error

Solution code:
from math import gcd

X = int(input())

line = input()
numbers = [int(n) for n in line.split()]

num_factors = [factors(num) for num in numbers]
left_list = [0]*(X+1)
right_list = [0]*(X+1)
for i in range(X):
    left_list[i+1] = gcd(left_list[i], numbers[i])
    right_list[X-1-i] = gcd(right_list[X-i], numbers[X-1-i])
predicted_value = max([gcd(left_list[i], right_list[i+1]) for i in range(X)])


print(predicted_value)

Submission status: Runtime Error

Solution code:
from math import gcd
def main():
    n = int(input())
    a = list(map(int, input().split()))
    ar = a[::-1]
    lgcds = [1]*n
    rgcds = [1]*n
    lgcd, rgcd = a[0], ar[0]
    lgcds[0] = rgcd
    lgcds[1] = lgcd
    rgcds[n-1] = lgcd
    rgcds[n-2] = rgcd
    for i in range(2, n):
        lgcd = gcd(lgcd, a[i])
        rgcd = gcd(rgcd, ar[i])
        lgcds[i] = lgcd
        rgcds[n-1-i] = rgcd
    ans = 1
    for i in range(n):
        gi = gcd(lgcds[i], rgcds[i])
        if gi > ans:
            ans = gi
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
from fractions import gcd
from functools import lru_cache

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()

@lru_cache(None)
def solve(index, n, g):
    '''既に１つ数を選んだらnは１'''
    if index == N:
        return g
    if n == 1:
        return solve(index+1, 1, gcd(g, A[index]))
    else:
        ret = max(solve(index+1, 1, g), solve(index+1, 0, gcd(g, A[index])))
        return ret

result1 = solve(0, 0,  A[0])
result2 = solve(0, 0, A[-1])
answer = max(result1, result2)
print(answer)

Submission status: Runtime Error

Solution code:
from functools import gcd   # gcd(6, 4) -> 2
from functools import reduce

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

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

ans = 0
for i in range(N):
    tmp = gcd_list(A[:i] + A[i+1:])
    ans = max(ans, tmp)

print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd   # gcd(6, 4) -> 2
from functools import reduce

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

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

ans = 0
for i in range(N):
    tmp = gcd_list(A[:i] + A[i+1:])
    ans = max(ans, tmp)

print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
from math import gcd
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def prime_factorize(n): # Nの素因数分解
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

# 約数が１つしかないものを探す
N = ir()
A = lr()
g = A[0]
dic = defaultdict(int)
for a in A:
    g = gcd(g, a)
    primes = prime_factorize(a)
    for p in primes:
        dic[p] += 1

cand = [1]
for k, v in dic.items():
    if v == 1:
        cand.append(k)

x = max(cand)
g = A[0] if A[0] % x != 0 else A[-1]
for a in A:
    if a%x == 0:
        continue
    g = gcd(g, a)

answer = g
print(answer)

Submission status: Runtime Error

Solution code:
import math
import copy
N = int(input())
ListA = list(map(int,input().split()))



Answer = 1
if N == 2:
    Answer = math.gcd(ListA[0],ListA[1])
else:
    for j in range(N):
        Lista = copy.deepcopy(ListA)
        Lista.pop(j)
        GCDa = math.gcd(Lista[0],Lista[1])
        proAnswer = GCDa
        for i in range(N-1):
            GCDa = math.gcd(Lista[i],GCDa)
            if GCDa == 1:
                break
            Answer = max(GCDa,proAnswer,Answer)

print(Answer)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
alist = list(map(int,input().split()))
aalist = alist[:]
mx = 0
for i in range(n):
    alist.pop(i)
    for j in range(1,n-1):
            alist[j] = math.gcd(alist[j], alist[j-1])
    mx = max(mx,alist[n-2])
    alist = aalist[:]
print(mx)

Submission status: Runtime Error

Solution code:
import math

N = int(input())
A = list(map(int, input().split()))
left = [0]*N
right = [0]*N

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

right_gcd = A[-1]
right[-1] = A[-1]
for i in range(N-2, 0, -1):
    right[i] = math.gcd(right_gcd, A[i])

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

print(max_val)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
left = [0]*N
right = [0]*N

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

right_gcd = A[-1]
right[-1] = A[-1]
for i in range(N-2, 0, -1):
    right[i] = math.gcd(right_gcd, A[i])

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

print(max_val)

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed=True):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N = iip(False)
    A = iip()

    A.sort()
    A1 = [i for i in A]
    A2 = [i for i in A]

    ss1 = soinsuu_bunkai(A[0])
    ss2 = soinsuu_bunkai(A[1])
    ss1.extend(ss2)


    #print(A)
    ak1 = 1
    for i in ss1:
        out = 0
        ahk = None
        for j, a in enumerate(A1):
            if a % i != 0:
                out += 1
                if out == 2: #2回アウトなら終了。
                    break
                else:
                    ahk = j
            else:
                A1[j] //= i
        if out == 2:
            continue
        elif out == 1:
            ah1[ahk] *= i
        else:
            ak1 *= i

    #print(ak1)
    #print(ah1)
    #print(ak2)
    #print(ah2)
    print(ak1*max(ah1))



#####################################################ライブラリ集ここから

def fprint(s):
    for i in s:
        print(i)

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
class SegmentTree:
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length()
        self.default = default
        self.dat = [default]*(self.size*2-1)
        self.f = f

    def update(self, i, x):
        i += self.size-1
        self.dat[i] = x
        while i > 0:
            i = (i-1) >> 1
            self.dat[i] = self.f(self.dat[i*2+1], self.dat[i*2+2])

    def query(self, l, r, k=0, L=0, R=None):
        if R is None:
            R = self.size
        if R <= l or r <= L:
            return self.default
        if l <= L and R <= r:
            return self.dat[k]
        else:
            lres = self.query(l, r, k*2+1, L, (L+R) >> 1)
            rres = self.query(l, r, k*2+2, (L+R) >> 1, R)
            return self.(lres, rres)

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

n = int(input())
a = list(map(int, input().split()))
s = SegmentTree(n, gcd)
for i in range(n):
    s.update(i, a[i])

ans = 1
for i in range(n):
    left = s.query(0, i)
    right = s.query(i+1, n)
    res = gcd(left, right)
    if ans < res:
        ans = res
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
D = [A[i+1]-A[i] for i in range(len(A)-1)]
 
if N == 2:
  print(max(A))
elif len(set(A))==1:
  print(A[0])
else:
  for d in D:
    cnt = 0
    for a in A:
      if a%d != 0:
        cnt = cnt+1
    if cnt <=1:
      print(d)
      break

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
D = [A[i+1]-A[i] for i in range(len(A)-1)]
 
if N == 2:
  print(max(A))
elif len(set(A))==1:
  print(A[0])
else:
  for d in D:
    cnt = 0
    for a in A:
      if a%d != 0:
        cnt = cnt+1
    if cnt <=1:
      print(i)
      break

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split())).sort()
D = [A[i+1]-A[i] for i in range(len(A)-1)]
 
if N == 2:
  print(max(A))
elif len(set(A))==1:
  print(A[0])
else:
  for d in D:
    cnt = 0
    for a in A:
      if a%d != 0:
        cnt = cnt+1
    if cnt <=1:
      print(i)
      break

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split())).sort()
D = [A[i+1]-A[i] for i in range(len(A)-1)]

if N == 2:
  print(max(A))
else:
  for i in reversed(range(0, min(A)+1)):
    cnt = 0
    for a in A:
      if a%i != 0:
        cnt = cnt+1
    if cnt <=1:
      print(i)
      break

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split())).sort()
D = [A[i+1]-[i] for i in range(A-1)]

if N == 2:
  print(max(A))
elif set(D) == {0}:
  print()
else:
  for i in D:
    cnt = 0
    ans = 0
    for a in A:
      if a%i != 0:
        cnt = cnt+1
        if cnt <=1:
          ans = cnt
          break
    if ans != 0:
      print(ans)
      break

Submission status: Runtime Error

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

if N == 2:
  print(max(A))
else:
  for i in reversed(range(0, min(A)+1)):
    cnt = 0
    ans = 0
    for a in A:
      if a%i != 0:
        cnt = cnt+1
        if cnt <=1:
          ans = cnt
          break
    if ans != 0:
      print(ans)
      break

Submission status: Runtime Error

Solution code:
def main():
    from collections import deque
    from functools import reduce
    from math import gcd

    n, *a = map(int, open(0).read().split())
    q = deque(a)
    ans = 0
    for i in range(n):
        t = q.popleft()
        g = reduce(gcd, q)
        ans = max(ans, g)
        q.append(t)
        q.rotate(-1)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    from functools import reduce
    from math import gcd

    n, *a = map(int, open(0).read().split())
    g = [reduce(gcd, a[:i]+a[i+1:]) for i in range(n)]
    ans = max(g)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
def gcd(a, b):
	if a > b:
		a, b = b, a
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
n = int(input())
a = np.array([int(x) for x in input().split()])
np.sort(a)
l = np.zeros(n + 1)
r = np.zeros(n + 1)
m = np.zeros(n)
for i in range(n):
	l[i + 1] = gcd(l[i], a[i])
for i in reversed(range(n)):
	r[i] = gcd(r[i + 1], a[i])
for i in range(n):
	m[i] = gcd(l[i], r[i + 1])
print(int(np.max(m)))

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
from fractions import gcd

class SegmentTree:
    def __init__(self, N, func, I):
        self.sz = N
        self.func = func
        self.I = I
        self.seg = [I for i in range(self.sz * 2)]
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k //= 2
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])
 
    def query(self, a, b):
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a % 2 == 1:
                R = self.func(R, self.seg[a])
                a += 1
            if b % 2 == 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a //= 2
            b //= 2
        return R

def main():
    N = int(readline())
    m = map(int,read().split())
    seg = SegmentTree(N , gcd , 0)
    for i in range(N):
        seg.assign(i , next(m))
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

main()

Submission status: Runtime Error

Solution code:
import math
import copy

N = int(input())
A = sorted(map(int, input().split()))
lans = 0

for i in range(N):
  a = copy.copy(A)
  del a[i]
  ans = a[0]
  for j in range(N-1):
    ans = math.gcd(ans, a[j])
  if lans < ans:
    lans = ans
  

print(lans)

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
import copy

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

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

ans = 0
for i in range(n-1):
    tmp_list = copy.copy(a_list)
    tmp_list.pop(i)
    #print(tmp_list)
    tmp = gcd(*tmp_list)
    #print(tmp)
    if tmp > ans:
        ans = tmp
    
print(ans)

Submission status: Runtime Error

Solution code:
from fractions import math

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

if n==1:
    print(10**9)
    exit()

if n==2:
    print(max(a))
    exit()

def is_prime(n):
    if n == 1:
        return True
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


if len(set(a)) == 1:
    print(a[0])
    exit()

sosu = []

if is_prime(a[0]):
    gcd_a = a[1]
    for i in range(2, n):
        gcd_a = gcd(gcd_a, a[i])
    print(gcd_a)
    exit()
else:
    gcd_a = a[0]

for i in range(1, n):
    tmp = gcd(gcd_a, a[i])
    if tmp == 1:
        sosu.append(a[i])
    else:
        gcd_a = tmp

if len(sosu)>1:
    print(1)
    exit()
elif len(sosu)==1:
    print(gcd_a)
    exit()
else:
    sosu2 = []

    if is_prime(a[0]//gcd_a):
        gcd_a_ = a[1]//gcd_a
        for i in range(2, n):
            gcd_a_ = gcd(gcd_a_, a[i]//gcd_a)
        print(gcd_a_*gcd_a)
        exit()
    else:
        gcd_a_ = a[0]//gcd_a

    for i in range(1, n):
        tmp = gcd(gcd_a_, a[i]//gcd_a)
        if tmp == 1:
            sosu2.append(a[i]//gcd_a)
        else:
            gcd_a_ = tmp

    if len(sosu2) > 1:
        print(gcd_a)
    else:
        print(gcd_a_*gcd_a)