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

Difficulty: interview

Starter code:

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 : 
                #print(how_many)
                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


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)
        if i == 1 : u[i] = 1
        elif (i//divi[i][1]) % divi[i][1] == 0 : u[i] = 0
        else : u[i] = -u[i//divi[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 : 
                #print(how_many)
                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