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 fractions import gcd
n=int(input())
a=list(map(int, input().split()))
List1=[0]*n
List1[0]=a[0]
List2=[0]*n
List2[0]=a[-1]
for i in range(1, n):
    List1[i]=gcd(List1[i-1], a[i])
    List2[i]=gcd(List2[i-1], a[-i-1])
ans=List2[-2]
for i in range(1, n-1):
    ans=max(ans, gcd(List1[i-1], List2[n-i-2]))
ans=max(ans,List1[n-2])
print(ans)

Solution (Python):
from functools import reduce
from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
A = list(set(a))
ans = [reduce(gcd, A)]

if len(A) == 1:
    print(A[0])
    exit()
for i in A:
    b = sorted(A)
    b.remove(i)
    if a.count(i) == 1:
        ans.append(reduce(gcd, b))

print(max(ans))

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

N = int(input())
A = list(map(int, input().split()))
divisors = sorted(make_divisors(A[0]) + make_divisors(A[1]), reverse=True)

ans = 0
for d in divisors:
    ok_cnt = 0
    for a in A:
        if a % d == 0:
            ok_cnt += 1
    if ok_cnt >= N-1:
        ans = d
        break
print(ans)

Solution (Python):


import sys
import fractions

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def gcd(x, y):
    if x % y == 0:
        return y
    else:
        x, y = y, x % y
        return gcd(x, y)


def main():
    n = II()
    A = LI()
    A.sort()
    A.reverse()

    pre = [0] * n
    pre[0] = A[0]
    for i in range(1, n):
        pre[i] = gcd(pre[i - 1], A[i])
    res = pre[-1]
    for i in range(n):
        t = pre[i]
        for j in range(i + 2, n):
            t = gcd(t, A[j])
            if t == pre[j - 1]:
                t = -1
                break
        res = max(res, t)

    t = A[1]
    for a in A[1:]:
        t = gcd(t, a)

    return max(res, t)


print(main())

Solution (Python):
def divisor(x):
    y = list()
    for i in range(1, int(x ** 0.5 + 1)):
        if x % i == 0:
            y.append(i)
            y.append(x // i)
    return y

n = int(input())
a = list(map(int, input().split()))
a.sort()
d0 = divisor(a[0])
d1 = divisor(a[1])
d = dict.fromkeys(d0 + d1)
ans = 1
for di in sorted(list(d.keys()))[::-1]:
    flag = False
    ans_flag = True
    for ai in a:
        if ai % di != 0:
            if flag:
                ans_flag = False
                break
            else:
                flag = True
    if ans_flag:
        ans = di
        break
print(ans)

Solution (Python):
import fractions


def gcd(l, t):
    a = l.pop(0)
    for v in l:
        a = fractions.gcd(a, v)
        if a <= t:
            break
    return a


N = int(input())
*A, = map(int, input().split())
A.sort()

dp = [[1]*N for i in range(2)]
dp[0][0] = A[0]

a, b = A[0], A[-1]
for i in range(1, N):
    a = fractions.gcd(a, A[i])
    dp[0][i] = a
    b = fractions.gcd(b, A[N-i])
    dp[1][N-i] = b

ans = 1
for i in range(N):
    g = 1
    if i == 0:
        g = dp[1][1]
    elif i == (N-1):
        g = dp[0][-2]
    else:
        g = fractions.gcd(dp[0][i-1], dp[1][i+1])
    if g > ans:
        ans = g
print(ans)

Solution (Python):
def divisor(x):
    i = 1
    d = []
    while i*i <= x:
        if x%i == 0:
            d.append(i)
            d.append(x//i)
        i += 1
    return d

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

ans = 1
for i in range(2):
    for d in divisor(a[i]):
        ct = 0
        for j in a:
            if j%d == 0:
                ct += 1
        if ct >= n-1:
            ans = max(ans, d)

print(ans)

Solution (Python):
N = int(input())
A = [int(_) for _ in input().split()]

from fractions import gcd

xs1 = []

r = A[0]
for x in A:
    r = gcd(x, r)
    xs1.append(r)

xs2 = []

r = A[-1]
for x in A[::-1]:
    r = gcd(x, r)
    xs2.append(r)

xs2 = xs2[::-1]




result = max(xs1[-2], xs2[1])

for i in range(N - 2):
    r = gcd(xs1[i], xs2[i + 2])
    result = max(result, r)

print(result)

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


def gcd(a, b):
    if a < b:
        a, b = b, a
    assert a >= b
    r = a % b
    if r == 0:
        return b
    
    else:
        return gcd(b, r)


gcd_list_l = list()
gcd_list_r = list()

for i in range(0, N):
    if i == 0:
       value = As[i]
    else:
        value = gcd(gcd_list_l[-1], As[i])
    
    gcd_list_l.append(value)

for i in range(N)[::-1]:
    if i == N - 1:
        value = As[i]
    else:
        value = gcd(gcd_list_r[-1], As[i])
    gcd_list_r.append(value)

gcd_list_r.reverse()




ans = 0
for i in range(N):
    if i == 0:
        value = gcd_list_r[i + 1]
    elif i == N - 1:
        value = gcd_list_l[i - 1]
    else:
        value = gcd(gcd_list_l[i - 1], gcd_list_r[i + 1])
    
    ans = max(value, ans)
print(ans)

Solution (Python):
from fractions import gcd

n = int(input())
a_list = [int(i) for i in input().split()]

l_list = [a_list[i] for i in range(n)]
r_list = [a_list[i] for i in range(n)]
r_list.reverse()

for i in range(1, n):
    l_list[i] = gcd(a_list[i], l_list[i-1])
for i in range(1, n):
    r_list[i] = gcd(r_list[i-1], a_list[n-i-1])

gcd_list = [0]
if n > 2:
    gcd_list = [gcd(l_list[i-1], r_list[n-i-2]) for i in range(1, n-1)]
gcd_0 = r_list[n-2]
gcd_n = l_list[n-2]
ans = max(max(max(gcd_list), gcd_0), gcd_n)
print(ans)

Solution (Python):
from fractions import gcd

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

if N == 2:
    print(max(A))
else:
    a = gcd(A[1], A[2])
    b = gcd(A[0], A[2])
    c = gcd(A[0], A[1])
    mx = max(a, b, c)
    mn = gcd(c, A[2])

    for a in A[3:]:
        new = gcd(mx, a)
        mx = max(new, mn)
        mn = gcd(mn, a)
    print(mx)

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


n = int(input())
a = [int(item) for item in input().split()]

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

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

ans = -1

for i in range(n):
    ans = max(ans, gcd(g_pre[i - 1], g_suf[i + 1]))

print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A.sort()
def divisors(n):
    div = set()
    A = 1
    while A*A <= n:
        if n%A == 0:
            if A*A == n:
                div.add(A)
            else:
                B = n//A
                div.add(A)
                div.add(B)
        A += 1
    return div
div = list(divisors(A[0]) | divisors(A[1]))
m = 0
for x in div:
    count = 0
    for a in A:
        if a%x != 0:
            count += 1
    if count <= 1:
        m = max(m, x)
print(m)

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0:
        a, b = b, a % b
    return b

g = [None] * N
grev = [None] * N
g[0] = A[0]
grev[-1] = A[-1]
for i in range(1, N):
    g[i] = gcd(g[i-1], A[i])
    grev[-1-i] = gcd(grev[-i], A[-1-i])
maxgcd = max(grev[1], g[N-2])
for i in range(1, N-1):
    maxgcd = max(maxgcd, gcd(g[i-1], grev[i+1]))
print(maxgcd)

Solution (Python):


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

appear_D = {}


def sosuu(n):
    output = []
    for i in range(1, int(pow(n, 0.5))+1):
        if n % i == 0:
            output.append(i)
            if i != n // i:
                output.append(n // i)

    return output


ans_cantdidate = []

min_fst = a[0]
for i in range(n):
    if a[i] < min_fst:
        min_fst = a[i]

min_snd = a[0] if a[0] != min_fst else a[1]
for i in range(n):
    if min_fst < a[i] < min_snd:
        min_snd = a[i]

sosuus = set(sosuu(min_fst)) | set(sosuu(min_snd))
for num in sosuus:
    not_common = 0
    for i in range(n):
        if a[i] % num > 0:
            not_common += 1
        if not_common > 1:
            break
    if not_common < 2:
        ans_cantdidate.append(num)

print(max(ans_cantdidate))

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator



inf = float('inf')
N = 0
A = []


def set_inputs():
    global N, A
    N = get_int()
    A = get_li()
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    
    forward = [A[0]]
    for a in A[1:]:
        forward.append(gcd(forward[-1], a))
    backward = [A[-1]]
    for a in reversed(A[:-1]):
        backward.append(gcd(backward[-1], a))
    backward.reverse()
    ans = max(forward[-2], backward[1])
    for i in range(1, len(A)-1):
        ans = max(ans, gcd(forward[i-1], backward[i+1]))
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Solution (Python):
def gcd(x, y):
  b = max(x, y)
  s = min(x, y)
  r = b % s
  while r != 0:
    b = s
    s = r
    r = b % s
  return s

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

ma = 0
L = [[]] * N
all = gcd(A[0], A[1])
L[1] = [A[0], A[1]]

for i in range(2, N):
  t = [all]
  all = gcd(all, A[i])
  for j in L[i - 1]:
    k = gcd(j, A[i])
    if k not in t:
      t.append(k)
  L[i] = t

Ans = max(L[-1])

print(Ans)

Solution (Python):
n = int(input())
A = [int(a) for a in input().split()]

A.sort()
A_min = A[1]

def func():
    for i in range(A_min, 0, -1):
        cnt = 0
        for j in range(n):
            if cnt == 0:
                if A[j] % i > 0:
                    cnt += 1
                    bad = j
            elif cnt == 1:
                if A[j] % i > 0:
                    cnt += 1
                    break

        if cnt < 2:
            return i

result = func()
print(result)

Solution (Python):
from fractions import gcd

n = int(raw_input())
L = map(int, raw_input().split())

D1 = [0]*n
D2 = [0]*n

for i in xrange(1, n):
    D1[i] = gcd(D1[i-1], L[i-1])

for i in xrange(n-2, -1, -1):
    D2[i] = gcd(D2[i+1], L[i+1])

M = [None]*n

for i in xrange(n):
    M[i] = gcd(D1[i], D2[i])

print max(M)

Solution (Python):
def make_divisors(n,m):
    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)
    for i in range(1, int(m**0.5)+1):
        if m % i == 0:
            divisors.append(i)
            if i != m // i:
                divisors.append(m//i)

    divisors.sort()
    return divisors

N=int(input())

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

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

div=(make_divisors(A[0],A[1]))
div=list(set(div))
div.sort(reverse=True)
if len(A)<=2:
  print(div[0])
  exit()
for i in div:
  count=0
  for a in A[2:]:
    if a%i!=0:
      count+=1
    if count==2:
      break
  if count==0 or (count==1 and A[0]%i==0 and A[1]%i==0):
    print(i)
    exit()

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


def make_divisors(n):
    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


A1 = make_divisors(A[0])
A2 = make_divisors(A[1])
experiment = []
for i in range(0, len(A1)):
    experiment.append([A1[i], 1])

flag = 1
for i in range(0, len(A2)):
    for j in range(0, len(A1)):
        if A2[i] == A1[j]:
            experiment[j][1] = 2
            flag = 0
    if flag == 1:
        experiment.append([A2[i], 1])
    flag = 1

for i in range(2, N):
    for j in range(0, len(experiment)):
        if A[i] % experiment[j][0] != 0:
            experiment[j][1] -= 1
max = experiment[0][0]
for i in range(0, len(experiment)):
    if experiment[i][1] > 0 and experiment[i][0] > max:
        max = experiment[i][0]

print("{}".format(max))

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

n=int(input())
at=[int(i) for i in input().split()]
a=set(at)
d={}
for i,j in enumerate(a):
    t=div(j)
    for k in t:
        if k in d:
            d[k]+=1
        elif i==0 or k not in d:
            d[k]=1
ans=1
for i in d:
    x=0
    for j in at:
        if j%i: x+=1
    if x<2: ans=max(ans,i)
print(ans)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    a,b,t = LI()
    k = t//a
    print(k*b)
    return


def B():
    n = I()
    v = LI()
    c = LI()
    ans = 0
    for i in range(n):
        if v[i] > c[i]:
            ans += (v[i]-c[i])
    print(ans)
    return


def C():
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b%a, a)
    n = I()
    a = LI()
    m = math.ceil(n**0.5)
    f = [0 for i in range(m)]
    for i in range(m):
        b = a[m*i:min(n,m*(i+1))]
        if b:
            g = b[0]
            for j in b[1:]:
                g = gcd(g,j)
            f[i] = g
        else:
            f.pop(-1)
    ans = 1
    for i in range(n):
        j = i//m
        c = f[:j]+f[j+1:]+a[m*j:i]+a[i+1:min(n,m*(j+1))]
        g = c[0]
        for k in c[1:]:
            g = gcd(g, k)
        ans = max(ans,g)
    print(ans)
    return


def D():
    n = I()
    a = LI()
    k = 0
    for i in a:
        if i < 0:
            k += 1
    ans = 0
    m = float("inf")
    for i in a:
        ans += abs(i)
        m = min(m,abs(i))
    if k%2:
        ans -= 2*m
    print(ans)
    return



if __name__ == "__main__":
    C()

Solution (Python):
def gcd (a, b):
	x1, x2 = 0, 1
	y1, y2 = 1, 0
	q = 0
	while b != 0:
		x1, x2 = x2, x1 - q * x2
		y1, y2 = y2, y1 - q * y2
		q = a // b
		a, b = b, a % b
	return a, x2, y2



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

d_left = [0] * N
d_right = [0] * N
d_left[0] = A[0]
d_right[N-1] = A[N-1]
for i in range(1, N):
	d_left[i], _, _ = gcd(d_left[i-1], A[i])
	d_right[N-i-1], _, _ = gcd(d_right[N-i], A[N-i-1])

max_d = max(d_right[1], d_left[N-2])
for i in range(1, N-1):
	max_d = max(max_d, gcd(d_left[i-1], d_right[i+1])[0])
print(max_d)

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


def kari():
    a = list(map(int, input().split()))
    b = map(int, input().split())


def start_process(num, data):
    kouyakusuu1, kouyakusuu2, kouyakusuu3 = gcd(data[0], data[1]), max(data[0], data[1]), min(data[0], data[1])
    

    for i in range(2, num):
        if i == 2:
            a = gcd(data[i], kouyakusuu2)
            b = gcd(data[i], kouyakusuu3)
            kari1 = max(a, b)
            kari2 = kouyakusuu1

            kari3 = gcd(data[i], kouyakusuu1)
        else:
            kari1 = gcd(data[i], kouyakusuu2)
            kari2 = kouyakusuu1

            kari3 = gcd(data[i], kouyakusuu1)



        kouyakusuu1 = kari3
        kouyakusuu2 = max(kari1, kari2)



    print(max(kouyakusuu1, kouyakusuu2))




def main():
    num = int(input())
    data = list(map(int, input().split()))
    start_process(num, data)



if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
import fractions

sys.setrecursionlimit(10000)
INF = float('inf')


def inp():
    return int(input())


def inl():
    return list(map(int, input().split()))


def inls():
    return input().split()


def Yesif(cond):
    print('Yes' if cond else 'No')


def YESIF(cond):
    print('YES' if cond else 'NO')


def yesif(cond):
    print('yes' if cond else 'no')


N = inp()
A = inl()

ans = set()
ans.add(A[1])
gcd = A[0]
for i, a in enumerate(A):
    if i == 0:
        continue

    news = set()
    for ss in ans:
        news.add(fractions.gcd(ss, a))
    ans = news

    new_gcd = fractions.gcd(gcd, a)
    if new_gcd < gcd:
        ans.add(gcd)
    gcd = new_gcd

print(max(ans))

Solution (Python):
import fractions

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

l = [a[0]]
for i in range(1, n - 1):
  l.append(fractions.gcd(l[-1], a[i]))
r = [a[-1]]
for i in range(1, n - 1):
  r.append(fractions.gcd(r[-1], a[-i-1]))
for i in range(n):
  if i == 0:
    res = r[-1]
  elif i == n - 1:
    res = max(res, l[-1])
  else:
    res = max(res, fractions.gcd(l[i-1], r[-i-1]))
print(res)

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

new_ans = 0
li = [0]*n
li2 = [0]*n

li[0] = a[0]
li2[n-1] = a[n-1]
for i in range(1,n):
    li[i] =fractions.gcd(li[i-1], a[i])

for i in range(1,n)[::-1]:
    li2[i-1] =fractions.gcd(li2[i], a[i-1])

ans =0
for i in range(1,n-1):
    tmp = fractions.gcd(li[i-1],li2[i+1])
    if ans < tmp:
        ans = tmp
ans = max(ans, li[n-2], li2[1])
print(ans)

Solution (Python):
from fractions import gcd
N = int(input())
A = [int(i) for i in input().split()]
g = A[0]
mini_index_1 = 0
mini_index_2 = 0
glist = [0]
for i in range(N):
    ng = gcd(g, A[i])
    if ng < g:
        mini_index_1 = i
        mini_index_2 = i-1
        g = ng
        glist.append(i)


ans = 1
gcddd = 0

for gindex in glist:
    gcddd = 0
    for i in range(N):
        if gindex == i:
            continue
        else:
            if gcddd == 0:
                gcddd = A[i]
            else:
                gcddd = gcd(gcddd, A[i])
    ans = max(ans, gcddd)
print(ans)

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

def gcd(x,y):
    if(y==0):
        return x
    return gcd(y,x%y)
pre = [dat[0]]
for d in dat[1:]:
    pre.append(gcd(pre[-1],d))
pre = [-1]+pre[:-1]
pos = [dat[-1]]
for d in dat[:-1][::-1]:
    pos.append(gcd(pos[-1],d))
pos = pos[::-1]
pos = pos[1:]+[-1]
res = 1
for i in range(n):
    if pre[i]==-1:
        res = max(res,pos[i])
    elif pos[i]==-1:
        res = max(res,pre[i])
    else:
        res = max(res,gcd(pre[i],pos[i]))
print(res)

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

def GCM(m,n):
    while n>0:
        m,n = n,m%n
    return m

fGCM = [0 for i in range(N)]
bGCM = [0 for i in range(N)]

fGCM[0]=A[0]
bGCM[N-1]=A[N-1]

for i in range(N-1):
    j = N-1-i
    fGCM[i+1]=GCM(fGCM[i],A[i+1])
    bGCM[j-1]=GCM(bGCM[j],A[j-1])

eGCM=[0 for i in range(N)]
eGCM[0]=bGCM[1]
eGCM[N-1]=fGCM[N-2]
for i in range(1,N-1):
    eGCM[i] = GCM(fGCM[i-1],bGCM[i+1])

ans = max(eGCM)
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
end = sorted(a)[1]

for i in range(end+1, 0, -1):
  x = 0
  for j in a:
    if j % i != 0:
      x += 1
    if x >= 2:
      break
  if x <= 1:
    print(i)
    break

Solution (Python):

import sys
from itertools import accumulate

try:
    from math import gcd
except Exception:
    from fractions import gcd

def solve(N: int, A: "List[int]"):
    gcds0 = list(accumulate(A, gcd))
    gcds1 = list(accumulate(A[::-1], gcd))[::-1]

    ret = 0
    for i in range(N):
        if i == 0:
            ret = max(ret, gcds1[i+1])
        if i == (N-1):
            ret = max(ret, gcds0[i-1])
        else:
            ret = max(ret, gcd(gcds0[i-1], gcds1[i+1]))
    print(ret)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [ int(next(tokens)) for _ in range(N) ]  
    solve(N, A)

if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
import fractions
a_list=list(map(int,input().split()))
f_list=[a_list[0]]
r_list=[a_list[n-1]]
for i in range(n-1):
    f=fractions.gcd(f_list[i],a_list[i+1])
    r=fractions.gcd(r_list[i],a_list[n-i-2])
    f_list.append(f)
    r_list.append(r)
Max=max(r_list[n-2],f_list[n-2])
for i in range(n-2):
    number=fractions.gcd(f_list[i],r_list[n-3-i])
    if number>Max:
        Max=number
print(Max)

Solution (Python):



from collections import deque
import heapq
import math
import bisect


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


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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
K = 17
N = int(input())
A = [0] * (2**K-1) + [int(a) for a in input().split()] + [0] * (2**K-N)
for i in range(2**K-1)[::-1]:
    A[i] = gcd(A[2*i+1], A[2*i+2])

def calc(i0):
    g = 0
    for k in range(K):
        i = (i0^(1<<k)) + (2**K-1)
        for l in range(k):
            i = (i-1) // 2
        g = gcd(g, A[i])
    return g
ma = 0
for i in range(N):
    ma = max(ma, calc(i))
print(ma)

Solution (Python):
import functools
import fractions
N = int(input())
A = [int(x) for x in input().split()]
GCD = functools.reduce(fractions.gcd, A)
B = sorted([a // GCD for a in A], reverse=True)
def ggcd(B, cancel):
  gcd = B[0]
  for b in B[1:]:
    _gcd = fractions.gcd(gcd, b)
    if _gcd == 1 and cancel > 0:
      _gcd = gcd
      cancel -= 1
    gcd = _gcd
  return gcd
print(GCD * max(ggcd(B, 1), ggcd(B[1:], 0)))

Solution (Python):
from fractions import gcd

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

cum_left = [A[0]]
cum_right = [A[N - 1]]
for i in range(1, N - 1):
    cum_left.append(gcd(cum_left[-1], A[i]))
    cum_right.append(gcd(cum_right[-1], A[N - 1 - i]))

ans = max(cum_left[N - 2], cum_right[N - 2])
for i in range(1, N - 1):
    ans = max(ans, gcd(cum_left[i - 1], cum_right[N - 2 - i]))
print(ans)

Solution (Python):
from fractions import gcd

N=int(input())
A=list(map(int,input().split()))
X=[A[0]]
Y=[A[-1]]
for i in range(N):
    X.append(gcd(X[-1],A[i]))
    Y.append(gcd(Y[-1],A[N-1-i]))
X=X[1:]
Y=Y[1:]
Y=Y[::-1]
ans=1
for i in range(N):
    if i==0:
        ans_=Y[i+1]
    elif i==N-1:
        ans_=X[i-1]
    else:
        ans_=gcd(X[i-1],Y[i+1])
    ans=max(ans,ans_)
print(ans)

Solution (Python):
import sys
from fractions import gcd

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

if N == 2:
  print(max(A))
  sys.exit()

g = gcd(A[0], A[1])
X = set([A[0], A[1]])

for a in A[2:]:
  XX = set([g])
  g = gcd(g, a)
  for x in X:
    XX.add(gcd(x, a))
  X = XX

print(max(X))

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

def main():
    n = int(input())
    arr = list(map(int, input().split()))
    left = [0] * n
    right = [0] * n
    left[0] = arr[0]
    right[-1] = arr[-1]
    for i in range(1, n):
        left[i] = gcd(left[i - 1], arr[i])
        right[n - i - 1] = gcd(right[n - i], arr[n - i - 1])
    m = max(left[-2], right[1])
    for i in range(1, n - 1):
        m = max(m, gcd(left[i - 1], right[i + 1]))
    print(m)
    return 0

main()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    a,b,t = LI()
    k = t//a
    print(k*b)
    return


def B():
    n = I()
    v = LI()
    c = LI()
    ans = 0
    for i in range(n):
        if v[i] > c[i]:
            ans += (v[i]-c[i])
    print(ans)
    return


def C():
    def gcd(a,b):
        if a == 0:
            return b
        return gcd(b%a, a)
    n = I()
    a = LI()
    if n <= 1000:
        ans = 1
        for i in range(n):
            b = a[:i]+a[i+1:]
            g = b[0]
            for j in b[1:]:
                g = gcd(g,j)
            ans = max(ans,g)
        print(ans)
    else:
        m = math.ceil(n**0.5)
        while len(a) < m**2:
            n += 1
            a.append(a[-1])
        f = [0 for i in range(m)]
        for i in range(m):
            b = a[m*i:m*(i+1)]
            g = b[0]
            for j in b[1:]:
                g = gcd(g,j)
            f[i] = g
        ans = 1
        for i in range(n):
            j = i//m
            c = f[:j]+f[j+1:]+a[m*j:i]+a[i+1:m*(j+1)]
            g = c[0]
            for k in c[1:]:
                g = gcd(g, k)
            ans = max(ans,g)
        print(ans)
    return


def D():
    n = I()
    a = LI()
    k = 0
    for i in a:
        if i < 0:
            k += 1
    ans = 0
    m = float("inf")
    for i in a:
        ans += abs(i)
        m = min(m,abs(i))
    if k%2:
        ans -= 2*m
    print(ans)
    return



if __name__ == "__main__":
    C()

Solution (Python):
n = int(input())
l = list(map(int, input().split()))
l.sort()
fir = l[0]
sec = l[1]
lfir = []
for i in range(1,int(fir**.5)+2):
  if fir % i == 0:
    lfir.append(i)
    lfir.append(fir//i)
for i in range(1,int(sec**.5)+2):
  if sec % i == 0:
    lfir.append(i)
    lfir.append(sec//i)
ok = 1
lfir = sorted(list(set(lfir)))
for i in lfir:
  cnt = 0
  for j in l:
    if j%i:
      cnt += 1
  if cnt < 2:
    ok = i
print(ok)

Solution (Python):
n = int(input())
a = [int(item) for item in input().split()]

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

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

bad_id = 0
max_div = 1
for j in range(10):
    if j == 5:
        bad_id == 0
        a.reverse()
    bid = bad_id
    init = False
    for i, item in enumerate(a):
        if i == bid:
            continue
        if not init:
            val = item
            div = val
            init = True
        else:
            val = gcd(div, item)
            if val != div:
                bad_id = i
                div = val
    max_div = max(div, max_div)
    
print(max_div)

Solution (Python):


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

def make_divisors(n):
    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

if n == 2:
    print(max(a))
else:
    list1 = make_divisors(a[0])
    list2 = make_divisors(a[1])
    list1.sort()
    list2.sort()
    flag1 = 0
    cand1 = 0
    for i in range(len(list1)):
        flag1 = 0
        for j in range(n):
            if a[j] % list1[i] != 0:
                flag1 += 1
        if flag1 <= 1:
            cand1 = list1[i]
    cand2 = 0
    for i in range(len(list2)):
        flag2 = 0
        for j in range(n):
            if a[j] % list2[i] != 0:
                flag2 += 1
        if flag2 <= 1:
            cand2 = list2[i]
    print(max(cand1,cand2))

Solution (Python):
from fractions import gcd


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


gcd_l = [0] * n
gcd_r = [0] * n
for i in range(n):
    if i == 0:
        gcd_l[i] = A[i]
        gcd_r[-i-1] = A[-i-1]
    else:
        gcd_l[i] = gcd(gcd_l[i-1], A[i])
        gcd_r[-i-1] = gcd(gcd_r[-i], A[-i-1])

ans = [0] * n
ans[0] = gcd_r[1]
ans[n-1] = gcd_l[n-2]
for i in range(1, n-1):
    ans[i] = gcd(gcd_l[i-1], gcd_r[i+1])
print(max(ans))

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

N=int(input())
A=list(map(int,input().split()))
d1,d2=[],[]
g1,g2=A[0],A[-1]
d1.append(g1)
d2.append(g2)
for n in range(1,N-1):
    g1=gcd(g1,A[n])
    g2=gcd(g2,A[-1-n])
    d1.append(g1)
    d2.append(g2)
dmax=max(d1[N-2],d2[N-2])
for n in range(N-2):
    d=gcd(d1[n],d2[N-3-n])
    if d>dmax:
        dmax=d
print(dmax)

Solution (Python):
def gcd(a, b):
  if a < b:
    a, b = b, a
  if b == 0:
    return a
  c = a % b
  return gcd(b, c)
  
n=int(input())
a=list(map(int,input().split()))
g1=[0 for i in range(n)]
g2=[0 for i in range(n)]
g1[0]=a[0]
g2[n-1]=a[n-1]
for i in range(1,n):
  g1[i]=gcd(g1[i-1],a[i])
for i in range(n-2,-1,-1):
  g2[i]=gcd(g2[i+1],a[i])
ans=1
for i in range(n-2):
  a=gcd(g1[i],g2[i+2])
  ans=max(ans,a)
ans=max(ans,g1[n-2],g2[1])
print(ans)

Solution (Python):

import sys
import math
import numpy as np
import itertools
import fractions


n = int(input())

a = [int(i) for i in input().split()]

hidari = [0]*n
migi   = [0]*n
hidari[0] = a[0]
for i in range(1,n):
    hidari[i]=fractions.gcd(hidari[i-1],a[i])
migi[n-1] = a[n-1]
for i in range(n-2,-1,-1):
    migi[i]=fractions.gcd(migi[i+1],a[i])

saidai=max(migi[1],hidari[n-2])
for i in range(1,n-1):
    saidai = max(saidai, fractions.gcd(hidari[i-1],migi[i+1]))


print(saidai)

Solution (Python):
import collections as c
ip = lambda : map(int, input().split())


from fractions import gcd
N = int(input())
A = [int(i) for i in input().split()]
dp = [[0,0,0] for _ in range(N+1)]
dp[1] = [A[0],0,A[0]]
dp[2] = [gcd(dp[1][0],A[1]),dp[1][0],max(A[1] ,gcd(dp[1][2],A[1]))]
for i in range(3,N+1):
    dp[i][0] = gcd(dp[i-1][0],A[i-1])
    dp[i][1] = dp[i-1][0]
    dp[i][2] = max(gcd(dp[i-1][1],A[i-1]),gcd(dp[i-1][2],A[i-1]))

print(max(dp[N]))