Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import heapq
import sys

readline = sys.stdin.buffer.readline


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    rA = list(map(lambda x: -1 * x, A[::-1]))

    MM = A[:N]
    mm = rA[:N]
    heapq.heapify(MM)
    heapq.heapify(mm)
    M = [sum(MM)]
    m = [sum(mm)]

    for i in range(N, 2*N):
        heapq.heappushpop(MM, A[i])
        heapq.heappushpop(mm, rA[i])
        M.append(sum(MM))
        m.append(sum(mm))

    Dm = -10**14
    for i, j in zip(M, m[::-1]):
        if i + j > Dm:
            Dm = i + j

    print(Dm)


main()


### FIXED CODE ###

import heapq
import sys

readline = sys.stdin.buffer.readline


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    rA = list(map(lambda x: -1 * x, A[::-1]))

    MM = A[:N]
    mm = rA[:N]
    heapq.heapify(MM)
    heapq.heapify(mm)
    M = [sum(MM)]
    m = [sum(mm)]

    for i in range(N, 2*N):
        pM = heapq.heappushpop(MM, A[i])
        pm = heapq.heappushpop(mm, rA[i])
        M.append(M[-1] - pM + A[i])
        m.append(m[-1] - pm + rA[i])

    Dm = -10**14
    for i, j in zip(M, m[::-1]):
        if i + j > Dm:
            Dm = i + j

    print(Dm)


main()
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
for i in range(n):
    a_tmp = a[:]
    a_tmp.pop(i)
    print(max(a_tmp))

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
maxvalue = max(a)
maxindex = a.index(max(a))
for i in range(n):
    if i != maxindex:
        print(maxvalue)
    else:
        a_tmp = a[:]
        a_tmp.pop(maxindex) 
        print(max(a_tmp))
### BUGGY CODE ###


import math

k = int(input())

cache = {}
ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            key = tuple(sorted([a,b,c]))
            x = cache.get(key, math.gcd(math.gcd(a, b), c))
            ans = ans + x
            cache[key] =  x
print(ans)

### FIXED CODE ###

import itertools
import math

k = int(input())
x = 0
for v in itertools.combinations_with_replacement(list(range(1, k+1)), 3):
    a, b, c = v
    x = x + math.gcd(math.gcd(a,b), c)

y = 0
for v in itertools.combinations(list(range(1, k+1)), 3):
    a, b, c = v
    y = y + math.gcd(math.gcd(a,b), c)

z = k * (1 + k) / 2
print( int(3 * x  + y * 3  -  2 * z))
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))
ans=1
for x in a:
    ans=ans*x
if ans>pow(10,18):
    ans=-1
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
if 0 in a:
    print(0)
else:
    ans=1
    for x in a:
        ans=ans*x
        if ans>pow(10,18):
            ans=-1
            break
    print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())
cnt = 0

for x in range(k + 1):
    for y in range(k + 1):
        for z in range(k + 1):
            if x + y + z == s:
                cnt += 1
print(cnt)


### FIXED CODE ###

k, s = map(int, input().split())
cnt = 0

for i in range(k + 1):
    t = s - i
    if t >= 0:
        cnt += max(0, (t + 1) - 2 * (max(0, t - k)))
print(cnt)
### BUGGY CODE ###

A, B, C, D = map(int,input().split())

ans = 0
j = A
while j <= B:
    count = 0
    if j%C:
        count += 1
    if j%D:
        count += 1

    if count == 2:
        ans += 1

    j+= 1

print(ans)

### FIXED CODE ###

#考え方
#（BについてCでもDでも割り切れない数の個数）-（についてCでもDでも割り切れない数の個数）
#↑それぞれは、B -（B//C + B//D - B//lcm(C,D)) 、　A -（A//C + A//D - A//lcm(C,D))で出せる

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

    else:
        return gcd(y,x%y)



A, B, C, D = map(int,input().split())

if C < D:
    t = C
    C = D
    D = t

max_ky = gcd(C,D)

#最小公倍数
lcm_c = C//max_ky
lcm_d = D//max_ky
lcm = max_ky * lcm_c * lcm_d

count_b = B - (B//C + B//D - B//lcm)
count_a = A - (A//C + A//D - A//lcm)
if(A%C != 0 and A%D != 0):
    count_a -= 1
ans = count_b - count_a

print(ans)






#りゅうせいの解答1 実行時間超過
#A, B, C, D = map(int,input().split())
# ans = 0
# j = A
# while j <= B:
#     count = 0
#     if j%C:
#         count += 1
#     if j%D:
#         count += 1
#
#     if count == 2:
#         ans += 1
#
#     j+= 1
#
# print(ans)
### BUGGY CODE ###

from collections import defaultdict


def solve(H, M, W, bombs):
    count_h = defaultdict(int)
    count_w = defaultdict(int)
    for b in bombs:
        h = str(b[0])
        count_h[h] += 1
        w = str(b[1])
        count_w[w] += 1
    max_h = max(count_h.values())
    max_w = max(count_w.values())
    points_h = [int(k) for k in count_h.keys() if count_h[k] == max_h]
    points_w = [int(k) for k in count_w.keys() if count_w[k] == max_w]
    ans = max_h + max_w
    if _find_cross_bomb(points_h, points_w, bombs):
        ans -= 1
    print(ans)


def _find_cross_bomb(points_h, points_w, bombs):
    c = 0
    for b in bombs:
        if (b[0]) in points_h:
            if (b[1]) in points_w:
                c += 1
    return c == len(points_h) * len(points_w)


if __name__ == "__main__":
    H, W, M = map(int, input().split())
    bombs = [list(map(lambda x: int(x) - 1, input().split())) for i in range(M)]
    solve(H, M, W, bombs)


### FIXED CODE ###

import sys


def solve():
    readline = sys.stdin.readline
    H, W, M = map(int, readline().split())
    h = [0] * H
    w = [0] * W
    b = set()
    for _ in range(M):
        y, x = map(int, readline().split())
        x -= 1
        y -= 1
        h[y] += 1
        w[x] += 1
        b.add(y * W + x)
    h = sorted(zip(h, range(H)), reverse=True)
    ans = 0
    for i in range(W):
        x = w[i]
        for y, j in h:
            if x + y > ans:
                if j * W + i in b:
                    ans = x + y - 1
                else:
                    ans = x + y
                    break
            else:
                break
    print(ans)


if __name__ == '__main__':
    solve()
### BUGGY CODE ###

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

use_1 = 0
use_2 = 0
for i in set(a):
    can = a.count(i) // 2
    if can == 1:
        if use_1 < i:
            use_2 = use_1
            use_1 = i
    elif can > 1:
         use_1 = max(use_1, i)
         use_2 = max(use_2, i)

print(use_1*use_2)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
a = a[::-1]
tobasu = 0
one = 0
two = 0
for i in range(len(a) - 1):
    if tobasu == 1:
        tobasu = 0
        continue
    if a[i] == a[i + 1] and one == 0:
        tobasu = 1
        one = a[i]
    elif a[i] == a[i + 1] and one != 0 and two == 0:
        two = a[i]
        break
print(one * two)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N=int(input())
P=[list(map(int,input().split())) for i in range(N)]
ANS=[1<<60]*(N+1)
ANS[-1]=0

DP1=[20000]*N

S=0
for i in range(N):
    x,y,p=P[i]
    DP1[i]=min(abs(x),abs(y))
    S+=DP1[i]*p

ANS[0]=S

def dfs(DP,now,used):
    if used==N-1:
        return
    for next_town in range(now,N):
        x,y,p=P[next_town]

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][0]-x))
            S+=DP2[i]*P[i][2]

        #print(DP,now,used,next_town,DP2)
            
        ANS[used+1]=min(ANS[used+1],S)
        if S!=0:
            dfs(tuple(DP2),next_town+1,used+1)

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][1]-y))
            S+=DP2[i]*P[i][2]

        #print(DP,now,used,next_town,DP2)
            
        ANS[used+1]=min(ANS[used+1],S)
        if S!=0:
            dfs(tuple(DP2),next_town+1,used+1)

dfs(tuple(DP1),0,0)

for i in range(1,N):
    ANS[i]=min(ANS[i],ANS[i-1])

print(*ANS)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
P=[list(map(int,input().split())) for i in range(N)]
ANS=[1<<60]*(N+1)
ANS[-1]=0

DP1=[20000]*N

S=0
for i in range(N):
    x,y,p=P[i]
    DP1[i]=min(abs(x),abs(y))
    S+=DP1[i]*p

ANS[0]=S

def dfs(DP,now,used):
    if used==N-1:
        return
    for next_town in range(now,N):
        x,y,p=P[next_town]

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][0]-x))
            S+=DP2[i]*P[i][2]

        #print(DP,now,used,next_town,DP2)
            
        ANS[used+1]=min(ANS[used+1],S)
        if S!=0:
            dfs(DP2,next_town+1,used+1)

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][1]-y))
            S+=DP2[i]*P[i][2]

        #print(DP,now,used,next_town,DP2)
            
        ANS[used+1]=min(ANS[used+1],S)
        if S!=0:
            dfs(DP2,next_town+1,used+1)

dfs(DP1,0,0)

for i in range(1,N):
    ANS[i]=min(ANS[i],ANS[i-1])

print(*ANS)
### BUGGY CODE ###

def main():
  ans = 0
  n = int(input())
  a = tuple(map(int, input().split()))
  ov = 10**9+7
  from fractions import gcd
  def lcm(a):
      x = a[0]
      for i in range(1, n):
          x = (x * a[i]) // gcd(x, a[i])
      return x
  l = lcm(a)
  for i in a:
    ans += l//i%ov
  print(ans%ov)
if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  from functools import reduce
  from fractions import gcd
  ans = 0
  n = int(input())
  b = tuple(map(int, input().split()))
  ov = 10**9+7
  def lcm(x,y):
    return (x * y) // gcd(x, y)
  def lcm_list(a):
    return reduce(lcm, a, 1)
  l = lcm_list(b)
  for i in range(n):
    ans += l//b[i]
  print(ans%ov)
if __name__ == "__main__":
  main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

def main():
    S = input()
    N = len(S)

    # S = [int(s) if s!="?" else -1 for s in S ]
    dp = [[0] * 13 for _ in range(N+1)]

    s = S[0]
    if s == "?":
        for j in range(10):
            dp[0][j] += 1
    else:
        dp[0][int(s)%13] += 1
    for i in range(1,N):
        s = S[i]
        if s == "?":
            for j in range(0,13):
                for x in range(10):
                    k = (j*10+x)%13
                    dp[i][k] += dp[i-1][j]
        else:
            for j in range(0,13):
                k = (j*10+int(s))%13
                dp[i][k] += dp[i-1][j]


    print(dp[N-1][5] % (10**9+7))


if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def main():
    S = input()
    N = len(S)
    MOD = 10**9+7

    # S = [int(s) if s!="?" else -1 for s in S ]
    dp = [[0] * 13 for _ in range(N+1)]

    s = S[0]
    if s == "?":
        for j in range(10):
            dp[0][j] += 1
    else:
        dp[0][int(s)%13] += 1
    for i in range(1,N):
        s = S[i]
        if s == "?":
            for j in range(0,13):
                for x in range(10):
                    k = (j*10+x)%13
                    dp[i][k] += dp[i-1][j]
                    dp[i][k] %= MOD
        else:
            for j in range(0,13):
                k = (j*10+int(s))%13
                dp[i][k] += dp[i-1][j]
                dp[i][k] %= MOD


    print(dp[N-1][5])


if __name__ == "__main__":
  main()
### BUGGY CODE ###

H, W, K = map(int, input().split())
S = []
for _ in range(H):
    S.append([c for c in input()])

ans = float('inf')
for div in range(2 ** (H - 1)):
    g = 0
    ids = [0] * H
    for i in range(H):
        ids[i] = g
        if div >> i & 1:
            g += 1
    g += 1

    c = [[0 for _ in range(1005)] for _ in range(10)]
    for i in range(H):
        for j in range(W):
            c[ids[i]][j] += int(S[i][j])

    num = g - 1
    now = [0] * g
    def add(j):
        for i in range(g):
            now[i] += c[i][j]
            if now[i] > K:
                return False
        return True

    for j in range(W):
        if not add(j):
            num += 1
            now = [0] * g
            if not add(j):
                num = float('inf')
                break

    ans = min(ans, num)
print(ans)


### FIXED CODE ###

H, W, K = map(int, input().split())
S = []
for _ in range(H):
    S.append([c for c in input()])

ans = float('inf')
for div in range(2 ** (H - 1)):
    g = 0
    ids = [0] * H
    for i in range(H):
        ids[i] = g
        if div >> i & 1:
            g += 1
    g += 1

    c = [[0 for _ in range(1005)] for _ in range(10)]
    for i in range(H):
        for j in range(W):
            c[ids[i]][j] += int(S[i][j])

    num = g - 1
    now = [0] * g
    def add(j):
        for i in range(g):
            now[i] += c[i][j]
            if now[i] > K:
                return False
        return True

    for j in range(W):
        if not add(j):
            num += 1
            now = [0] * g
            if not add(j):
                num = float('inf')
                break

    ans = min(ans, num)
print(ans)
### BUGGY CODE ###

N = int(input())
An = [int(x) for x in input().split()]  

# ボールを全部使えるときの合計を求める
s = 0
for i in range(1,N+1):
    b = An.count(i)
    if b > 1:
        s += int(b*(b-1) / 2)

for k in range(N):
    print(s - (An.count(An[k])-1))

### FIXED CODE ###

import collections as c

# 入力
N = int(input())
An = [int(x) for x in input().split()]
 
# 各数字の個数を求める
Cn = c.Counter(An)
 
# 全部の組み合わせ
s = 0
for v in Cn.values():
    s += int(v*(v-1) / 2)

for i in range(0,N):
    print(s - (Cn[An[i]] - 1))
### BUGGY CODE ###

intMax = -100000000

inputData = int(input())
inputList = list()
count = 0
while count < inputData:
    inputList.append(int(input()))
    count = count + 1

inputDataMax = intMax
inputDataMin = inputList[0]
count2 = 1
while count2 < inputData:
    inputDataMax = max(inputDataMax,  inputList[count2] - inputDataMin)
    inputMin = min(inputDataMin, inputList[count2])

print(inputDataMax)


### FIXED CODE ###

intMax = -10000000000
inputData = int(input())
inputList = list()
for i in range(inputData):
    inputList.append(int(input()))

inputDataMax = intMax
inputDataMin = inputList[0]
for i in range(inputData - 1):
    inputDataMax = max(inputDataMax,  inputList[i + 1] - inputDataMin)
    inputDataMin = min(inputDataMin, inputList[i + 1])

print(inputDataMax)
### BUGGY CODE ###

n,p= map(int,input().split())
res=1
if n==1:
    res=p
else:
    for i in range(int(p**(1/n))+1,1,-1):
        if p%i**n==0:
            res=i
            break
print(res)

### FIXED CODE ###

n,p= map(int,input().split())
for i in range(round(p**(1/n)),0,-1):
    if p%(i**n)==0:
        print(i)
        exit()
### BUGGY CODE ###

n=int(input())
an=list(map(int,input().split()))
ans=1
for i in range(n):
    ans*=an[i]
if ans>10**18:
    print("-1")
    exit()
print(ans)

### FIXED CODE ###

n=int(input())
an=list(map(int,input().split()))
x=an.count(0)
if x>=1:
    print(0)
    exit()
ans=1
for i in range(n):
    ans*=an[i]
    if ans>10**18:
        print("-1")
        exit()
print(ans)
### BUGGY CODE ###

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]

dp = [10 ** 18] * (H + 1)

dp[0] = 0

for i in range(H + 1):
    for A, B in AB:
        if i + A >= H:
            dp[H] = min(dp[H], dp[i] + B)
        else:
            dp[i + A] = min(dp[i + A], dp[i] + B)

res = dp[H]

print(res)


### FIXED CODE ###

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]

dp = [10 ** 18] * (H + 1)

dp[0] = 0

for i in range(H + 1):
    for A, B in AB:
        if i + A >= H:
            dp[H] = min(dp[H], dp[i] + B)
        else:
            dp[i + A] = min(dp[i + A], dp[i] + B)

res = dp[H]

print(res)
### BUGGY CODE ###

import sys
import numpy as np
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()

#動的計画法 dp
dp =np.array([[0 for _ in range(n+1)] for _ in range(n+1)])

for i in range(n-1, -1, -1):
    for j in range(n-1, -1, -1):
        if i ==j:
            continue
        if S[i] != S[j]:
            dp[i][j] = 0
        elif S[i] == S[j]:
            dp[i][j] = 1 + dp[i+1][j+1]
            if dp[i][j] >=n/2:
                dp[i][j] = 0

print(np.max(dp))

### FIXED CODE ###

import sys
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()


dp = [[0 for i in range(n)] for j in range(n)]
#初期条件
for j in range(1, n):
    if S[0] == S[j]:
        dp[0][j] = 1

#print(dp)

for i in range(1, n-1):
    for j in range(i+1, n):
        if S[i] ==S[j]:
            dp[i][j] = min(dp[i-1][j-1] +1, j-i)

maxp = 0
for i in range(n-1):
    for j in range(i+1, n):
        if maxp < dp[i][j]:
            maxp = dp[i][j]
#print(dp)
print(maxp)
### BUGGY CODE ###

A,B = map(int, input().split())
ans = 0
for i in range(A,B+1):
    if i == A:
        ans = A
    else:
        ans ^= i
print(ans)

### FIXED CODE ###

A,B = map(int, input().split())


def f(n):
    if n%4 == 0:
        return n
    elif n%4 == 1:
        return 1
    elif n%4 == 2:
        return n ^ (n-1) ^ (n-2)
    elif n%4 == 3:
        return 0

print(f(A-1)^f(B))
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = sorted(Counter(list(map(int, input().split()))).items(), reverse=True)
if len(a) == 2 ** n:
  print('Yes')
  exit(0)
g = [0]*(n+1)
g[n] = 1
for _, x in a:
  if sum(g) < x:
    print('No')
    break
  t = [0]*(n+1)
  for i in range(n, -1, -1):
    if g[i] <= x:
      t[i-1] = t[i] + g[i]
      x -= g[i]
      g[i] = 0
    else:
      t[i-1] = t[i] + x
      g[i] -= x
      x = 0
  t[n] = 0
  g = [x+y for x,y in zip(g, t)]
else:
  print('Yes')


### FIXED CODE ###

from collections import Counter
n = int(input())
a = sorted(Counter(list(map(int, input().split()))).items(), reverse=True)
g = [0]*(n+1)
g[n] = 1
for _, x in a:
  if sum(g) < x:
    print('No')
    break
  t = [0]*(n+1)
  for i in range(n, -1, -1):
    if g[i] <= x:
      t[i-1] = t[i] + g[i]
      x -= g[i]
      g[i] = 0
    else:
      t[i-1] = t[i] + x
      g[i] -= x
      x = 0
  t[n] = 0
  g = [x+y for x,y in zip(g, t)]
else:
  print('Yes')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))
from bisect import bisect_left, insort
N = int(input())
A = inpl()

before = sorted(A[:N])
after = sorted(A[N:])
x = sum(before)
y = sum(after[:N])
score = x - y

for i in range(N):
    insort(before, A[N+i])
    del after[bisect_left(after, A[N+i])]
    score = max(score, sum(before[-N:]) - sum(after[:N]))

print(score)

### FIXED CODE ###

# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from heapq import heapify, heappop, heappush
from copy import deepcopy

N = int(input())
A = inpl()

before = deepcopy(A[:N])
heapify(before)
middle = A[N:-N]
after = [-a for a in A[-N:]]
heapify(after)

sb = sum(A[:N])
sa = -sum(A[-N:])

SB = [sb]
SA = [sa]

for m in middle:
    b = heappop(before)
    if b < m:
        heappush(before, m)
        sb += m - b
    else:
        heappush(before, b)
    SB.append(sb)    

for m in middle[::-1]:
    m = -m
    a = heappop(after)
    if a < m:
        heappush(after, m)
        sa += m - a
    else:
        heappush(after, a)
    SA.append(sa) 

    
print(max([b+a for b, a in zip(SB, SA[::-1])]))
### BUGGY CODE ###

s = input() #sys.stdin.readlineは最後が改行
n =len(s)

from collections import defaultdict
amari = defaultdict(lambda:0)
amari[0]=1
num=0
tmp=0

for i in range(n):
    num = tmp + int(s[-1-i])*(10**(i))
    tmp = num%2019
    amari[tmp]+=1

from math import factorial

ans = 0
for key,val in amari.items():
    if val>1:
        ans +=factorial(val) // factorial(2) // factorial(val - 2)

print(ans)


### FIXED CODE ###

s = input() #sys.stdin.readlineは最後が改行
n =len(s)

from collections import defaultdict
amari = defaultdict(lambda:0)
amari[0]=1
num=0
tmp=0
ans =0

for i in range(n):
    num = tmp + int(s[-1-i])*pow(10,i,2019)
    tmp = num%2019
    amari[tmp]+=1

    if amari[tmp]>1:
        val = amari[tmp]
        ans -= (val-1)*(val-2)//2
        ans += (val)*(val-1)//2

print(ans)
### BUGGY CODE ###

import sys
n = int(input())

print(0)
sys.stdout.flush()
s = input()

if s == "Vacant":
    exit()

low = 1
high = n
tmp = 0

while low+1 < high:
    mid = (low + high) //2
    
    print(mid)
    sys.stdout.flush()
    t = input()
    
    if mid % 2 == 0:
        if t[0] == s[0]:
            low = mid
        elif t[0] == "V":
            exit()
        else:
            high = mid
    else:
        if t[0] == s[0]:
            high = mid
        elif t[0] == "V":
            exit()
        else:
            low = mid
print(high)
exit()

### FIXED CODE ###

import sys
n = int(input())

print(0)
sys.stdout.flush()
s = input()

if s == "Vacant":
    exit()

low = 1
high = n-1
tmp = 0
cnt = 1

while low+1 < high:
    mid = (low + high) //2
    
    print(mid)
    sys.stdout.flush()
    t = input()
    cnt += 1
    
    if mid % 2 == 0:
        if t[0] == s[0]:
            low = mid
        elif t[0] == "V":
            exit()
        else:
            high = mid
    else:
        if t[0] == s[0]:
            high = mid
        elif t[0] == "V":
            exit()
        else:
            low = mid

print(high)
sys.stdout.flush()
s = input()
if s[0] == "V":
    exit()
else:
    print(low)
    sys.stdout.flush()
    s = input()
    exit()
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import fractions
from functools import reduce

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

def gcd(nums):
    return reduce(fractions.gcd,nums)

ans = 1
for i in range(N):
    a = copy.deepcopy(A)
    a.remove(A[i])
    ans = max(ans,gcd(a))

print(ans)


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import fractions
from functools import reduce



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

def gcd(nums):
    return reduce(fractions.gcd,nums)

ans = 1
A.sort()
gcd1 = gcd(A)
for i in range(N):
    A[i] //= gcd1

ans *= gcd1

gcd2 = A[0]
for i in range(1,N):
    gcd2 = fractions.gcd(gcd2,A[i])
    if gcd2 == 1:
        key = i
        break

a = copy.deepcopy(A)
a.remove(A[0])
if gcd(a)!=1:
    ans *= gcd(a)
    print(ans)
    exit()

a = copy.deepcopy(A)
a.remove(A[key])
if gcd(a)!=1:
    ans *= gcd(a)
    print(ans)
    exit()
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

cnt = 0
jk = {}
for j in range(1, N-1):
    jk[j] = []
    for k in range(j+1, N):
        if S[j] != S[k]:
            jk[j].append(k)

for i in range(N-2):
    for j in range(i+1, N-1):
        if S[i] == S[j]:
            continue
        ks = jk[j]
        for k in ks:
            if S[i] == S[k]:
                continue
            if j-i != k-j:
                cnt += 1

print(cnt)



### FIXED CODE ###

N = int(input())
S = "A" + input()
r, g, b = 0, 0, 0

for s in S[1:]:
    if s == "R":
        r += 1
    elif s == "G":
        g += 1
    else:
        b += 1

pat = r*g*b

for i in range(1, N-1):
    for j in range(i+1, N):
        k = 2*j - i
        if (j+1 <= k <= N) and S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            pat -= 1

print(pat)
### BUGGY CODE ###

N = int(input())
paper = []
paper.append(1000000001)

for i in range(N):
    # Aのi番目
    ai = int(input())
    for p in range(len(paper)):
        if paper[p] < ai:
            continue
        elif paper[p] == ai:
            paper.remove(ai)
            break
        else:
            paper.insert(p, ai)
            break

print(len(paper) -1)

### FIXED CODE ###

def main():
    N = int(input())

    paper = []
    for i in range(N):
        paper.append(int(input()))

    # TimSortっていうMergeSortの改良版らしい
    paper.sort()

    preNum = paper[0]
    sameNumCount = 1
    ans = 0
    for num in paper[1:]:
        if preNum == num:
            sameNumCount += 1
        else:
            ans += sameNumCount % 2
            preNum = num
            sameNumCount = 1
    # 一番最後の判定
    if paper[-1] == preNum:
        ans += sameNumCount % 2

    print(ans)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import defaultdict
mod = 2019
S = input()
N = len(S)

S = S[::-1]
A = []
for i in range(N):
    s = int(S[i])*pow(10,i)
    A.append(s%mod)
B = [0]
for i in range(N):
    s = B[i]+A[i]
    B.append(s%mod)

D = defaultdict(int)
for i in range(N+1):
    D[B[i]]+=1
ans = 0
for key in D.keys():
    m = D[key]
    ans += m*(m-1)//2
print(ans)

### FIXED CODE ###

S = input()

from collections import defaultdict
mod = 2019
N = len(S)
D = defaultdict(int)
S = S[::-1]
ans = 0
T = 0
D[0]+=1
for i in range(N):
    s = int(S[i])*pow(10,i,mod)
    T = (T+s)%mod
    ans += D[T]
    D[T]+=1
print(ans)