Given an array $a$, consisting of $n$ integers, find:

$$\max\limits_{1 \le i < j \le n} LCM(a_i,a_j),$$

where $LCM(x, y)$ is the smallest positive integer that is divisible by both $x$ and $y$. For example, $LCM(6, 8) = 24$, $LCM(4, 12) = 12$, $LCM(2, 3) = 6$.


-----Input-----

The first line contains an integer $n$ ($2 \le n \le 10^5$) — the number of elements in the array $a$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$) — the elements of the array $a$.


-----Output-----

Print one integer, the maximum value of the least common multiple of two elements in the array $a$.


-----Examples-----
Input
3
13 35 77

Output
1001
Input
6
1 2 4 8 16 32

Output
32

Source: codeforces | Difficulty: MEDIUM


Solutions:
import math
N = 10 ** 5 + 10
u = [-1] * N
divi = [[] for i in range(N)]
pd = [[] for i in range(N)]
mark = [0] * N

def precalc():
	for i in range(1, N):
		for j in range(i, N, i):
			divi[j].append(i)
	for i in range(2, N):
		if mark[i] == 1:
			continue
		for j in range(i, N, i):
			pd[j].append(i)
			mark[j] = 1
	for i in range(1, N):
		for prm in pd[i]:
			time = 0
			_i = i
			while _i % prm == 0:
				time += 1
				_i /= prm
			if time > 1:
				u[i] = 0
				continue
		if u[i] == -1:
			if len(pd[i]) & 1:
				u[i] = -1
			else:
				u[i] = 1
has = [False] * N
cnt = [0] * N

def has_coprime(n):
	ret = 0
	for d in divi[n]:
		ret += u[d] * cnt[d]
	return ret

def update(n, val):
	for d in divi[n]:
		cnt[d] += val

def solve(n):
	li = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		if has[li[i]]:
			ans = max(ans, li[i])
		has[li[i]] = True
	for g in range(1, N):
		st = []
		for num in reversed(list(range(1, N // g + 1))):
			if num * g > N - 1 or not has[num * g]:
				continue
			how_many = has_coprime(num)
			while how_many > 0:
				now = st.pop()
				if math.gcd(now, num) == 1:
					ans = max(ans, num * now * g)
					how_many -= 1
				update(now, -1)
			st.append(num)
			update(num, 1)
		while st:
			update(st.pop(), -1)
	print(ans)
precalc()
while True:
	try:
		n = int(input())
		solve(n)
	except EOFError:
		break