You are given a sequence of $n$ integers, $a_0,a_1,\ldots,a_{n-1}$. Find and print any integer $\boldsymbol{x}$ such that $\boldsymbol{x}$ is divisor of every $a_i$ except for exactly one element.

Input Format

The first line contains an integer, $n$, denoting the length of the sequence. 

The second line contains $n$ positive space-separated integers describing $a_0,a_1,\ldots,a_{n-1}$.

Constraints

$1\leq n\leq10^5$
$1\leq a_i\leq10^{18}$
It is guaranteed that a solution exists.

Output Format

Print any positive integer denoting $\boldsymbol{x}$ such that $\boldsymbol{x}$ is a divisor of exactly $n-1$ of the sequence's elements. $\boldsymbol{x}$ must be between $\mbox{1}$ and $2\cdot10^{18}$

Sample Input 0
4
3 6 18 12

Sample Output 0
6

Explanation 0

We are given the array $[3,6,18,12]$. There are two possible answers:

$x=6$ is a divisor of $\boldsymbol{6}$, $12$, and $\mbox{18}$ but not a divisor of $3$.
$x=2$ is a divisor of $\boldsymbol{6}$, $12$, and $\mbox{18}$ but not a divisor of $3$.

Thus, we can print either $\boldsymbol{6}$ or $2$ as our answer.

Source: hackerrank | Difficulty: MEDIUM
Tags: Number theory


Solutions:
import sys
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
if n == 1:
	print(a[0] + 1)
	sys.exit(0)

def divn(d):
	return sum((num % d == 0 for num in a))

def gcd(a, b):
	if min(a, b) == 0:
		return max(a, b)
	return gcd(b, a % b)
g = a[0]
for i in range(n):
	g = gcd(g, a[i])
for i in range(n):
	a[i] //= g
res = g
culprit = -1
g = a[0]
for i in range(n):
	g = gcd(g, a[i])
	if g == 1:
		culprit = i
		break
g = a[0 if culprit else 1]
for i in range(n):
	if i != culprit:
		g = gcd(g, a[i])
print(res * g)


from functools import lru_cache, reduce

@lru_cache(maxsize=None)
def gcd(m, n):
	if n:
		return gcd(n, m % n)
	else:
		return m

def gcdl(a):
	if a:
		return reduce(gcd, a)
	else:
		return 0
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
if n == 1:
	print(a[0] + 1)
elif n == 2:
	print(max(a))
else:
	mask = 1
	res = []
	while mask < n:
		v1 = gcdl([a[i] for i in range(n) if i & mask == 0])
		v2 = gcdl([a[i] for i in range(n) if i & mask > 0])
		if min(v1, v2):
			res.append(max(v1, v2))
		mask <<= 1
	print(gcdl(res))


def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
if n == 1:
	print(a[0] + 1)
else:
	lgcd = [None] * len(a)
	lgcd[0] = a[0]
	for i in range(1, len(a)):
		lgcd[i] = gcd(lgcd[i - 1], a[i])
	rgcd = [None] * len(a)
	rgcd[-1] = a[-1]
	for i in range(1, len(a)):
		rgcd[-(i + 1)] = gcd(rgcd[-i], a[-(i + 1)])
	for i in range(len(a)):
		if i == 0:
			g = rgcd[1]
		elif i + 1 == len(a):
			g = lgcd[-2]
		else:
			g = gcd(lgcd[i - 1], rgcd[i + 1])
		if a[i] % g != 0:
			print(g)
			break


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

def solve(A):
	if len(A) == 1:
		return A[0] + 1
	pre = [0]
	for a in A:
		pre.append(gcd(pre[-1], a))
	suf = [0]
	for a in reversed(A):
		suf.append(gcd(suf[-1], a))
	suf = suf[::-1]
	for i in range(len(A)):
		g = gcd(pre[i], suf[i + 1])
		if A[i] % g != 0:
			return g
n = int(input())
A = list(map(int, input().split()))
print(solve(A))


import sys

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
if n == 1:
	ans = a[0] + 1
else:
	gcd_forward = [a[0]]
	gcd_backward = [a[n - 1]]
	for i in range(1, n):
		gcd_forward.append(gcd(a[i], gcd_forward[-1]))
		gcd_backward.insert(0, gcd(a[n - i - 1], gcd_backward[0]))
	u = gcd_backward[1]
	v = gcd_forward[n - 2]
	if u > 1 and a[0] % u != 0:
		ans = u
	elif v > 1 and a[n - 1] % v != 0:
		ans = v
	else:
		for k in range(1, n - 1):
			u = gcd(gcd_backward[k + 1], gcd_forward[k - 1])
			if u > 1 and a[k] % u != 0:
				ans = u
				break
print(ans)


import sys

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
prefix = []
suffix = []
k = a[0]
l = a[len(a) - 1]
if n == 1:
	j = 1
	while True:
		if not a[0] % j == 0:
			break
		j += 1
	print(j)
else:
	for i in range(len(a) - 1):
		k = gcd(k, a[i])
		prefix.append(k)
		l = gcd(l, a[len(a) - i - 1])
		suffix.append(l)
	for i in range(len(a)):
		if i == 0:
			p = suffix[len(a) - 2]
		elif i == len(a) - 1:
			p = prefix[len(a) - 2]
		else:
			p = gcd(prefix[i - 2], suffix[len(a) - i - 2])
		if not a[i] % p == 0:
			print(p)


from fractions import gcd
import sys
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
gcdf = [a[0]]
gcdb = [a[n - 1]]
for i in range(1, n):
	gcdf.append(gcd(gcdf[i - 1], a[i]))
	gcdb.append(gcd(gcdb[i - 1], a[n - i - 1]))
gcdb = gcdb[::-1]
ans = -1
GCD = gcdb[0]
if n == 1:
	ans = a[0] + 1
elif gcdb[0] != gcdb[1]:
	ans = gcdb[1]
elif gcdf[n - 2] != gcdf[n - 1]:
	ans = gcdf[n - 1]
else:
	for i in range(1, n - 1):
		G = gcd(gcdf[i - 1], gcdb[i + 1])
		if G != GCD:
			ans = G
			break
print(ans)


from functools import reduce
from math import gcd
n = int(input())
xs = [int(x) for x in input().split()]
xs.sort()
if n == 1:
	res = xs[0] + 1
else:
	prefix = [0] * n
	suffix = [0] * n
	prefix[0] = xs[0]
	for i in range(1, n):
		prefix[i] = gcd(prefix[i - 1], xs[i])
	suffix[n - 1] = xs[n - 1]
	for i in range(n - 2, -1, -1):
		suffix[i] = gcd(suffix[i + 1], xs[i])
	for i in range(n):
		if i == 0:
			pre = 0
		else:
			pre = prefix[i - 1]
		if i == n - 1:
			suf = 0
		else:
			suf = suffix[i + 1]
		g = gcd(pre, suf)
		if xs[i] % g != 0:
			res = g
			break
print(res)


from fractions import gcd
n = int(input())
l = [int(x) for x in input().split()]
if n == 1:
	print(l[0] + 1)
	exit()
forward = [l[0]]
g = gcd(l[0], l[1])
for i in range(1, n):
	g = gcd(g, l[i])
	forward.append(g)
backward = [l[-1]]
g = gcd(l[-1], l[-2])
for i in range(n - 2, -1, -1):
	g = gcd(g, l[i])
	backward.append(g)
backward.reverse()
for i in range(n):
	if i == 0:
		r = backward[i + 1]
	elif i == n - 1:
		r = forward[i - 1]
	else:
		r = gcd(forward[i - 1], backward[i + 1])
	if l[i] % r != 0:
		print(r)
		break


import sys

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

def gcd_(ar):
	l = len(ar)
	if l == 0:
		return 0
	if l == 1:
		return ar[0]
	if l == 2:
		return gcd(ar[0], ar[1])
	l >>= 1
	d1 = gcd_(ar[:l])
	d2 = gcd_(ar[l:])
	return gcd(d1, d2)
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
if n == 1:
	print(a[0] + 1)
else:
	forward = [0] * n
	backward = [0] * n
	for i in range(1, n):
		forward[i] = gcd(a[i - 1], forward[i - 1])
		backward[i] = gcd(a[-i], backward[i - 1])
	for i in range(n):
		d = gcd(forward[i], backward[-(i + 1)])
		if a[i] % d != 0:
			print(d)
			break


import math
n = int(input())
a = [int(x) for x in input().split()]
if n == 1:
	print(a[0] + 1)
elif n == 2:
	print(max(a))
else:
	g = 0
	for x in a:
		g = math.gcd(g, x)
	for h in [math.gcd(a[0], a[1]), math.gcd(a[0], a[2]), math.gcd(a[1], a[2])]:
		nope = 0
		for x in a:
			i = math.gcd(h, x)
			if i > g:
				h = i
			else:
				nope += 1
		if nope == 1:
			print(h)
			break


from functools import reduce
from fractions import gcd
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))

def chosen_one(n, a):
	if n == 1:
		return a[0] + 1
	else:
		a_set = set(a)
		a_set = list(a_set)
		n = len(a_set)
		if n == 2:
			if a.count(a_set[0]) > 1:
				return a_set[0]
			else:
				return a_set[1]
		else:
			z = a_set[0]
			l_r = [z]
			for i in range(n - 1):
				z = gcd(z, a_set[i + 1])
				l_r.append(z)
			x = a_set[-1]
			r_l = [x]
			for i in range(-1, -n, -1):
				x = gcd(x, a_set[i - 1])
				r_l.append(x)
			res = 0
			r_l = r_l[::-1]
			for i in range(1, n - 1):
				if a_set[i] % gcd(l_r[i - 1], r_l[i + 1]) != 0:
					res = i
					return gcd(l_r[res - 1], r_l[res + 1])
			if a_set[0] % r_l[1] != 0:
				return r_l[1]
			if a_set[-1] % l_r[-2] != 0:
				return l_r[-2]
print(chosen_one(n, a))


import sys
from fractions import gcd
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
f = [0 for _ in a]
l = [0 for _ in a]
f[0] = a[0]
l[-1] = a[-1]
for i in range(1, n):
	f[i] = gcd(f[i - 1], a[i])
	l[n - i - 1] = gcd(l[n - i], a[n - i - 1])
if len(a) == 1:
	print(a[0] + 1)
elif a[0] % l[1]:
	print(l[1])
elif a[-1] % f[-2]:
	print(f[-2])
else:
	for i in range(1, n - 1):
		g = gcd(f[i - 1], l[i + 1])
		if a[i] % g:
			print(g)
			break


import sys
from time import time

def primes_gen(n):
	sieve = [True] * n
	for p in range(2, n):
		if sieve[p]:
			yield p
			for i in range(p + p, n, p):
				sieve[i] = False

def pf_gen(n, prms):
	for p in prms:
		if n < p:
			return
		cnt = 0
		while n % p == 0:
			cnt += 1
			n //= p
		if cnt != 0:
			yield (p, cnt)
	if n != 1:
		yield (n, 1)

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

def test(aa):
	N = pow(10, 6)
	prms = tuple(primes_gen(N + 1))
	for a in aa:
		pfs = tuple(pf_gen(a, prms))
	return None

def solve(aa):
	print('aa=%s' % (aa,), file=sys.stderr)
	if len(aa) == 1:
		return aa[0] + 1
	g = aa[0]
	for a in aa[1:]:
		g = gcd(g, a)
	print('g=%d' % g, file=sys.stderr)
	aa = [a // g for a in aa]
	print('aa=%s' % (aa,), file=sys.stderr)
	for (i, a) in enumerate(aa):
		h = a
		matches = 1
		for (j, b) in enumerate(aa):
			if i != j:
				new_h = gcd(h, b)
				if new_h != 1:
					h = new_h
					matches += 1
		print('i=%d a=%d h=%d matches=%d' % (i, a, h, matches), file=sys.stderr)
		if matches == len(aa) - 1:
			return g * h
	return None
tm = time()
_ = int(input())
aa = tuple(map(int, input().split()))
print(solve(aa))
print('time elapsed: %s' % (time() - tm), file=sys.stderr)


import sys

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
a = [0] + a
m = min(a)
ans = 0

def find(ar):
	an = [0] * len(ar)
	for i in range(1, len(ar)):
		an[i] = gcd(an[i - 1], ar[i])
	return an
pref = find(a)
suff = find(a[::-1])
suff = suff[::-1]
if n == 1:
	print(a[1] + 1)
else:
	for i in range(1, n):
		div1 = pref[i - 1]
		div2 = suff[i + 1]
		div = gcd(div1, div2)
		if a[i] % div != 0:
			print(div)
			exit(0)


from math import gcd
from functools import reduce
n = int(input().strip())
arr = list(map(int, input().strip().split(' ')))
if n == 1:
	print(arr[0] + 1)
else:
	g = 0
	for i in range(n):
		g = gcd(g, arr[i])
	for i in range(n):
		arr[i] //= g
	original_g = g
	g = 0
	for i in range(n):
		g_temp = gcd(g, arr[i])
		if g_temp == 1:
			if i == n - 1:
				continue
			elif gcd(g, arr[i + 1]) > 1:
				continue
			else:
				arr[i - 1] = arr[i]
				g = reduce(lambda x, y: gcd(x, y), arr)
				break
		g = g_temp
	print(g * original_g)


import sys
import math
import sys
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
if n == 1:
	print(a[0] + 1)
	sys.exit(0)
pre = [0] * n
pre[0] = a[0]
for i in range(1, n):
	pre[i] = math.gcd(pre[i - 1], a[i])
suf = [0] * n
suf[n - 1] = a[n - 1]
for i in range(n - 2, -1, -1):
	suf[i] = math.gcd(suf[i + 1], a[i])
x = [0] * n
x[0] = suf[1]
x[n - 1] = pre[n - 1]
for i in range(1, n - 1):
	x[i] = math.gcd(pre[i - 1], suf[i + 1])
for i in range(n):
	if a[i] % x[i] != 0:
		print(x[i])
		break


import sys
import math
n = int(input().strip())
a = list(map(int, input().strip().split(' ')))
prefixes = [a[0]]
for num in a[1:]:
	prefixes.append(math.gcd(num, prefixes[-1]))
suffixes = [a[-1]]
a.reverse()
for num in a[1:]:
	suffixes.insert(0, math.gcd(num, suffixes[0]))
a.reverse()
divisor = a[0] + 1
if n != 1:
	if a[0] % suffixes[1] != 0:
		divisor = suffixes[1]
	elif a[-1] % prefixes[-2] != 0:
		divisor = prefixes[-2]
	else:
		for i in range(1, n - 1):
			gcdOfRest = math.gcd(prefixes[i - 1], suffixes[i + 1])
			if a[i] % gcdOfRest != 0:
				divisor = gcdOfRest
				break
print(divisor)


from math import gcd
n = int(input())
A = list(map(int, input().split()))
if n == 1:
	print(A[0] + 1)
else:
	gauche = [0] * n
	droite = [0] * n
	g = 0
	for i in range(n):
		g = gauche[i] = gcd(g, A[i])
	g = 0
	for i in range(n - 1, -1, -1):
		g = droite[i] = gcd(g, A[i])
	for i in range(n):
		if i == 0:
			g = droite[i + 1]
		elif i == n - 1:
			g = gauche[i - 1]
		else:
			g = gcd(gauche[i - 1], droite[i + 1])
		if A[i] % g != 0:
			print(g)
			break


import random

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

def listGCD(L):
	if len(L) == 1:
		return L[0]
	if len(L) == 2:
		return gcd(L[0], L[1])
	return gcd(listGCD(L[::2]), listGCD(L[1::2]))

def AllButOneGCD(L):
	if len(L) == 1:
		return L[0] + 1
	a = listGCD(L[::2])
	b = listGCD(L[1::2])
	candidate = max(a, b)
	for i in range(5):
		random.shuffle(L)
		a = listGCD(L[::2])
		b = listGCD(L[1::2])
		candidate = gcd(candidate, max(a, b))
	return candidate
T = int(input())
A = [int(x) for x in input().split()]
print(AllButOneGCD(A))


import math
import os
import random
import re
import sys
from math import gcd
n = int(input())
a = list(map(int, input().rstrip().split()))

def solve(a, n):
	if n == 1:
		return a[0] + 1
	gcd_l = [a[0]]
	gcd_r = [a[n - 1]]
	for x in a:
		gcd_l.append(gcd(x, gcd_l[-1]))
	for x in reversed(a):
		gcd_r.insert(0, gcd(x, gcd_r[0]))
	for (i, x) in enumerate(a):
		if i == 0:
			d = gcd_r[i + 1]
		elif i == n - 1:
			d = gcd_l[i - 1]
		else:
			d = gcd(gcd_l[i - 1], gcd_r[i + 1])
		if x % d != 0:
			return d
print(solve(a, n))


import os
import sys
from math import gcd
n = int(input())
a = list(map(int, input().rstrip().split()))
if n == 1:
	print(a[0] + 1)
else:
	(prefix, suffix) = ([0], [0] * (n + 2))
	for i in range(n):
		prefix.append(gcd(a[i], prefix[i]))
	for i in reversed(range(n)):
		suffix[i] = gcd(suffix[i + 1], a[i])
	for i in range(n):
		curr = gcd(prefix[i], suffix[i + 2])
		if a[i] % curr != 0:
			print(curr)


import math

def calcul(n, a):
	if n == 1:
		return a[1] + 1
	else:
		prefix = [0] * (n + 2)
		suffix = [0] * (n + 2)
		for i in range(1, n + 1):
			prefix[i] = math.gcd(a[i], prefix[i - 1])
		for i in range(n, 0, -1):
			suffix[i] = math.gcd(suffix[i + 1], a[i])
		for i in range(1, n + 1):
			cur = math.gcd(prefix[i - 1], suffix[i + 1])
			if a[i] % cur != 0:
				return cur
n = int(input())
a = [0] + list(map(int, input().rstrip().split())) + [0]
print(calcul(n, a))


from math import gcd
from itertools import accumulate
from functools import reduce
import os
import random
import re
import sys

def GCD(numbers):
	if len(numbers) > 2:
		return reduce(lambda x, y: gcd(x, y), numbers)
	else:
		return gcd(numbers[0], numbers[1])

def solve(a):
	n = len(a)
	if n == 1:
		return a[0] + 1
	if n == 2:
		return max(a)
	left = list(accumulate(a, gcd))
	right = list(reversed(list(accumulate(reversed(a), gcd))))
	for i in range(len(a)):
		if i == 0:
			if a[i] % right[i + 1] > 0:
				return right[i + 1]
		elif i + 1 == n:
			if a[i] % left[i - 1] > 0:
				return left[i - 1]
		else:
			g = gcd(left[i - 1], right[i + 1])
			if a[i] % g > 0:
				return g
	return 'Not Found'
n = int(input())
a = list(map(int, input().rstrip().split()))
print(solve(a))


from math import gcd
n = int(input())
p = [0] * 1000001
s = [0] * 1000001
a = list(map(int, input().split()))
ki = [0] * n
if n == 1:
	print(a[0] + 1)
else:
	for i in range(1, n + 1):
		p[i] = gcd(a[i - 1], p[i - 1])
	for i in range(n, 0, -1):
		s[i] = gcd(s[i + 1], a[i - 1])
	for i in range(1, n + 1):
		curr = gcd(p[i - 1], s[i + 1])
		if a[i - 1] % curr != 0:
			print(curr)
			break


def mygcd(a, b):
	if a < b:
		(a, b) = (b, a)
	r = a % b
	while r > 0:
		(a, b) = (b, r)
		r = a % b
	return b
N = int(input())
A = list(map(int, input().split()))
if N == 1:
	print(A[0] + 1)
elif N == 2:
	print(max(A))
else:
	g = mygcd(A[0], A[1])
	ind = 1
	factor = 1
	if g > 1:
		for i in range(2, N):
			G = g
			g = mygcd(A[i], G)
			if g == 1:
				ind = i
				break
			if g < G:
				ind = i
		else:
			factor = g
			for i in range(N):
				A[i] = A[i] // g
	if ind == N - 1:
		print(G)
	else:
		g = A[N - 1]
		for i in range(ind + 1, N - 1):
			g = mygcd(A[i], g)
		for a in A[ind::-1]:
			G = g
			g = mygcd(a, G)
			if g == 1:
				g = G
		print(G * factor)


import math
import os
import random
import re
import sys
n = int(input())
a = list(map(int, input().rstrip().split()))
if n == 1:
	print(a[0] + 1)
elif n == 2:
	print(max(a[0], a[1]))
elif n == 3:
	tmp1 = math.gcd(a[0], a[1])
	tmp2 = math.gcd(a[1], a[2])
	print(max(tmp1, tmp2))
else:
	prefix = [0] * n
	suffix = [0] * n
	gcds = [0] * n
	prefix[0] = a[0]
	suffix[n - 1] = a[n - 1]
	for i in range(1, n):
		prefix[i] = math.gcd(a[i], prefix[i - 1])
	for i in range(1, n):
		suffix[n - 1 - i] = math.gcd(a[n - 1 - i], suffix[n - i])
	gcds[0] = suffix[1]
	gcds[n - 1] = prefix[n - 2]
	for i in range(1, n - 1):
		gcds[i] = math.gcd(prefix[i - 1], suffix[i + 1])
	for i in range(0, n):
		if gcds[i] != 1 and a[i] % gcds[i] != 0:
			print(gcds[i])


import math
import os
import random
import re
import sys
from functools import reduce
from fractions import gcd

def chosen_one(n, a):
	if n == 1:
		return a[0] + 1
	else:
		a_set = set(a)
		a_set = list(a_set)
		n = len(a_set)
		if n == 2:
			if a.count(a_set[0]) > 1:
				return a_set[0]
			else:
				return a_set[1]
		else:
			z = a_set[0]
			l_r = [z]
			for i in range(n - 1):
				z = gcd(z, a_set[i + 1])
				l_r.append(z)
			x = a_set[-1]
			r_l = [x]
			for i in range(-1, -n, -1):
				x = gcd(x, a_set[i - 1])
				r_l.append(x)
			res = 0
			r_l = r_l[::-1]
			for i in range(1, n - 1):
				if a_set[i] % gcd(l_r[i - 1], r_l[i + 1]) != 0:
					res = i
					return gcd(l_r[res - 1], r_l[res + 1])
			if a_set[0] % r_l[1] != 0:
				return r_l[1]
			if a_set[-1] % l_r[-2] != 0:
				return l_r[-2]
n = int(input())
a = list(map(int, input().rstrip().split()))
print(chosen_one(n, a))


import math
import os
import random
import re
import sys
from math import gcd

def chosen_gcd(a):
	if len(a) == 1:
		return a[0] + 1
	answer = 0
	for _ in range(2):
		seg_size = 1
		while seg_size < len(a):
			seg_size <<= 1
		seg_tree = [0] * seg_size + a + [a[-1]] * (seg_size - len(a))
		for i in range(seg_size - 1, -1, -1):
			seg_tree[i] = gcd(seg_tree[i * 2], seg_tree[i * 2 + 1])
		for (i, x) in enumerate(a):
			j = i + seg_size
			g = seg_tree[j ^ 1]
			while j > 3:
				j >>= 1
				g = gcd(g, seg_tree[j ^ 1])
			answer = max(answer, g)
		a.reverse()
	return answer
input()
a = [int(x) for x in input().split()]
answer = chosen_gcd(a)
print(answer)


import math
import os
import random
import re
import sys
n = int(input())
a = list(map(int, input().rstrip().split()))
D = 0
for x in a:
	D = math.gcd(D, x)
d = 0
i = 0
while math.gcd(d, a[i]) > D:
	d = math.gcd(d, a[i])
	i += 1
for i in range(i + 1, len(a)):
	d = math.gcd(d, a[i])
if d:
	print(d)
else:
	print(a[0] + 1)


import math
import os
import random
import re
import sys

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

def fun():
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	random.shuffle(a)
	if len(a) == 1:
		return a[0] + 1
	if gcd(a[0], a[1]) != 1:
		r = a[0]
	elif gcd(a[1], a[2]) == 0:
		r = a[0]
	else:
		r = a[1]
	flag = True
	temp = 0
	for i in range(1, n):
		temp = gcd(r, a[i])
		a[i - 1] = temp
		if temp != 1:
			r = temp
		else:
			flag = False
	a[n - 1] = r
	if flag:
		for i in range(n - 2, -1, -1):
			if a[i] != a[i + 1]:
				return a[i]
				break
	else:
		return r
print(fun())


import math
import os
import random
import re
import sys
from math import gcd
n = int(input())
a = list(map(int, input().rstrip().split()))
d = a[0]
if n == 1:
	print(d + 1)
else:
	for i in range(1, len(a)):
		d = gcd(d, a[i])
	for i in range(len(a)):
		a[i] //= d
	s = d
	d = a[0]
	i = 0
	while d != 1:
		i = i + 1
		d = gcd(d, a[i])
	sauv = d
	del a[i]
	d = a[0]
	for j in range(1, len(a)):
		d = gcd(d, a[j])
	print(d * sauv * s)


import math
import os
import random
import re
import sys
from fractions import gcd
n = int(input())
a = list(map(int, input().rstrip().split()))
if n == 1:
	print(a[0] + 1)
gcd_left = [0] * n
gcd_right = [0] * n
for i in range(n - 1):
	gcd_left[i + 1] = gcd(gcd_left[i], a[i])
	gcd_right[n - i - 2] = gcd(gcd_right[n - i - 1], a[n - i - 1])
for i in range(n):
	cgcd = gcd(gcd_left[i], gcd_right[i])
	if a[i] % cgcd != 0:
		print(cgcd)
		break


import heapq

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

def gcdL(L, a=None):
	if not L:
		return a
	else:
		g0 = L[0]
		for el in L:
			g0 = gcd(g0, el)
		if a:
			return gcd(a, g0)
		else:
			return g0

def lcm(a, b):
	return a * b // gcd(a, b)

def twosNeeded(n):
	n = n - 1
	count = 0
	while n:
		n = n // 2
		count += 1
	return count
n = int(input())
a = sorted(list(map(int, input().rstrip().split())), key=lambda x: -x)
if n == 1:
	print(a[0] + 1)
else:
	numSplits = twosNeeded(n)
	a.extend([lcm(a[-1], a[-2])] * (2 ** numSplits - n))
	n = 2 ** numSplits
	H = [(-gcdL(a[n // 2:]), -1, 0), (-gcdL(a[:n // 2]), -1, 1)]
	heapq.heapify(H)
	(negGCD, negSplit, outGroup) = heapq.heappop(H)
	while -negSplit < numSplits:
		split = -negSplit
		(dexLO, dexHI) = (outGroup * 2 ** (numSplits - split), (outGroup + 1) * 2 ** (numSplits - split))
		dexMID = (dexLO + dexHI) // 2
		heapq.heappush(H, (-gcdL(a[dexMID:dexHI], -negGCD), -(split + 1), 2 * outGroup))
		heapq.heappush(H, (-gcdL(a[dexLO:dexMID], -negGCD), -(split + 1), 2 * outGroup + 1))
		(negGCD, negSplit, outGroup) = heapq.heappop(H)
	print(-negGCD)


import math
import os
import random
import re
import sys
n = int(input())
a = list(map(int, input().rstrip().split()))
if n == 1:
	print(a[0] + 1)
s = [1] * n
p = [1] * n
p[0] = a[0]
s[n - 1] = a[n - 1]
for i in range(1, n):
	p[i] = math.gcd(a[i], p[i - 1])
for i in range(n - 2, -1, -1):
	s[i] = math.gcd(s[i + 1], a[i])
for i in range(0, n - 1, 1):
	if i == 0:
		if a[i] % s[i + 1] != 0:
			print(s[i + 1])
			break
	else:
		c = math.gcd(s[i + 1], p[i - 1])
		if a[i] % c != 0:
			print(c)
		if i == n - 1:
			if a[i] % p[i - 1] != 0:
				print(p[i - 1])
				break


import math
import os
import random
import re
import sys
from math import gcd

def solve(n, a):
	if n == 1:
		print(a[0] + 1)
	leftGCDs = [0 for i in range(0, n)]
	leftGCDs[0] = a[0]
	for i in range(1, n):
		leftGCDs[i] = gcd(leftGCDs[i - 1], a[i])
	rightGCDs = [0 for i in range(0, n)]
	rightGCDs[n - 1] = a[n - 1]
	for i in range(n - 2, 0, -1):
		rightGCDs[i] = gcd(rightGCDs[i + 1], a[i])
	i = 0
	while True:
		if i == 0:
			if a[i] % rightGCDs[i + 1] != 0:
				return rightGCDs[i + 1]
		elif i == n - 1:
			if a[i] % leftGCDs[i - 1] != 0:
				return leftGCDs[i - 1]
		else:
			otherGCD = gcd(leftGCDs[i - 1], rightGCDs[i + 1])
			if a[i] % otherGCD != 0:
				return otherGCD
		i = i + 1
n = int(input())
a = list(map(int, input().rstrip().split()))
print(solve(n, a))


import math
import os
import random
import re
import sys
from math import gcd
n = int(input())
A = list(map(int, input().split()))
if n == 1:
	print(A[0] + 1)
else:
	gauche = [0] * n
	droite = [0] * n
	g = 0
	for i in range(n):
		g = gauche[i] = gcd(g, A[i])
	g = 0
	for i in range(n - 1, -1, -1):
		g = droite[i] = gcd(g, A[i])
	for i in range(n):
		if i == 0:
			g = droite[i + 1]
		elif i == n - 1:
			g = gauche[i - 1]
		else:
			g = gcd(gauche[i - 1], droite[i + 1])
		if A[i] % g != 0:
			print(g)
			break


import math
import os
import random
import re
import sys
n = int(input())
a = list(map(int, input().rstrip().split()))
if len(a) == 1:
	print(a[0] + 1)
	sys.exit(0)
prefix1 = [a[0]]
for (i, x) in enumerate(a[1:]):
	prefix1.append(math.gcd(prefix1[i - 1], x))
prefix2 = [0] * len(a)
prefix2[len(a) - 1] = a[len(a) - 1]
for i in range(len(a) - 2, -1, -1):
	prefix2[i] = math.gcd(prefix2[i + 1], a[i])
for i in range(len(a)):
	if i == 0:
		lgcd = prefix2[i + 1]
	else:
		lgcd = prefix1[i - 1]
	if i == len(a) - 1:
		rgcd = prefix1[i - 1]
	else:
		rgcd = prefix2[i + 2]
	totalgcd = math.gcd(lgcd, rgcd)
	if a[i] % totalgcd != 0:
		print(totalgcd)
		break


import math
import os
import random
import re
import sys
from math import gcd

def findTheOne(a):
	if len(a) == 1:
		return a[0] + 1
	pre = [0]
	post = [0]
	for i in range(0, len(a)):
		pre.append(gcd(pre[i], a[i]))
		post.append(gcd(post[i], a[len(a) - i - 1]))
	pre.pop(-1)
	post.pop(-1)
	post.reverse()
	for i in range(0, len(a)):
		cur = gcd(pre[i], post[i])
		if a[i] % cur != 0:
			return cur
n = int(input())
a = list(map(int, input().rstrip().split()))
print(findTheOne(a))


import sys

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

def the_one(line):
	n = int(next(line))
	a = [0] + list(map(int, next(line).split()))
	if n == 1:
		print(a[1] + 1)
		return
	prefix = [0] * (n + 2)
	suffix = [0] * (n + 2)
	for i in range(1, n + 1):
		prefix[i] = gcd(a[i], prefix[i - 1])
	for i in range(n, 0, -1):
		suffix[i] = gcd(a[i], suffix[i + 1])
	for i in range(1, n + 1):
		curr = gcd(prefix[i - 1], suffix[i + 1])
		if a[i] % curr:
			print(curr)
			return
the_one(sys.stdin)


import math
import os
import random
import re
import sys
n = int(input())
lst = list(map(int, input().strip().split()))
if len(lst) == 1:
	print(lst[0] + 1)
	exit(0)
pref = [0]
suff = [0]
for i in range(len(lst) - 1):
	pref.append(math.gcd(lst[i], pref[len(pref) - 1]))
for i in range(len(lst) - 1, 0, -1):
	suff.append(math.gcd(lst[i], suff[len(suff) - 1]))
suff.reverse()
for i in range(len(lst)):
	if lst[i] % math.gcd(pref[i], suff[i]) != 0:
		print(math.gcd(pref[i], suff[i]))


import math
import os
import random
import re
import sys
import itertools
n = int(input())
a = list(map(int, input().rstrip().split()))
if len(a) == 1:
	print(a[0] + 1)
	sys.exit(0)
g1 = itertools.accumulate(a, math.gcd)
g2 = itertools.accumulate(a[::-1], math.gcd)
prf = [e for e in g1]
suf = [e for e in g2]
suf.append(0)
prf.insert(0, 0)
suf = suf[::-1]
suf.append(0)
k = 0
for i in range(1, n + 1):
	g = math.gcd(prf[i - 1], suf[i + 1])
	if a[k] % g != 0:
		print(g)
		break
	k = k + 1


import math
import os
import random
import re
import sys

def findans(a):
	if len(a) == 1:
		return a[0] + 1
	leftgcd = [0] * len(a)
	rightgcd = [0] * len(a)
	leftgcd[0] = a[0]
	rightgcd[len(a) - 1] = a[len(a) - 1]
	for i in range(1, len(a)):
		leftgcd[i] = math.gcd(leftgcd[i - 1], a[i])
	for i in range(len(a) - 2, -1, -1):
		rightgcd[i] = math.gcd(rightgcd[i + 1], a[i])
	for i in range(0, len(a)):
		temp = a[i]
		if i == 0:
			mygcd = rightgcd[1]
		elif i == len(a) - 1:
			mygcd = leftgcd[len(a) - 2]
		else:
			gcd1 = leftgcd[i - 1]
			gcd2 = rightgcd[i + 1]
			mygcd = math.gcd(gcd1, gcd2)
		if temp % mygcd != 0:
			return mygcd
n = int(input())
a = list(map(int, input().rstrip().split()))
print(findans(a))


import sys
import math
p = [0] * 10000000
s = [0] * 10000000
a = []
n = int(input())
if n == 1:
	print(int(input()) + 1)
	sys.exit()
a = list(map(int, input().split(' ')))
for i in range(n):
	p[i + 1] = math.gcd(a[i], p[i])
for j in range(n, 0, -1):
	s[j] = math.gcd(s[j + 1], a[j - 1])
for i in range(1, n + 1):
	cur = math.gcd(p[i - 1], s[i + 1])
	if a[i - 1] % cur != 0:
		print(cur)
		sys.exit()


import math
import os
import random
import re
import sys
n = int(input())
a = list(map(int, input().rstrip().split()))
if n == 1:
	print(a[0] + 1)
else:
	pre = [0]
	suf = [0]
	p = 0
	s = 0
	dup = a.copy()
	dup.reverse()
	for i in range(len(a)):
		pre.append(math.gcd(pre[p], a[i]))
		p += 1
	for i in range(len(dup)):
		suf.append(math.gcd(suf[s], dup[i]))
		s += 1
	suf.reverse()
	for i in range(len(a)):
		g = math.gcd(pre[i], suf[i + 1])
		if a[i] % g != 0:
			print(g)
			break


import math
import os
import random
import re
import sys
n = int(input())
a = list(map(int, input().rstrip().split()))
t = 0
l = [0]
l1 = []
t1 = 0
for i in a:
	t = math.gcd(t, i)
	l.append(t)
for i in a[::-1]:
	t1 = math.gcd(t1, i)
	l1.append(t1)
l1 = l1[::-1]
l1.append(0)
if n == 1:
	print(a[0] + 1)
else:
	for i in range(n):
		a1 = a[i]
		gd = math.gcd(l[i], l1[i + 1])
		if a1 == 0:
			continue
		if a1 % gd:
			print(gd)
			break


import math
import os
import random
import re
import sys
n = int(input())
a = list(map(int, input().rstrip().split()))
if n == 1:
	print(n + 1)
	exit()
k = a[::-1]
p = [0] * n
s = [0] * n
for i in range(len(p) - 1):
	x = math.gcd(a[i], p[i])
	p[i + 1] = x
for i in range(len(s) - 1):
	y = math.gcd(k[i], s[i])
	s[i + 1] = y
s = s[::-1]
for i in range(len(p)):
	g = math.gcd(p[i], s[i])
	try:
		if a[i] % g != 0:
			print(g)
			break
	except:
		pass


import math
import os
import random
import re
import sys
n = int(input())
a = list(map(int, input().rstrip().split()))
if n == 1:
	print(a[0] + 1)
p = []
s = []
le = len(a)
p.append(0)
s.append(0)
for x in range(1, le):
	p.append(math.gcd(p[x - 1], a[x - 1]))
for x in range(le - 1, 0, -1):
	s.insert(0, math.gcd(a[x], s[0]))
for x in range(0, n):
	z = math.gcd(p[x], s[x])
	if a[x] % z != 0:
		print(z)
		break


import math
import os
import random
import re
import sys
n = int(input())
a = list(map(int, input().rstrip().split()))
if n == 1:
	print(a[0] + 1)
else:
	p = [0]
	q = []
	r = 0
	for u in a:
		r = math.gcd(r, u)
		p.append(r)
	r = 0
	for u in a[::-1]:
		r = math.gcd(r, u)
		q.append(r)
	q = q[::-1]
	q.append(0)
	for i in range(n):
		l = a[i]
		d = math.gcd(p[i], q[i + 1])
		if d == 0:
			continue
		if l % d:
			print(d)
			break


import math
import os
import random
import re
import sys
n = int(input())
a = list(map(int, input().rstrip().split()))
if n == 1:
	print(a[0] + 1)
else:
	pre = [0]
	suf = [0]
	p = 0
	s = 0
	dup = a.copy()
	dup.reverse()
	for i in range(len(a)):
		pre.append(math.gcd(pre[p], a[i]))
		p += 1
	for i in range(len(dup)):
		suf.append(math.gcd(suf[s], dup[i]))
		s += 1
	suf.reverse()
	for i in range(len(a)):
		g = math.gcd(pre[i], suf[i + 1])
		if a[i] % g != 0:
			print(g)
			break


import math
import os
import random
import re
import sys
from math import gcd
n = int(input())
a = list(map(int, input().split()))
if n == 1:
	print(a[0] + 1)
	sys.exit()
pref = [0] * (n + 1)
suff = [0] * (n + 1)
for i in range(1, n):
	pref[i] = gcd(pref[i - 1], a[i - 1])
t = a[::-1]
for i in range(1, n):
	suff[i] = gcd(suff[i - 1], t[i - 1])
suff = suff[::-1]
for i in range(len(suff)):
	q = gcd(suff[i + 2], pref[i])
	if a[i] % q != 0:
		print(q)
		break


import math
import os
import random
import re
import sys

def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)
n = int(input())
a = list(map(int, input().rstrip().split()))
if n == 1:
	print(a[0] + 1)
else:
	lgcd = [-1] * n
	lgcd[0] = a[0]
	rgcd = [-1] * n
	rgcd[-1] = a[-1]
	for i in range(1, n):
		lgcd[i] = gcd(lgcd[i - 1], a[i])
	for i in range(n - 2, 0, -1):
		rgcd[i] = gcd(rgcd[i + 1], a[i])
	for i in range(n):
		if i == 0:
			g = rgcd[1]
		elif i == n - 1:
			g = lgcd[-2]
		else:
			g = gcd(lgcd[i - 1], rgcd[i + 1])
		if a[i] % g != 0:
			print(g)
			break


import math
import os
import random
import re
import sys
n = int(input())
a = list(map(int, input().rstrip().split()))
lenA = len(a)
if lenA == 1:
	print(a[0] + 1)
else:
	gcd1 = a[0]
	for i in range(1, lenA):
		gcd1 = math.gcd(gcd1, a[i])
	a1 = [x // gcd1 for x in a]
	finish = False
	while not finish:
		if a1[0] != 1:
			gcd2 = a1[0]
		else:
			gcd2 = a1[1]
			finish = True
		for i in range(1, lenA):
			gcd2Old = gcd2
			gcd2New = math.gcd(gcd2, a1[i])
			if gcd2New == 1:
				gcd2 = gcd2Old
				finish = True
			else:
				gcd2 = gcd2New
		a1 = [x // gcd2 for x in a1]
	print(gcd1 * gcd2)


from collections import Counter

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

def solve(n, a):
	if n == 1:
		return a[0] + 1
	elif n == 2:
		return max(a[0], a[1])
	l = [a[0]] * n
	r = [a[-1]] * n
	for i in range(1, n):
		l[i] = gcd(l[i - 1], a[i])
	for i in range(n - 2, -1, -1):
		r[i] = gcd(r[i + 1], a[i])
	g = []
	for i in range(n):
		if i == n - 1:
			g.append(l[i - 1])
		elif i == 0:
			g.append(r[i + 1])
		else:
			g.append(gcd(l[i - 1], r[i + 1]))
	cnt = Counter(g)
	if len(cnt) != 2:
		return None
	else:
		for x in g:
			if cnt[x] == 1:
				return x
	return None
print(solve(int(input()), list(map(int, input().split()))))


import sys
import math
p = [0] * 10000000
s = [0] * 10000000
a = []
n = int(input())
if n == 1:
	print(int(input()) + 1)
	sys.exit()
a = list(map(int, input().split(' ')))
for i in range(n):
	p[i + 1] = math.gcd(a[i], p[i])
for j in range(n, 0, -1):
	s[j] = math.gcd(s[j + 1], a[j - 1])
for i in range(1, n + 1):
	cur = math.gcd(p[i - 1], s[i + 1])
	if a[i - 1] % cur != 0:
		print(cur)
		sys.exit()


from math import gcd
n = int(input())
a = list(map(int, input().split()))
if n == 1:
	print(a[0] + 1)
	quit()
g = [a[0]]
h = [a[-1]]
for i in range(1, n):
	g.append(gcd(a[i], g[-1]))
	h.append(gcd(a[-i - 1], h[-1]))
h.reverse()
for i in range(1, n - 1):
	c = gcd(g[i - 1], h[i + 1])
	if a[i] % c:
		print(c)
		break
else:
	if a[0] % h[1]:
		print(h[1])
	else:
		print(g[-2])


import sys
import math
p = [0] * 10000000
s = [0] * 10000000
a = []
n = int(input())
if n == 1:
	print(int(input()) + 1)
	sys.exit()
a = list(map(int, input().split(' ')))
for i in range(n):
	p[i + 1] = math.gcd(a[i], p[i])
for j in range(n, 0, -1):
	s[j] = math.gcd(s[j + 1], a[j - 1])
for i in range(1, n + 1):
	cur = math.gcd(p[i - 1], s[i + 1])
	if a[i - 1] % cur != 0:
		print(cur)
		sys.exit()


import math
import os
import random
import re
import sys
n = int(input())
a = list(map(int, input().rstrip().split()))
if n == 1:
	print(a[0] + 1)
else:
	pr = [0]
	sf = [0]
	p = 0
	s = 0
	b = a.copy()
	b.reverse()
	for i in range(len(a)):
		pr.append(math.gcd(pr[p], a[i]))
		p += 1
	for i in range(len(b)):
		sf.append(math.gcd(sf[s], b[i]))
		s += 1
	sf.reverse()
	for i in range(len(a)):
		g = math.gcd(pr[i], sf[i + 1])
		if a[i] % g != 0:
			print(g)
			break


import math
import os
import random
import re
import sys

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
n = int(input())
a = list(map(int, input().rstrip().split()))
if len(a) == 1:
	print(n + 1)
	sys.exit(0)
prefix = [a[0]]
suffix = [a[-1]]
for i in range(1, len(a)):
	prefix.append(gcd(prefix[i - 1], a[i]))
	suffix.append(gcd(suffix[i - 1], a[len(a) - i - 1]))
suffix.reverse()
for i in range(1, len(a) - 1):
	g = gcd(prefix[i - 1], suffix[i + 1])
	if a[i] % g != 0:
		print(g)
		break
if a[0] % suffix[1] != 0:
	print(suffix[1])
if a[-1] % prefix[-2] != 0:
	print(prefix[-2])


from math import gcd
n = int(input())
A = list(map(int, input().split()))
if n == 1:
	print(A[0] + 1)
else:
	gauche = [0] * n
	droite = [0] * n
	g = 0
	for i in range(n):
		g = gauche[i] = gcd(g, A[i])
	g = 0
	for i in range(n - 1, -1, -1):
		g = droite[i] = gcd(g, A[i])
	for i in range(n):
		if i == 0:
			g = droite[i + 1]
		elif i == n - 1:
			g = gauche[i - 1]
		else:
			g = gcd(gauche[i - 1], droite[i + 1])
		if A[i] % g != 0:
			print(g)
			break


import math
import os
import random
import re
import sys
n = int(input())
a = list(map(int, input().rstrip().split()))
if n == 1:
	print(a[0] + 1)
else:
	pre = [0]
	suf = [0]
	p = 0
	s = 0
	dup = a.copy()
	dup.reverse()
	for i in range(len(a)):
		pre.append(math.gcd(pre[p], a[i]))
		p += 1
	for i in range(len(dup)):
		suf.append(math.gcd(suf[s], dup[i]))
		s += 1
	suf.reverse()
	for i in range(len(a)):
		g = math.gcd(pre[i], suf[i + 1])
		if a[i] % g != 0:
			print(g)
			break


from math import gcd
n = int(input())
l = list(map(int, input().split()))
l.sort()
if n == 1:
	print(l[0] + 1)
	exit()
p = [0] * 10000000
s = [0] * 10000000
ka = 0
for i in range(1, n + 1):
	p[i] = gcd(ka, l[i - 1])
	ka = p[i]
ka = 0
for i in range(n, 0, -1):
	s[i] = gcd(s[i + 1], l[i - 1])
	ka = s[i]
for i in range(1, n + 1):
	z1 = p[i - 1]
	z2 = s[i + 1]
	yo = gcd(z1, z2)
	if l[i - 1] % yo != 0:
		print(yo)
		exit()


import sys
import math
p = [0] * 10000000
s = [0] * 10000000
a = []
n = int(input())
if n == 1:
	print(int(input()) + 1)
	sys.exit()
a = list(map(int, input().split(' ')))
for i in range(n):
	p[i + 1] = math.gcd(a[i], p[i])
for j in range(n, 0, -1):
	s[j] = math.gcd(s[j + 1], a[j - 1])
for i in range(1, n + 1):
	cur = math.gcd(p[i - 1], s[i + 1])
	if a[i - 1] % cur != 0:
		print(cur)
		sys.exit()


import math
import os
import random
import re
import sys
n = int(input())
a = list(map(int, input().rstrip().split()))
if n == 1:
	print(a[0] + 1)
else:
	pre = [0]
	suf = [0]
	p = 0
	s = 0
	dup = a.copy()
	dup.reverse()
	for i in range(len(a)):
		pre.append(math.gcd(pre[p], a[i]))
		p += 1
	for i in range(len(dup)):
		suf.append(math.gcd(suf[s], dup[i]))
		s += 1
	suf.reverse()
	for i in range(len(a)):
		g = math.gcd(pre[i], suf[i + 1])
		if a[i] % g != 0:
			print(g)
			break


import sys
import math
p = [0] * 10000000
s = [0] * 10000000
a = []
n = int(input())
if n == 1:
	print(int(input()) + 1)
	sys.exit()
a = list(map(int, input().split(' ')))
for i in range(n):
	p[i + 1] = math.gcd(a[i], p[i])
for j in range(n, 0, -1):
	s[j] = math.gcd(s[j + 1], a[j - 1])
for i in range(1, n + 1):
	cur = math.gcd(p[i - 1], s[i + 1])
	if a[i - 1] % cur != 0:
		print(cur)
		sys.exit()


import sys
import math
p = [0] * 10000000
s = [0] * 10000000
a = []
n = int(input())
if n == 1:
	print(int(input()) + 1)
	sys.exit()
a = list(map(int, input().split(' ')))
for i in range(n):
	p[i + 1] = math.gcd(a[i], p[i])
for j in range(n, 0, -1):
	s[j] = math.gcd(s[j + 1], a[j - 1])
for i in range(1, n + 1):
	cur = math.gcd(p[i - 1], s[i + 1])
	if a[i - 1] % cur != 0:
		print(cur)
		sys.exit()


import sys
import math
p = [0] * 10000000
s = [0] * 10000000
a = []
n = int(input())
if n == 1:
	print(int(input()) + 1)
	sys.exit()
a = list(map(int, input().split(' ')))
for i in range(n):
	p[i + 1] = math.gcd(a[i], p[i])
for j in range(n, 0, -1):
	s[j] = math.gcd(s[j + 1], a[j - 1])
for i in range(1, n + 1):
	cur = math.gcd(p[i - 1], s[i + 1])
	if a[i - 1] % cur != 0:
		print(cur)
		sys.exit()


import math
import os
import random
import re
import sys
n = int(input())
a = list(map(int, input().rstrip().split()))
if n == 1:
	print(a[0] + 1)
else:
	b = [0] * (n + 1)
	c = [0] * (n + 1)
	for i in range(0, n):
		b[i + 1] = math.gcd(b[i], a[i])
	for i in range(n - 1, 0, -1):
		c[i] = math.gcd(c[i + 1], a[i])
	for i in range(1, n + 1):
		g = math.gcd(b[i - 1], c[i])
		if a[i - 1] % g != 0:
			print(g)
			break


import math
import os
import random
import re
import sys
n = int(input())
a = list(map(int, input().rstrip().split()))
res = 0
for i in range(0, len(a)):
	res = math.gcd(res, a[i])
res2 = 0
for i in range(len(a)):
	res2 = math.gcd(res2, a[i])
	if res2 == res:
		flag = i
		break
res = 0
for i in range(len(a)):
	if i != flag:
		res = math.gcd(res, a[i])
if n < 2:
	print(a[0] + 1)
else:
	print(res)


import math, sys, io, itertools
from math import gcd

def solve(n, arr):
	if n < 3:
		return arr[0] + 1 if n < 2 else max(arr, default=0)
	(a1, a2) = arr[:2]
	gcdall = gcd(a1, a2)
	candidates = {}
	if a2 != gcdall:
		candidates[a1] = a2
	if a1 != gcdall:
		candidates[a2] = a1
	for i in range(2, n):
		ai = arr[i]
		r = ai % gcdall
		for ak in candidates:
			candidates[ak] = gcd(candidates[ak], ai)
		if r != 0:
			if ai not in candidates:
				candidates[ai] = gcdall
			gcdall = gcd(gcdall, r)
	result = [gcd_k for (ak, gcd_k) in candidates.items() if gcd_k > gcdall]
	return result[0]

def read_case(ifile=sys.stdin):
	n = int(ifile.readline().strip())
	arr = [int(s) for s in ifile.readline().split()]
	return (n, arr)

def file_case(fn):
	with open(fn, 'r') as ifile:
		return read_case(ifile)

def string_case(case_str):
	return read_case(io.StringIO(case_str))
(n, arr) = read_case()
result = solve(n, arr)
print(result)


import math
import os
import random
import re
import sys
n = int(input())
a = list(map(int, input().rstrip().split()))
if n == 1:
	print(a[0] + 1)
else:
	pre = [0]
	suf = [0]
	p = 0
	s = 0
	dup = a.copy()
	dup.reverse()
	for i in range(len(a)):
		pre.append(math.gcd(pre[p], a[i]))
		p += 1
	for i in range(len(dup)):
		suf.append(math.gcd(suf[s], dup[i]))
		s += 1
	suf.reverse()
	for i in range(len(a)):
		g = math.gcd(pre[i], suf[i + 1])
		if a[i] % g != 0:
			print(g)
			break


import math
import os
import random
import re
import sys
from math import gcd
n = int(input())
A = list(map(int, input().rstrip().split()))
if n == 1:
	print(A[0] + 1)
else:
	gauche = [0] * n
	droite = [0] * n
	g = 0
	for i in range(n):
		g = gauche[i] = gcd(g, A[i])
	g = 0
	for i in range(n - 1, -1, -1):
		g = droite[i] = gcd(g, A[i])
	for i in range(n):
		if i == 0:
			g = droite[i + 1]
		elif i == n - 1:
			g = gauche[i - 1]
		else:
			g = gcd(gauche[i - 1], droite[i + 1])
		if A[i] % g != 0:
			print(g)
			break


import math
import os
import random
import re
import sys
n = int(input())
a = list(map(int, input().rstrip().split()))
if n == 1:
	print(a[0] + 1)
	exit()
dp = [0] * n
dp[0] = a[0]
for i in range(1, n):
	dp[i] = dp[i - 1]
	b = a[i]
	while b:
		tmp = b
		b = dp[i] % b
		dp[i] = tmp
bp = [0] * n
bp[-1] = a[-1]
for i in range(n - 2, -1, -1):
	bp[i] = bp[i + 1]
	b = a[i]
	while b:
		tmp = b
		b = bp[i] % b
		bp[i] = tmp
for i in range(1, n - 1):
	(b, c) = (dp[i - 1], bp[i + 1])
	while c:
		tmp = c
		c = b % c
		b = tmp
	if a[i] % b:
		print(b)
		exit()
if a[0] % bp[1]:
	print(bp[1])
	exit()
if a[-1] % dp[-2]:
	print(dp[-2])
	exit()


import math
import os
import random
import re
import sys
n = int(input())
a = list(map(int, input().rstrip().split()))
if n == 1:
	print(a[0] + 1)
else:
	pre = [0]
	suf = [0]
	p = 0
	s = 0
	dup = a.copy()
	dup.reverse()
	for i in range(len(a)):
		pre.append(math.gcd(pre[p], a[i]))
		p += 1
	for i in range(len(dup)):
		suf.append(math.gcd(suf[s], dup[i]))
		s += 1
	suf.reverse()
	for i in range(len(a)):
		g = math.gcd(pre[i], suf[i + 1])
		if a[i] % g != 0:
			print(g)
			break


from math import gcd
n = int(input())
a = list(map(int, input().split()))
if n == 1:
	print(a[0] + 1)
	exit(0)
gcd_left = [0] * (n + 2)
gcd_right = [0] * (n + 2)
for i in range(n):
	gcd_left[i + 1] = gcd(gcd_left[i], a[i])
for i in range(n - 1, -1, -1):
	gcd_right[i + 1] = gcd(gcd_right[i + 2], a[i])
ans = 1
for i in range(n):
	tmp = gcd(gcd_left[i], gcd_right[i + 2])
	if gcd(tmp, a[i]) != tmp:
		ans = max(ans, tmp)
print(ans)


import math
n = int(input())
a = list(map(int, input().rstrip().split()))
if n == 1:
	print(a[0] + 1)
else:
	pre = [0]
	suf = [0]
	p = 0
	s = 0
	dup = a.copy()
	dup.reverse()
	for i in range(len(a)):
		pre.append(math.gcd(pre[p], a[i]))
		p += 1
	for i in range(len(dup)):
		suf.append(math.gcd(suf[s], dup[i]))
		s += 1
	suf.reverse()
	for i in range(len(a)):
		g = math.gcd(pre[i], suf[i + 1])
		if a[i] % g != 0:
			print(g)
			break


import sys
import math
p = [0] * 10000000
s = [0] * 10000000
a = []
n = int(input())
if n == 1:
	print(int(input()) + 1)
	sys.exit()
a = list(map(int, input().split(' ')))
for i in range(n):
	p[i + 1] = math.gcd(a[i], p[i])
for j in range(n, 0, -1):
	s[j] = math.gcd(s[j + 1], a[j - 1])
for i in range(1, n + 1):
	cur = math.gcd(p[i - 1], s[i + 1])
	if a[i - 1] % cur != 0:
		print(cur)
		sys.exit()


import sys
import math
p = [0] * 10000000
s = [0] * 10000000
a = []
n = int(input())
if n == 1:
	print(int(input()) + 1)
	sys.exit()
a = list(map(int, input().split(' ')))
for i in range(n):
	p[i + 1] = math.gcd(a[i], p[i])
for j in range(n, 0, -1):
	s[j] = math.gcd(s[j + 1], a[j - 1])
for i in range(1, n + 1):
	cur = math.gcd(p[i - 1], s[i + 1])
	if a[i - 1] % cur != 0:
		print(cur)
		sys.exit()


import sys
import math
p = [0] * 10000000
s = [0] * 10000000
a = []
n = int(input())
if n == 1:
	print(int(input()) + 1)
	sys.exit()
a = list(map(int, input().split(' ')))
for i in range(n):
	p[i + 1] = math.gcd(a[i], p[i])
for j in range(n, 0, -1):
	s[j] = math.gcd(s[j + 1], a[j - 1])
for i in range(1, n + 1):
	cur = math.gcd(p[i - 1], s[i + 1])
	if a[i - 1] % cur != 0:
		print(cur)
		sys.exit()


import math
n = int(input())
a = list(map(int, input().rstrip().split()))
pre = [0] * n
suf = [0] * n
pre[0] = a[0]
suf[n - 1] = a[n - 1]
for i in range(1, n):
	pre[i] = math.gcd(a[i], pre[i - 1])
	suf[n - 1 - i] = math.gcd(a[n - 1 - i], suf[n - i])
solution = -1
if n == 1:
	solution = a[0] + 1
elif a[0] % suf[1] != 0:
	solution = suf[1]
elif a[n - 1] % pre[n - 2] != 0:
	solution = pre[n - 2]
else:
	for i in range(2, n - 1):
		d = math.gcd(pre[i - 1], suf[i + 1])
		if a[i] % d != 0:
			solution = d
			break
print(solution)


import math as m

def the_chosen_one(a, n):
	if n == 1:
		return a[0] + 1
	minim = min(a)
	a.remove(minim)
	gcd_ = 0
	for i in range(n - 1):
		gcd_ = m.gcd(gcd_, a[i])
	if gcd_ > minim:
		return gcd_
	a.append(minim)
	min_gcd_ = a[0]
	gcd_ = 0
	for i in range(n):
		gcd_ = m.gcd(gcd_, a[i])
		if gcd_ <= min_gcd_:
			min_gcd_ = gcd_
	gcd_ = 0
	for i in range(n):
		gcd_ = gcd_ = m.gcd(gcd_, a[i])
		if gcd_ == min_gcd_:
			a.remove(a[i])
			break
	gcd_ = 0
	for i in range(n - 1):
		gcd_ = m.gcd(gcd_, a[i])
	return gcd_
n = int(input())
a = list(map(int, input().rstrip().split()))
res = the_chosen_one(a, n)
print(res)


import math
import os
import random
import re
import sys
n = int(input())
a = list(map(int, input().rstrip().split()))
a.sort()
l = len(a)
prefix = [a[0]]
suffix = [a[l - 1]]
if n == 1:
	print(a[0] + 1)
else:
	for i in range(1, n):
		suffix.append(math.gcd(suffix[i - 1], a[l - 1 - i]))
		prefix.append(math.gcd(a[i], prefix[i - 1]))
	suffix.reverse()
	for j in range(0, n):
		if j == 0:
			k = math.gcd(0, suffix[j + 1])
		elif j == n - 1:
			k = math.gcd(prefix[j - 1], 0)
		else:
			k = math.gcd(prefix[j - 1], suffix[j + 1])
		if a[j] % k != 0:
			print(k)
			break


import sys
import math
p = [0] * 10000000
s = [0] * 10000000
a = []
n = int(input())
if n == 1:
	print(int(input()) + 1)
	sys.exit()
a = list(map(int, input().split(' ')))
for i in range(n):
	p[i + 1] = math.gcd(a[i], p[i])
for j in range(n, 0, -1):
	s[j] = math.gcd(s[j + 1], a[j - 1])
for i in range(1, n + 1):
	cur = math.gcd(p[i - 1], s[i + 1])
	if a[i - 1] % cur != 0:
		print(cur)
		sys.exit()


import sys
import math
p = [0] * 10000000
s = [0] * 10000000
a = []
n = int(input())
if n == 1:
	print(int(input()) + 1)
	sys.exit()
a = list(map(int, input().split(' ')))
for i in range(n):
	p[i + 1] = math.gcd(a[i], p[i])
for j in range(n, 0, -1):
	s[j] = math.gcd(s[j + 1], a[j - 1])
for i in range(1, n + 1):
	cur = math.gcd(p[i - 1], s[i + 1])
	if a[i - 1] % cur != 0:
		print(cur)
		sys.exit()


import sys
import math
p = [0] * 10000000
s = [0] * 10000000
a = []
n = int(input())
if n == 1:
	print(int(input()) + 1)
	sys.exit()
a = list(map(int, input().split(' ')))
for i in range(n):
	p[i + 1] = math.gcd(a[i], p[i])
for j in range(n, 0, -1):
	s[j] = math.gcd(s[j + 1], a[j - 1])
for i in range(1, n + 1):
	cur = math.gcd(p[i - 1], s[i + 1])
	if a[i - 1] % cur != 0:
		print(cur)
		sys.exit()


import sys
import math
p = [0] * 10000000
s = [0] * 10000000
a = []
n = int(input())
if n == 1:
	print(int(input()) + 1)
	sys.exit()
a = list(map(int, input().split(' ')))
for i in range(n):
	p[i + 1] = math.gcd(a[i], p[i])
for j in range(n, 0, -1):
	s[j] = math.gcd(s[j + 1], a[j - 1])
for i in range(1, n + 1):
	cur = math.gcd(p[i - 1], s[i + 1])
	if a[i - 1] % cur != 0:
		print(cur)
		sys.exit()