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

import sys
sys.setrecursionlimit(500)
N, W = map(int, input().split())
A = []
V = []
for i in range(N):
  a, v = map(int, input().split())
  A.append(a)
  V.append(v)

memo = {}
def dp(i, w):
  if (i, w) in memo:
    return memo[(i, w)]
  ret = None
  if i == N:
    ret = 0
  else:
    ret = dp(i+1, w)
    if A[i] <= w:
      ret2 = dp(i+1, w - A[i]) + V[i]
      ret = ret if ret > ret2 else ret2
  memo[(i, w)] = ret
  return ret

print(dp(0, W))

### FIXED CODE ###

N, W = map(int, input().split())
A = []
V = []
for i in range(N):
  a, v = map(int, input().split())
  A.append(a)
  V.append(v)

dp = [0] * (W+1)
for i in range(N)[::-1]:
  a = dp[:]
  for w in range(W+1):
    if A[i] <= w and a[w] < dp[w-A[i]] + V[i]:
      a[w] = dp[w-A[i]] + V[i]
  dp = a

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

s = input()
f = 0
for i in range(len(s)-1):
	if f == 0:
		l = s[i]
		if s.count(l) >= 2:
			t = s[i:]
			a = 0
			for j in range(t.count(l)-1):
				b = t[a+1:].index(l)
				u = t[:a+b+2]
				a += b
				if u.count(l) > len(u)/2:
					print(i+1, i+a+2)
					f = 1
					break
else:
	if f == 0:
		print("-1 -1")


### FIXED CODE ###

s = input()
for i in range(len(s)-2):
	if s[i] == s[i+1]:
		print(i+1, i+2)
		break
	elif s[i] == s[i+2]:
		print(i+1, i+3)
		break
else:
	if s[-2] == s[-1]:
		print(len(s)-1, len(s))
	else:
		print(-1, -1)
### BUGGY CODE ###

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

for vlen in range(N // 2, -1, -1):
    for l1 in range(N - vlen + 1):
        for l2 in range(l1 + vlen, N):
            if S[l1:l1 + vlen] == S[l2:l2 + vlen]:
                print(vlen)
                exit()
print(0)


### FIXED CODE ###

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

dp = [[None for j in range(N)] for i in range(N)]
vlen = 0
for i in range(N-1):
    for j in range(i + 1, N):
        if S[i] != S[j]:
            dp[i][j] = 0
        elif i - 1 >= 0 and j - 1 >= 0:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = 1
        if i + dp[i][j] <= j:
            vlen = max(vlen, dp[i][j])
print(vlen)
### BUGGY CODE ###

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

p = 10 ** 18

ans = 1
for a in A:
    ans *= a

if ans > p:
    ans = -1

print(ans)

### FIXED CODE ###

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

p = 10 ** 18

ans = 1

if 0 in A:
    ans = 0
else:
    for a in A:
        ans = ans * a
        if ans > p:
            ans = -1
            break

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

N = int(input())
s= input()

D = N
for i in range(N):
    temp = 0
    for j in range (N):
        if (i < j) and (s[j] == "E" ) or  (i > j) and (s[j] == "W" ) :
            temp += 1
    if temp < D:
        D = temp
print(D)

### FIXED CODE ###

from collections import Counter
N = int(input())
s= input()

D = Counter(s[1:])["E"]
nums = [D]
for i in range (1,N):
    temp = nums[-1]
    if s[i-1] == "W":
        temp += 1
    if s[i] == "E":
        temp -= 1
    nums.append(temp)

print(min(nums))
### BUGGY CODE ###

X, Y = map(int, input().split())

mod = 10**9+7
N = 670000
fac = [1]*(N+1)
rev = [1]*(N+1)
 
for i in range(1,N+1):
  fac[i] = i*fac[i-1]%mod
  rev[i] = pow(fac[i], mod-2, mod)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%mod

a, b = (2*X-Y)//3, (2*Y-X)//3
if a<0 or b<0:
    print(0)
else:
    print(comb(a+b, a))


### FIXED CODE ###

X, Y = map(int, input().split())

mod = 10**9+7
N = 1333334
fac = [1]*(N+1)
rev = [1]*(N+1)
 
for i in range(1,N+1):
  fac[i] = i*fac[i-1]%mod
  rev[i] = pow(fac[i], mod-2, mod)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%mod

a, b = (2*X-Y)//3, (2*Y-X)//3
if a<0 or b<0 or (2*X-Y)%3 or (2*Y-X)%3:
    print(0)
else:
    print(comb(a+b, a))
### BUGGY CODE ###

n,m = map(int, input().split())
A = list(map(int, input().split()))

for _ in range(m):
  b,c = map(int, input().split())
  A.extend([c]*b)

ans = sorted(A, key=lambda x:-x)
print(sum(ans[:n]))

### FIXED CODE ###

n,m = map(int, input().split())
A = list(map(int, input().split()))
BC = sorted([list(map(int, input().split())) for _ in range(m)], key=lambda x: -x[1])

add = []

for b,c in BC:
  add += [c]*b
  if len(add)>n:
    break
    
ans = sorted(A+add)    
print(sum(ans[-n:]))
### BUGGY CODE ###

import sys
import copy
# def input(): return sys.stdin.readline().rstrip()
# input = sys.stdin.readline
input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10 ** 7)

N, K = map(int, input().split())
# A = np.array(list(map(int, (input().split()))))
A = list(map(int, (input().split())))
# nd = np.zeros((N,N), dtype=bool)
# print(*A)
for i in range(min(K,1000)):
    cnt = [0]*N
    for j in range(N):
        # nd[j, max(j-A[j],0):min(j+A[j]+1,N)] = True
        for k in range(max(j-A[j],0), min(j+A[j]+1,N)):
            cnt[k] += 1
    # print(nd)
    A = copy.copy(cnt)

print(*A)

### FIXED CODE ###

import numpy as np
from numba import njit
import sys
# import copy
# def input(): return sys.stdin.readline().rstrip()
# input = sys.stdin.readline
input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10 ** 7)

N, K = map(int, input().split())
# A = np.array(list(map(int, (input().split()))))
A = np.array(input().split(), dtype=np.int64)
# A = list(map(int, (input().split())))
# nd = np.zeros((N,N), dtype=bool)
# print(*A)

# @njit('(i8[::1],)', cache=True)
@njit(cache=True)
def loop(A):
    for i in range(K):
        # cnt = [0]*N
        cnt = np.zeros_like(A)
        for j, x in enumerate(A):
            # nd[j, max(j-A[j],0):min(j+A[j]+1,N)] = True
            l = max(j-x,0)
            r = min(j+x+1,N)
            cnt[l] += 1
            if r<N:
                cnt[r] -= 1
            # for k in range(max(j-A[j],0), min(j+A[j]+1,N)):
            #     cnt[k] += 1
        # print(nd)
        # A = np.count_nonzero(nd, axis=0)
        # print(cnt)
        A = np.cumsum(cnt)
        if A[0] == A[N-1] == N:
            break
        # print(*A)
    return A

A = loop(A)
print(*A)
### BUGGY CODE ###

N=int(input())
CSF=[]
for i in range(1,N):
  a,b,c=map(int,input().split())
  CSF.append([a,b,c])

for i in range(0,N-1):
  ans=CSF[i][0]+CSF[i][1]
  for j in range(i+1,N-1):
    if ans<=CSF[j][1]:
      ans+=(CSF[j][1]-ans)
    else:
      cnt=1
      while (CSF[j][2]*cnt+CSF[j][1])<ans:
        cnt+=1
      ans+=(CSF[j][2]*cnt+CSF[j][1]-ans)
    ans+=CSF[j][0]
  print(ans)

print(0)


### FIXED CODE ###

N=int(input())
CSF=[]
for i in range(1,N):
  a,b,c=map(int,input().split())
  CSF.append([a,b,c])

for i in range(0,N-1):
  ans=CSF[i][0]+CSF[i][1]
  for j in range(i+1,N-1):
    if ans<=CSF[j][1]:
      ans=CSF[j][1]
    elif ans%CSF[j][2]==0:
      pass
    else:
      ans+=CSF[j][2]-ans%CSF[j][2]
    ans+=CSF[j][0]
  print(ans)

print(0)
### BUGGY CODE ###

import bisect
N = int(input())
Ln = list(map(int,input().split(' ')))

def binary_area_search(target_list: list, target_item: int) -> int:
    '''
    @params
    target_list: [1,3,5](ACC)
    target_item: 2

    @return
    return index
    '''
    low = 0
    high = len(target_list) - 1
    while low <= high:
        mid = (low + high) //2
        guess = target_list[mid]
        if guess > target_item:
            if mid == 0:
                return 0
            if target_item > target_list[mid-1]:
                return mid 
            high = mid -1
        else:
            if mid == len(target_list) - 1:
                return None
            if target_list[mid+1] > target_item:
                return mid + 1 
            low = mid + 1
    return None

def main():
    '''
    N^2*logN
    '''
    Ln.sort()
    count = 0
    for a in range(N):
        a_l = Ln[N-a-1]
        for b in range(a+1, N):
            b_l = Ln[N-b-1]
            c_threshold = a_l - b_l
            c_list = Ln[0:N-b-1]
            #c_idx = bisect.bisect_right(c_list,c_threshold)
            c_idx = binary_area_search(c_list,c_threshold)
            if c_idx is not None:
                count += len(c_list) - c_idx
    print(count)

def main2():
    '''
    N^2
    '''
    Ln.sort(reverse=True)
    count = 0
    for a in range(N):
        a_l = Ln[a]
        current_min = N-1
        b = a +1
        while b <= current_min:
            c_idx = current_min
            bc = Ln[b] + Ln[c_idx]
            if a_l < bc:
                count += (current_min - b)
                b += 1
                continue
            current_min -= 1
    print(count)
main()

### FIXED CODE ###

N = int(input())
Ln = list(map(int,input().split(' ')))
Ln.sort(reverse=True)

count = 0
for a in range(N):
    a_l = Ln[a]
    current_min = N-1
    b = a +1
    while b <= current_min:
        c_idx = current_min
        bc = Ln[b] + Ln[c_idx]
        if a_l < bc:
            count += (current_min - b)
            b += 1
            continue
        current_min -= 1
    '''
    for b in range(a+1, N):
        if b >= current_min:
            break
        for c in range(b+1,N):
            c_idx = current_min
            bc = Ln[b] + Ln[c_idx]
            if a_l < bc:
                count += (current_min - b)
                break
            current_min -= 1
    '''
print(count)
### BUGGY CODE ###

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

c = collections.Counter(a)

keys, values = zip(*c.most_common())

ans = 0

for i in values:
  if i != 1:
  	ans += (i*(i-1)//2)

for i in a:
    for j in range(len(keys)):
      if i == keys[j]:
        co = values[j]
        break
    print(ans-(co*(co-1)//2)+((co-1)*(co-2)//2))

      

### FIXED CODE ###

import collections
n = int(input())
a = list(map(str,input().split()))
ls = [i for i in range(2*10**5)]
c = collections.Counter(a)
comon = c.most_common()
ans = 0

for i in comon:
    if i != 1:
      ls[int(i[0])] = i[1]
      ans += (i[1]*(i[1]-1)//2)

for i in a:
    co = ls[int(i)]
    print(ans-(co*(co-1)//2)+((co-1)*(co-2)//2))
### BUGGY CODE ###

h,n=map(int,input().split())
a,b=[],[]
for i in range(n):
    a_sub,b_sub=map(int,input().split())
    a.append(a_sub)
    b.append(b_sub)
inf=10000000000000
ma=max(a)
dp=[inf]*(h+1+ma)
dp[0]=0
for i in range(n):
    x=[a[i],b[i]]
    for j in range(h+1+ma):
        if dp[j]!=inf:
            if j+x[0]<=h+ma:
                dp[j+x[0]]=min(dp[j+x[0]],dp[j]+x[1])
            else:
                break
print(min(dp[h:]))
#print(dp)


### FIXED CODE ###

h,n=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
ab.sort(reverse=True)
inf=1000000000
ma=ab[0][0]
dp=[inf]*(h+1+ma)
dp[0]=0
for i in range(n):
    x=ab[i]
    for j in range(h):
        if dp[j]!=inf:
            if j+x[0]<=h+ma:
                if j+x[0]>=h:
                    dp[h]=min(dp[h],dp[j]+x[1])
                else:
                    dp[j+x[0]]=min(dp[j+x[0]],dp[j]+x[1])
            else:
                break
print(dp[h])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]
for i in range(Q):
    for j in range(N):
        if A[j] == BC[i][0]:
            A[j] = BC[i][1]
    print(sum(A))

### FIXED CODE ###

import collections

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]

cnt_list = collections.Counter(A)
total = sum(A)
for i in range(Q):
    cnt_list[BC[i][1]] += cnt_list[BC[i][0]]
    total += (BC[i][1] - BC[i][0]) * cnt_list[BC[i][0]]
    cnt_list[BC[i][0]] = 0
    print(total)
### BUGGY CODE ###

N, K = list(map(int, input().split(" ")))
h = input().split(" ")
h = [int(number) for number in h]

minimumCostToReach = [0 for i in range(N)]

minimumCostToReach[0] = 0
for currentIndex in range(1, N):
  minimumCostToReach[currentIndex] = 1000000000

  for previousIndex in range(max(currentIndex - K, 0), currentIndex):
    cost = minimumCostToReach[previousIndex] + abs(h[currentIndex] - h[previousIndex])
    minimumCostToReach[currentIndex] = min(minimumCostToReach[currentIndex], cost)

print(minimumCostToReach[N - 1])


### FIXED CODE ###

def solve():
  N, K = [int(i) for i in input().split()]
  H = [int(i) for i in input().split()]
  dp = [0] * N

  for i in range(1, N):
    dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i - K, 0), i))

  return dp[N - 1]

print(solve())
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, K=map(int,input().strip().split(' '))
x=[]
y=[]
p=[]
for i in range(N):
    xt,yt=map(int,input().strip().split(' '))
    x.append(xt)
    y.append(yt)
    p.append([xt,yt])
ans=10**20
x.sort()
y.sort()
p.sort(key=lambda xt:xt[0])

for i in range(N):
    for j in range(i+1,N):
        xmin=x[i]
        xmax=x[j]
        for k in range(N):
            for l in range(k+1,N):
                ymin=y[k]
                ymax=y[l]
                A=(xmax-xmin)*(ymax-ymin)
                ct=0
                for m in range(N):
                    if xmin<=p[m][0] and p[m][0]<=xmax and ymin<=p[m][1] and p[m][1]<=ymax:
                        ct+=1
                if ct==K:
                    ans=min(ans,A)
                    break
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K=map(int,input().strip().split(' '))
x=[]
y=[]
point=[]
for i in range(N):
    xt,yt=map(int,input().strip().split(' '))
    x.append(xt)
    y.append(yt)
    point.append([xt,yt])
ans=10**20
x.sort()
y.sort()
point.sort(key=lambda x:x[1])


for i in range(N):
    for j in range(i+1,N):
        xmin=x[i]
        xmax=x[j]
        for k in range(N):
            ymin=y[k]
#            ymax=y[l]
#            
            ct=0
            for p in point:
                if xmin<=p[0] and p[0]<=xmax and ymin<=p[1]:
                    ct+=1
                if ct==K:
                    A=(xmax-xmin)*(p[1]-ymin)
                    ans=min(ans,A)
                    break
print(ans)
### BUGGY CODE ###

h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]
        
        num = i
        p = 0
        nex = [0 for _ in range(checker+1)]
        for m in range(h):
            nex[p] += s[m][0]
            p += num%2
            num = num >> 1
        if max(nex) > k:
            x = float('inf')
            continue

        if all(nex[m]+c[m] <= k for m in range(checker+1)):
            c = [c[I]+nex[I] for I in range(checker+1)]
        else:
            x += 1

        for j in range(1, w):
            num = i
            p = 0
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p] += s[m][j]
                p += num%2
                num = num >> 1
            if max(nex) > k:
                x = float('inf')
                break            
            
            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))

### FIXED CODE ###

h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]
        
        num = i
        p = 0
        nex = [0 for _ in range(checker+1)]
        for m in range(h):
            nex[p] += s[m][0]
            p += num%2
            num = num >> 1
        if max(nex) > k:
            x = float('inf')
            continue

        if all(nex[m]+c[m] <= k for m in range(checker+1)):
            c = [c[I]+nex[I] for I in range(checker+1)]
        else:
            x += 1

        for j in range(1, w):
            num = i
            p = 0
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p] += s[m][j]
                p += num%2
                num = num >> 1
            if max(nex) > k:
                x = float('inf')
                break            
            
            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))
### BUGGY CODE ###

N, Q = [int(v) for v in input().split()]

va = [N-1] * (N - 1)
ha = [N-1] * (N - 1)

count = 0
black = (N - 2) * (N - 2)
for i in range(Q):
    a, b = [int(v)-1 for v in input().split()]

    if a == 0:
        for j in range(1, ha[b]):
            if va[j] <= b:
                break
            va[j] = b
        count += ha[b] - 1
    else:
        for j in range(1, va[b]):
            if ha[j] <= b:
                break
            ha[j] = b
        count += va[b] - 1

print(black - count)


### FIXED CODE ###

def main():
    N, Q = [int(v) for v in input().split()]

    Query = [[int(v)-1 for v in input().split()] for _ in range(Q)]

    rows = [N-1] * (N - 1)
    cols = [N-1] * (N - 1)

    black = (N - 2) * (N - 2)
    min_row = N - 1
    min_col = N - 1

    for ty, x in Query:
        if ty == 0:
            if x < min_col:
                for j in range(x, min_col):
                    rows[j] = min_row
                min_col = x
            black -= rows[x] - 1
        else:
            if x < min_row:
                for j in range(x, min_row):
                    cols[j] = min_col
                min_row = x
            black -= cols[x] - 1

    print(black)

main()
### BUGGY CODE ###

import string

char_dict = {c: i for i, c in enumerate(string.digits + string.ascii_letters)}

th, tw = map(int, input().split())
t = [input().strip() for _ in range(th)]
ph, pw = map(int, input().split())


def conv_str(s):
    result = 0
    for c in s:
        result <<= 6
        result += char_dict[c]
    return result


t = [[conv_str(t[i][j:j + pw]) for j in range(tw - pw + 1)] for i in range(th)]
p = [conv_str(input().strip()) for _ in range(ph)]

for i in range(th - ph + 1):
    for j in range(tw - pw + 1):
        for k in range(ph):
            if t[i + k][j] != p[k]:
                break
        else:
            print(i, j)

### FIXED CODE ###

base1 = 127
base2 = 1009
mask = (1 << 32) - 1


def calc_hash(f, r, c):
    global ph, pw, h
    tmp = [[0] * c for _ in range(r)]
    dr, dc = r - ph, c - pw

    t1 = 1
    for _ in range(pw):
        t1 = (t1 * base1) & mask
    for i in range(r):
        e = 0
        for j in range(pw):
            e = e * base1 + f[i][j]
        for j in range(dc):
            tmp[i][j] = e
            e = (e * base1 - t1 * f[i][j] + f[i][j + pw]) & mask
        tmp[i][dc] = e

    t2 = 1
    for _ in range(ph):
        t2 = (t2 * base2) & mask
    for j in range(dc + 1):
        e = 0
        for i in range(ph):
            e = e * base2 + tmp[i][j]
        for i in range(dr):
            h[i][j] = e
            e = (e * base2 - t2 * tmp[i][j] + tmp[i + ph][j]) & mask
        h[dr][j] = e


th, tw = map(int, input().split())
t = [[ord(c) for c in input().strip()] for _ in range(th)]
ph, pw = map(int, input().split())
p = [[ord(c) for c in input().strip()] for _ in range(ph)]

if th >= ph and tw >= pw:
    h = [[0] * tw for _ in range(th)]
    calc_hash(p, ph, pw)
    key = h[0][0] & mask
    calc_hash(t, th, tw)
    for i in range(th - ph + 1):
        for j in range(tw - pw + 1):
            if h[i][j] & mask == key:
                print(i, j)
### BUGGY CODE ###

from collections import Counter
import sys

n, m, k = map(int, input().split())
F = [[] for _ in range(n)]
B = [[0] for _ in range(n)]

sys.setrecursionlimit(10**9)

for _ in range(m):
    a, b = map(int, input().split())
    F[a-1].append(b)
    F[b-1].append(a)

rks = [0]*(n)

def dfs(s,r):
    if rks[s] == 0:
        rks[s] = r
    else:
        return
    for i in F[s]:
        dfs(i-1,r)

r = 0
for i in range(n):
    if rks[i] == 0:
        r += 1
        dfs(i,r)

for _ in range(k):
    c, d = map(int, input().split())
    if rks[c-1] == rks[d-1]:
        B[c-1][0] += 1
        B[d-1][0] += 1

counter = Counter(rks)
for i in range(n):
    print(counter[rks[i]] - len(F[i]) - (B[i][0]) - 1)




### FIXED CODE ###

import sys
from math import *
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]
    
    rks = [None] *n
    sys.setrecursionlimit(10**9)
    # r: どの連結成分に存在するかをメモするid
    def dfs(graph,s,r):
        if rks[s] is None:
            rks[s] = r
        for i in range(len(graph[s])):
            if rks[graph[s][i]-1] is not None:
                continue
            dfs(graph, graph[s][i]-1,r)

    for i in range(m):
        a,b = map(int, input().split())
        fgraph[a-1].append(b)
        fgraph[b-1].append(a)

    # print(fgraph)
    #print(bgraph)
    # 連結成分に対してid的なindexをつける
    c = -1
    for i in range(n):
        if rks[i] is None:
            c += 1
            dfs(fgraph, i, c)
    
    for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)

    counter = Counter(rks)
    for i in range(n):
        # counter[rks[i]] 連結成分のサイズ
        # len(fgraph[i]) 友達の数
        # len(bgraph[i]) 連結成分内のブロックの数
        # 1 自分
        print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

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

#!/usr/bin/env python3
import sys


def solve(A: int, B: int):
    a = A
    for i in range(A+1,B+1):
        a^=i
    
    print(a)
        
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def sum_xor(X: int):
    untilb = 0
    if X%4==3:
        untilb = 0
    elif X%4==1:
        untilb = 1
    else:
        if (X+1)%4==3:
            untilb = 0^(X+1)
        elif (X+1)%4==1:
            untilb = 1^(X+1)

    return untilb

def solve(A: int, B: int):
    print(sum_xor(B)^sum_xor(A-1))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

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

import math
from functools import reduce
from math import gcd
K = int(input())
sum=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            items = [a,b,c]
            d=reduce(gcd,items)
            sum+=d
print(sum)

### FIXED CODE ###

import math
 
 
N = int(input())
 
s = 0
 
for i in range(N):
    for j in range(N):
        ss = math.gcd(i+1,j+1)
        for k in range(N):
            s +=math.gcd(ss,k+1)
 
print(s)
### BUGGY CODE ###

#!/usr/bin/python3

import numpy as np

N = int(input())
nums = np.array(list(map(int, input().split())))

sorted_num = np.sort((nums))

res = 1
for i in range(sorted_num[1], 0, -1):
    nums_div_i = np.remainder(nums, i)

    nums_div_i = nums_div_i > 0
    d = np.sum(np.ones(N) * nums_div_i)
    if d == 1 or d == 0:
        res = i
        break

print(res)


### FIXED CODE ###

#!/snap/bin/pypy3
def gcd(a, b):
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)


def main():
    N = int(input())
    nums = list(map(int, input().split()))

    L = [0 for _ in range(N + 1)]
    R = [0 for _ in range(N + 1)]

    for i, num in enumerate(nums):
        L[i + 1] = gcd(L[i], num)

    for i in range(N - 2, -1, -1):
        R[i] = gcd(R[i + 1], nums[i + 1])

    print(max(gcd(L[i], R[i]) for i in range(N)))


if __name__ == '__main__':
    main()