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

n,m = map(int,input().split())
cards = list(map(int,input().split()))
cards.sort()
actions = []
#print()
#print(cards)
for i in range(m):
    l,r  = map(int,input().split())
    actions.append([r,l])
actions.sort(reverse=True)
for i in range(m):
    minnum = min(cards)
    if actions[i][0] <= minnum:
        continue
    else:
        for j in range(actions[i][1]):
            #print(cards[j])
            if cards[j] <= actions[i][0]:
                cards[j] = actions[i][0]
            else:
                continue
    cards.sort()
    #print(cards)
print(sum(cards))

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

minA = A[0]
Query = []
for _ in range(m):
    b,c = map(int,input().split())
    if c > minA:
        Query.append([b,c])
Query = sorted(Query, key=lambda x:(x[1], x[0]), reverse=True)

ans = 0
index = 0
for b,c in Query:
    if index >= n:
        break
    #print("----")
    cnt = 0
    Flag = True
    while Flag:
        #print(A,b,c,index)
        if A[index] < c:
            A[index] = c
            cnt += 1
            index += 1
            if (cnt >= b) or (index >= n):
                Flag = False
        else:
            Flag = False
    '''
    #A.sort()
    if A[0] >= c:
        break
    else:
        index = min(bisect.bisect_left(A,c),b)
        if index > len(A):
            ans += c * len(A)
            break
        else:
            ans += c * index
            A = A[index:]
    print(A)
    '''
print(sum(A))
### BUGGY CODE ###

S = input()
nQ = int(input())

Ques = []
for i in range(nQ):
  Ques.append(input())
  
for iQ in Ques:
  iQ = iQ.split()
  if int(iQ[0]) == 1:
    S = S[::-1]
  else:
    if int(iQ[1]) == 1:
      S = iQ[2] + S
    elif int(iQ[1]) == 2:
      S = S + iQ[2]
print(S)


### FIXED CODE ###

S = input()
nQ = int(input())

Ques = []
nReverse = 0
nAddFront= 0
nAddBack = 0
for i in range(nQ):
  line = input().split()
  if int(line[0]) == 1:
    nReverse += 1
    Ques.append([int(line[0])])
  else:
    if int(line[1]) == 1:
      if nReverse % 2 == 0:
        nAddFront += 1
      else:
        nAddBack  += 1
    else:
      if nReverse % 2 == 0:
        nAddBack += 1
      else:
        nAddFront  += 1      
    Ques.append([int(line[0]),int(line[1]),line[2]])

#print(nAddFront,nAddBack)
SS = [-1] * (nAddFront + len(S) + nAddBack)
for i in range(len(S)):
   SS[nAddFront + i] = S[i]

left = nAddFront -1
right= nAddFront + len(S)

nReverseLoc = 0
for iQ in Ques:
   if iQ[0] == 1:
      nReverseLoc += 1
   if iQ[0] == 2:
    if int(iQ[1]) == 1:
      if nReverseLoc % 2 == 0:
        #nAddFront += 1
        SS[left] = iQ[2]
        left -= 1
      else:
        SS[right] = iQ[2]
        right += 1
    else:
      if nReverseLoc % 2 == 0:
        SS[right] = iQ[2]
        right += 1
      else:
        SS[left] = iQ[2]
        left  -= 1 

S = "".join(SS)
if nReverse % 2 == 1:
  S = S[::-1]
  
print(S)
### BUGGY CODE ###

import collections

n = int(input())
s = [list(input()) for _ in range(n)]

c = []
for i in s:
    c.append(collections.Counter(i))

ans = 0
for i in range(n):
    for j in range(i+1, n):
        if c[i] == c[j]:
            ans += 1
            
print(ans)

### FIXED CODE ###

import collections

n = int(input())

a = [str(sorted(input())) for _ in range(n)]
a.sort()
s = set(a)

c = collections.Counter(a)

ans = 0
for i in c.values():
        ans += (i-1) * i // 2

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

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 10**9+7

    dp = [[0]*(k+2) for i in range(n+1)]
    # dp[i][j]: i人目まで配ったときに残っているアメの個数がj個となる場合の数
    from itertools import accumulate
    dp[0][k] = 1
    for i in range(n):
        x = [0]*(k+2)
        for j in range(k+1):
            x[max(0, j-A[i])] += dp[i][j]%mod
            x[j+1] -= dp[i][j]%mod
        cum = list(accumulate(x))
        dp[i+1] = cum

    print(dp[n][0]%mod)

if __name__ == '__main__':
    main()

### FIXED CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = 10**9+7

dp = [[0]*(k+2) for i in range(n+1)]
# dp[i][j]: i人目まで配ったときに残っているアメの個数がj個となる場合の数
from itertools import accumulate
dp[0][k] = 1
for i in range(n):
    x = [0]*(k+2)
    for j in range(k+1):
        x[max(0, j-A[i])] += dp[i][j]%mod
        x[j+1] -= dp[i][j]%mod
    cum = list(accumulate(x))
    dp[i+1] = cum

print(dp[n][0]%mod)
### BUGGY CODE ###

# def lunlunChecker(N):
#   num = list(map(int,[l for l in str(N)]))
#    flag = True
#   for n in range(len(num)-1):
#       if abs(num[n]-num[n+1]) > 1:
#           flag = False
#           break
#   return flag
    
K = int(input())
cnt = 10
i = 10
lunlun_nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
if cnt > K:
    output = lunlun_nums.index(K) + 1
else :
    while cnt < K:
        i += 1
        if i//10 in lunlun_nums:
            num = list(map(int,[l for l in str(i)]))
            if abs(num[-2] - num[-1]) <= 1:
                lunlun_nums.append(i)
                cnt += 1
    output = i
print(output)


### FIXED CODE ###

from collections import deque

q = deque(range(1,10))
K = int(input())

for i in range(K):
    x = q.popleft()
    r =  x % 10
    if r != 0:
        q.append((10 * x) + (r - 1))
    q.append((10 * x) + r)
    if r != 9:
        q.append((10 * x) + (r + 1))

print(x)
### BUGGY CODE ###

import copy

n = int(input())
a = [int(input()) for _ in range(n)]
for i in range(n):
    a_copy = copy.deepcopy(a)
    a_copy.pop(i)
    print(max(a_copy))

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
a_sort = sorted(a, reverse=True)
for i in range(n):
    if a[i] == a_sort[0]:
        print(a_sort[1])
    else:
        print(a_sort[0])
### BUGGY CODE ###

N = int(input())

a = [int(x) for x in input().split()]
num = len(a)
for i in range(N):
    a = [int(x) for x in a if i+1 != x]
    print(num-len(a))
    num -= (num-len(a))
    


### FIXED CODE ###

import collections

N = int(input())

c = collections.Counter([int(x) for x in input().split()])
for i in range(N):
    print(c[i+1])
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    ans = deque([0] * N)
    con = deque([[] for _ in range(N)])

    for _ in range(N - 1):
        p, c = map(int, input().split())
        con[p-1].append(c-1)
        con[c-1].append(p-1)

    for _ in range(Q):
        p, v = map(int, input().split())
        ans[p-1] += v

    stacks = deque()
    stacks.append((0, -1))

    while stacks:
        stack = stacks.pop()
        node, parent = stack[0], stack[1]

        children = con[node]
        if children:
            for child in children:
                if child == parent:
                    continue
                ans[child] += ans[node]
                stacks.append((child, node))

    print(*ans, sep=' ')


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque

N, Q = map(int, input().split())
edge = [[] for i in range(N)]
ops = []
ans = [0] * N

for _ in range(N - 1):
    a, b = map(int, input().split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
for _ in range(Q):
    ops.append(tuple(map(int, input().split())))

for op in ops:
    node = op[0] - 1
    pnt = op[1]
    ans[node] += pnt

stack = deque()
stack.append((0, -1))

while stack:
    st = stack.pop()
    node, parent = st[0], st[1]
    children = edge[node]
    for child in children:
        if child == parent:
            continue
        ans[child] += ans[node]
        stack.append((child, node))

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


import math
n = int(input())

sqn = int(math.sqrt(n))+1
count = 0
aset = [0]*(n+1)
for x in range(1,sqn):
    for y in range(x,sqn):
        for z in range(y,n):
            a = x**2+y**2+z**2+x*y+y*z+z*x
            if a <= n:
                if x == y and y ==z:
                    aset[a] +=1
                else:
                    aset[a] +=3

for i in range(1,n+1):
    print(aset[i])

### FIXED CODE ###


import math
n = int(input())

sqn = int(math.sqrt(n))+1
count = 0
aset = [0]*(n+1)
for x in range(1,sqn):
    for y in range(x,sqn):
        for z in range(y,sqn):
            a = x**2+y**2+z**2+x*y+y*z+z*x
            if a <= n:
                if x == y and y ==z:
                    aset[a] +=1
                else:
                    if x == y or y ==z:
                        aset[a] +=3
                    else:
                        aset[a] +=6

for i in range(1,n+1):
    print(aset[i])
### BUGGY CODE ###

import heapq as hq
n, m = map(int, input().split())
q = list(map(int,input().split()))
hq.heapify(q)
for i in range(m):
    b, c = map(int,input().split())
    for j in range(b):
        if q[0] > c:
            continue
        else:
            hq.heappop(q)
            hq.heappush(q,c)
print(sum(q))

### FIXED CODE ###

import bisect
n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))
ope = []
d = []
for i in range(m):
    ope.append(list(map(int,input().split())))
ope = sorted(ope,key = lambda x:-x[1])
i = 0
ok = True
for b,c in ope:
    for rep in range(b):
        if i >= n or arr[i] > c:
            ok = False
            break
        arr[i] = c
        i += 1
    if ok:
        continue
    else:
        break
print(sum(arr))
### BUGGY CODE ###

N = int(input())
number = list(map(int,input().split()))
if not 1 in number:
    print(-1)
else:
    for i in range(N):
        now = i+1
        if now in number:
            #number.index(now)が左から数えたときのnowのindex番号
            number[:number.index(now)+1]=[]
            if i == N-1:
                count=0

        else:
            count = N-i
            break
    print(count)

### FIXED CODE ###

N = int(input())
number = list(map(int,input().split()))
count = 0
if not 1 in number:
    print(-1)
else:
    nownumber = 1
    nowindex = 0
    for i in range(N):
        if number[i]  == nownumber:
            count += 1
            nownumber += 1
        else:
            pass
    print(N-count)
### BUGGY CODE ###

from itertools import combinations

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

idxs = [i for i in range(N)]

ans = 0
for c in combinations(idxs, 3):
    # i, j, k = sorted(c)
    i, j, k = c
    s0 = S[i]
    s1 = S[j]
    s2 = S[k]

    if j - i != k - j and s0 != s1 and s1 != s2 and s0 != s2:
        ans += 1

print(ans)


### FIXED CODE ###


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

ris = [i for i, s in enumerate(S) if s == "R"]
gis = [i for i, s in enumerate(S) if s == "G"]
bis = [i for i, s in enumerate(S) if s == "B"]

all = len(ris) * len(gis) * len(bis)

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

ans = all - cnt


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

N = int(input())
S = input()
count = 0
while True:
	if S.count('R') == 0:
			break
	if S[0] == 'R':
		S=S.lstrip('R')
	else:
		count += 1
		Rpos = S.rfind('R')
		S = S[1:Rpos]
print(count)


### FIXED CODE ###

N = int(input())
S = input()
part = 0
leftW = 0
rightR = S.count('R')
moves = [rightR]

for i in range(N):
	if S[i] == 'R':  # rightR:decrease
		rightR -= 1
	else:          # leftW:increase
		leftW += 1
	moves.append(max(leftW, rightR))
# print(moves)
ans = min(moves[i] for i in range(N+1))
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

S = input().strip()
Q = int(input())
for i in range(Q):
    q = input().split()
    if q[0] == '1':
        S = S[::-1]
    elif q[0] == '2':
        if q[1] == '1':
            S = '{}{}'.format(q[2], S)
        elif q[1] == '2':
            S = '{}{}'.format(S, q[2])

print(S)


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline

S = deque(input().strip())
Q = int(input())
flag = 0

for i in range(Q):
    q = input().split()
    if q[0] == '1':
        flag = 1 if not flag else 0
    elif q[0] == '2':
        if q[1] == '1':
            S.appendleft(q[2]) if not flag else S.append(q[2])
        elif q[1] == '2':
            S.append(q[2]) if not flag else S.appendleft(q[2])

print(''.join(S)) if not flag else print(''.join(reversed(S)))
### BUGGY CODE ###

import math
from functools import reduce
def gcd(*numbers):
	return reduce(math.gcd, numbers)
k=int(input())
ans=0
for i in range(k):
	for j in range(k):
		for p in range(k):
			ans+=gcd(i+1,j+1,p+1)
print(ans)

### FIXED CODE ###

import math
from functools import reduce
def gcd(*numbers):
	return reduce(math.gcd, numbers)
k=int(input())
ans=0
for i in range(k):
	for j in range(k):
		for p in range(k):
			ans+=gcd(i+1,j+1,p+1)
print(ans)
### BUGGY CODE ###

from collections import deque
n,m=map(int,input().split())
li=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    li[a-1].append(b)
    li[b-1].append(a)
ans=[]
a=[0]*n
d=deque([1])
while len(d)>0:
    x=d.popleft()
    if x not in ans:
        ans.append(x)
        for v in li[x-1]:
            if v not in ans:
                d.append(v)
                if a[v-1]==0:
                    a[v-1]=x
if len(ans)==n:
    print("Yes")
    for i in range(1,n):
        print(a[i])
else:
    print("No")



### FIXED CODE ###

from collections import deque
n,m=map(int,input().split())
li=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    li[a-1].append(b)
    li[b-1].append(a)
ans=[0]*n
a=[[]  for _ in range(n)]
d=deque([1])
while len(d)>0:
    x=d.popleft()
    if ans[x-1]==0:
        ans[x-1]+=1
        for v in li[x-1]:
            if ans[v-1]==0:
                d.append(v)
                a[v-1].append(x)
if sum(ans)==n:
    print("Yes")
    for i in range(1,n):
        print(a[i][0])
else:
    print("No")
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
for i in range(1,n+1):
    print(li.count(i))

### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
li.sort(reverse = True)
count = 0
for i in range(1,n+1):
    count = 0
    while True:
        if li:
            if li[-1]==i:
                count+=1
                li.pop()
            else:
                break
        else:
            break
    print(count)
### BUGGY CODE ###

from bisect import bisect_left

import sys
input = lambda : sys.stdin.readline().strip()

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

def check(m):
    cnt = 0
    for ai in a:
        if ai == 0:
            if m >= 0:
                cnt += n-1
        elif ai < 0:
            x = -(-m//ai)
            cnt += n - bisect_left(a, x)
            if ai>= x:
                cnt -= 1
        else:
            x = m//ai
            cnt += bisect_left(a, x+1)
            if ai <= x:
                cnt -= 1
        if cnt//2 >= k:
            return True
    return False

left = -10**20
right = 10**20
while right-left>1:
    mid = (right+left)//2
    if check(mid):
        right = mid
    else:
        left = mid

print(right)

### FIXED CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

plus = minus = zero = 0
ps = []
ms = []
for i in a:
    if i == 0:
        zero += 1
    elif i > 0:
        plus += 1
        ps.append(i)
    else:
        minus += 1
        ms.append(-i)

ps.sort()
ms.sort()

def check(m):
    if m == 0:
        return plus*minus + zero*(zero-1)//2 + zero*(plus+minus) >= k
    elif m > 0:
        tmp = plus*minus + zero*(zero-1)//2 + zero*(plus+minus)
        for l in [ps, ms]:
            X = len(l)
            cur = X-1
            for i in range(X):
                while cur >= 0 and l[i]*l[cur] > m:
                    cur -= 1
                if cur <= i:
                    break
                tmp += cur-i
        return tmp >= k
    else:
        tmp = 0
        cur = 0
        for i in reversed(range(plus)):
            while cur < minus and ms[cur]*ps[i] < -m:
                cur += 1
            tmp += minus-cur
        return tmp >= k

left = -10**20
right = 10**20

while right-left>1:
    mid = (right+left)//2
    if check(mid):
        right = mid
    else:
        left = mid

print(right)
### BUGGY CODE ###

match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

N, M = map(int, input().split())
As = list(input().split())

dp = [None] * (N+1)
dp[0] = ""

for i in range(N+1):
    if i == 11:
        pass
    for A in As:
        if i - match[int(A)] >= 0 and not dp[i - match[int(A)]] is None:
            if dp[i] is None:
                dp[i] = str(max(int(A + dp[i - match[int(A)]]), int(dp[i - match[int(A)]] + A)))
            else:
                dp[i] = str(max(int(dp[i]), int(dp[i - match[int(A)]] + A)))
                dp[i] = str(max(int(dp[i]), int(A + dp[i - match[int(A)]])))

print(dp[N])

### FIXED CODE ###

def max_for_str(a, b):
    if len(a) > len(b):
        return a
    elif len(a) < len(b):
        return b
    else:#This case is unlikely to happen.
        for c1, c2 in zip(a, b):
            if c1 > c2:
                return a
            elif c1 < c2:
                return b
        return a
            
match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

N, M = map(int, input().split())
As = list(input().split())

dp = [None] * (N+1)
dp[0] = ""

for i in range(N+1):
    for A in As:
        if i - match[int(A)] >= 0 and not dp[i - match[int(A)]] is None:
            if dp[i] is None:
                dp[i] = A + dp[i - match[int(A)]]
            else:
                dp[i] = max_for_str(dp[i] , A + dp[i - match[int(A)]])

print(dp[N])
### BUGGY CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [0] * n
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])

    for i in range(2, n):
        dp[i] = min(abs(h[i] - h[j]) + dp[j] for j in range(max(0, i - k), i))
    print(dp[n - 1])


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [0] * n
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])

    for i in range(2, n):
        dp[i] = min(abs(h[i] - h[j]) + dp[j] for j in range(max(0, i - k), i))
    print(dp[n - 1])


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

S = input()
Q = int(input())
 
for i in range(Q):
    Que = input().split()
 
    if Que[0] == '1':
        S = S[::-1]
 
    if Que[0] == '2':
        if Que[1] == '1':
            S = Que[2] + S
        
        if Que[1] == '2':
            S = S + Que[2]
 
print(S)

### FIXED CODE ###

S = input()
Q = int(input())

A=""
Z=""
AZFlag = 0
for i in range(Q):
    Que = input().split()

    if Que[0] == '1':
        if AZFlag == 0:
            AZFlag = 1
            continue

        if AZFlag == 1:
            AZFlag = 0
            continue

    if Que[0] == '2':
        if Que[1] == '1' and AZFlag == 0:
            A = Que[2]+A
            continue

        if Que[1] == '1' and AZFlag == 1:
            Z = Z+Que[2]
            continue
        
        if Que[1] == '2' and AZFlag == 0:
            Z = Z+Que[2]
            continue

        if Que[1] == '2' and AZFlag == 1:
            A = Que[2]+A
            continue


if AZFlag == 0:
    print(A+S+Z)
if AZFlag == 1:
    print(Z[::-1]+S[::-1]+A[::-1])
### BUGGY CODE ###

import heapq
def dijkstra(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_a[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_a[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

def dijkstra1(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_b[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in graph_b[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n, m, s, t = map(int, input().split())
# graph作成
graph_a = {i: [] for i in range(1, n + 1)}
graph_b = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v, a, b = map(int, input().split())
    graph_a[u].append([a, v])
    graph_a[v].append([a, u])
    graph_b[u].append([b, v])
    graph_b[v].append([b, u])

yen = dijkstra(s)
snu = dijkstra1(t)

cost = [0] * n
for i in range(n):
    cost[i] = [yen[i + 1] + snu[i + 1],i]

heapq.heapify(cost)
c = -1
for i in range(n):
    if c < i:
        while cost:
            nn, t = heapq.heappop(cost)
            if t >= i:
                c = t
                break
    print(10 ** 15 - nn)


### FIXED CODE ###

import heapq
INF = 10**18
def dijkstra(s, edge, n):
    d = [INF] * n
    used = [True] * n #True: not used
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d
 
n, m, s, t = map(int, input().split())
s -= 1
t -= 1
graph_a = [[] for _ in range(n)]
graph_b = [[] for _ in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    u, v = u-1, v-1
    graph_a[u].append((a, v))
    graph_a[v].append((a, u))
    graph_b[u].append((b, v))
    graph_b[v].append((b, u))
 
yen = dijkstra(s, graph_a, n)
snu = dijkstra(t, graph_b, n)

cost = [0] * n
for i in range(n):
    cost[i] = (yen[i] + snu[i],i)

heapq.heapify(cost)
c = -1
aaa = 10 ** 15
for i in range(n):
    if c < i:
        while cost:
            nn, t = heapq.heappop(cost)
            if t >= i:
                c = t
                break
    print(aaa - nn)
### BUGGY CODE ###

n,m=map(int,input().split())
l1=[]
l2=[]
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    l1.append(b)
  if b==n:
    l2.append(a)
b=False
for i in range(2,n):
  if i in l1 and i in l2:
    b=True
if b:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")


### FIXED CODE ###

n,m=map(int,input().split())
bs=[False for i in range(n)]
bt=[False for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  if a==1 and (b!=n):
    bs[b-1]=True
  elif a!=1 and b==n:
    bt[a-1]=True
bool1=False
for i in range(1,n-1):
  if bs[i] and bt[i]:
    bool1=True
if bool1:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

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

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

L_gcd = [A[0]]
R_gcd = [A[-1]]

for i in range(1,N):
    L_gcd.append(gcd(L_gcd[i-1],A[i]))
    R_gcd.insert(0,gcd(A[N-i-1],R_gcd[0]))

ans = max(L_gcd[-2],R_gcd[1])

for i in range(N-2):
    if max(L_gcd[i],R_gcd[i+2])<=ans:
        break
    if gcd(L_gcd[i],R_gcd[i+2])>ans:
        ans = gcd(L_gcd[i],R_gcd[i+2])
print(ans)

### FIXED CODE ###

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

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

L_gcd = [0]*(N+1)
R_gcd = [0]*(N+1)

for i in range(N):
    L_gcd[i+1] = gcd(L_gcd[i],A[i])
    R_gcd[N-i-1] = gcd(R_gcd[N-i],A[N-i-1])

ans = 0
for i in range(N):
    if gcd(L_gcd[i],R_gcd[i+1])>ans:
        ans = gcd(L_gcd[i],R_gcd[i+1])
    
print(ans)