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

getFirstline = str(input())
getSecondline = str(input())
nfirst = len(getFirstline) 
nsecond = len(getSecondline) 
columns = [0 for _ in range(nfirst + 1)]
dp = [columns[::] for _ in range( nsecond + 1 ) ]

#print(dp)

dicts = {}

for i in range(nfirst + 1):
    curstrs = str(0) + "," + str(i)
    dicts[curstrs] = ""

for i in range(nsecond + 1):
    curstrs = str(i) + "," + str(0)
    dicts[curstrs] = ""


for i in range(nsecond):
    
    for j in range(nfirst):
        ii = i + 1 
        jj = j + 1
        curstrs = str(i) + "," + str(j)
        final = ""
        if getSecondline[i] == getFirstline[j]:
            if curstrs  in dicts:
                final = dicts[curstrs] + str(getSecondline[i])
            else:
                final = str(getSecondline[i])
                
            dp[ii][jj] = dp[ii -1][jj -1] + 1 
            
        else:
            if (dp[ii][jj-1] >= dp[ii-1][jj]):
                curstrs = str(ii) + "," + str(jj -1)
            else:
                curstrs = str(ii - 1) + "," + str(jj)
                
            dp[ii][jj] = max(dp[ii][jj - 1], dp[ii-1][jj])
            
            if curstrs not in dicts:
                final = ""
            else:
                final = dicts[curstrs]
        addcurstrs = str(ii) + "," + str(jj)
        dicts[addcurstrs] = final 
        
# for i in range(nsecond + 1):
#     print(dp[i])
#print(dicts)
finalstring = str(nsecond)+","+ str(nfirst)
#print(finalstring)
print(dicts[finalstring])
    
    

### FIXED CODE ###

s1 = input()
s2 = input()
arra = ["-"]
arrb = ["-"]
for i in s1:
    arra.append(i)
for i in s2:
    arrb.append(i)
n1 = len(s1)
n2 = len(s2)
temparr = [0 for i in range(n2 + 1)]
dp = [temparr[::] for i in range(n1 + 1)]

for i in range(1, n1 + 1):
    for j in range(1 , n2 + 1):
        if arra[i] != arrb[j]:
            dig = dp[i -1][j-1]
            upp = dp[i - 1][j]
            left = dp[i][j - 1]
            dign = dig
            uppn = upp
            leftn = left
            if dign >= uppn and dign >= leftn:
                dp[i][j] = dig
            elif uppn >= dign and uppn >= leftn:
                dp[i][j] = upp
            else:
                dp[i][j] = left
        else:
            dig = dp[i -1][j-1]
            upp = dp[i - 1][j]
            left = dp[i][j - 1]
            dig = dig + 1
            #print(dig)
            
            dign = dig
            uppn = upp
            leftn = left
            if dign >= uppn and dign >= leftn:
                dp[i][j] = dig
            elif uppn >= dign and uppn >= leftn:
                dp[i][j] = upp
            else:
                dp[i][j] = left

# for i in dp:
#     print(i) 
ans = ""

while n2 != 0 and n1 != 0 :
    
    if arra[n1] == arrb[n2]:
        ans += arra[n1]
        n2 -= 1 
        n1 -= 1 
        continue 
    else:
        if dp[n1 - 1][n2] >= dp[n1][n2 - 1]:
            n1 -= 1 
        else:
            n2 -=1 
print(ans[::-1])
### BUGGY CODE ###

N = int(input())
A=[]
l=[1]
ans=0
for i in range(N):
    A.append(int(input()))
for i in range(N):
    l.append(A[l[i]-1])
    if l[i+1]==2:
        ans=i+1
        break
    if l[i+1]in l[:i]:
        break
if ans!=0:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

N = int(input())
A=[]
l=[1]
ans=0
for i in range(N):
    A.append(int(input()))
for i in range(N):
    l.append(A[l[i]-1])
    if l[i+1]==2:
        ans=i+1
        break
if ans!=0:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

def mincuota(listas, N, M, X):
  for i in range(1, M+ 1):
    skill = 0
    for j in range(N):
      skill+= listas[j][i]
    if(skill < X):
      return -1
  else:
    newcuotas = []
    for i in range(N):
      newlistas = listas[:i]+ listas[i+ 1:]
      if(mincuota(newlistas, N- 1, M, X) != -1):
        newcuotas.append(mincuota(newlistas, N- 1, M, X))
    if(newcuotas == []):
      cuota = 0
      for i in range(N):
        cuota+= listas[i][0]
      return cuota
    else:
      return min(newcuotas)
  
N, M, X = map(int, input().split())
listas = []
for i in range(N):
  listas.append(list(map(int, input().split())))

  
print(mincuota(listas, N, M, X))

### FIXED CODE ###

def twodig(x, N):
  l = list(bin(x))
  n = len(l)- 2
  ans = []
  for i in range(N- n):
    ans.append(0)
  for i in range(2, n+ 2):
    ans.append(int(l[i]))
  return ans

N, M, X = map(int, input().split())
lista = []
for i in range(N):
  lista.append(list(map(int, input().split())))
  
count = 1
ans = []

for i in range(2** N):
  flag = 0
  r = twodig(count, N)
  newlista = []
  c = r.count(1)
  for j in range(c):
    index = r.index(1)
    r[index] = 0
    newlista.append(lista[index])
  for k in range(1, M+ 1):
    summ = 0
    for l in range(c):
      summ+= newlista[l][k]
    if(summ < X):
      ans.append(-1)
      flag = 1
      break
  if(flag == 1):
    count+= 1
    continue
  else:
    cuota = 0
    for i in range(c):
      cuota+= newlista[i][0]
    ans.append(cuota)
    count+= 1
    
Ans = list(filter(lambda x: x!= -1, ans))

if(Ans == []):
  print(-1)
else:
  print(min(Ans))
### BUGGY CODE ###

N, M = map(int,input().split())
t = [[] for _ in range(N)]
visited = [0] * N
for _ in range(M):
    X, Y, Z = map(int,input().split())
    X -= 1
    Y -= 1
    t[X].append(Y)
    t[Y].append(X)
for i in range(1, 10 ** 5 + 1):
    s = visited.index(0)
    stack = [s]
    visited[s] = 1
    while stack:
        st = stack.pop()
        for to in t[st]:
            if visited[to]:
                continue
            visited[to] = 1
            stack.append(to)
    if min(visited):
        ans = i
        break
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

def dfs(s):
    if visited[s]:
        return
    visited[s] = 1
    for to in t[s]:
        if visited[to]:
            continue
        dfs(to)
    
N, M = map(int,input().split())
t = [[] for _ in range(N)]
visited = [0] * N
for _ in range(M):
    X, Y, Z = map(int,input().split())
    X -= 1
    Y -= 1
    t[X].append(Y)
    t[Y].append(X)
ans = 0
for i in range(0, N):
    if visited[i]:
        continue
    ans += 1
    dfs(i)
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [True] * len(A)

for i in range(len(A)-1):
    a = A[i]
    if A[i+1] == a:
        B[i] = False
    for j in range(i+1, len(A)):
        if B[j] == True:
            if A[j] % a == 0:
                B[j] = False

print(sum(B))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [False] * (A[-1]+1)

for a in A:
    B[a] = True

for i in range(len(A)-1):
    a = A[i]
    if B[a] == True:
        if A[i] == A[i+1]:
            B[a] = False
        for x in range(2*a, len(B), a):
            B[x] = False

print(sum(B))
### BUGGY CODE ###


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

    # 最低限必要な諭吉を計算
    if 5000 * N < Y:
        n_yukichi = 1
        while True:
            if n_yukichi * 10000 + (N - n_yukichi) * 5000 >= Y:
                yukichi_need = n_yukichi
                break
            n_yukichi += 1
    else:
        yukichi_need = 0

    # 1000円の開始枚数を計算
    noguchi_start = (Y % 5000) // 1000


    for yukichi in range(yukichi_need, N+1):
        for higuchi in range(N-yukichi+1):
            if yukichi + higuchi > N:
                continue

            for noguchi in range(noguchi_start, N-yukichi-higuchi+1, 5):
                if yukichi + higuchi + noguchi > N:
                    break

                if yukichi + higuchi + noguchi < N:
                    continue

                if yukichi*10000 + higuchi*5000 + noguchi*1000 == Y:
                    print(yukichi, higuchi, noguchi)
                    return

    print(-1, -1, -1)
    return

main()


### FIXED CODE ###


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

    # 最低限必要な諭吉を計算
    if 5000 * N < Y:
        n_yukichi = 1
        while True:
            if n_yukichi * 10000 + (N - n_yukichi) * 5000 >= Y:
                yukichi_need = n_yukichi
                break
            n_yukichi += 1
    else:
        yukichi_need = 0

    # 1000円の開始枚数を計算
    noguchi_start = (Y % 5000) // 1000

    for yukichi in range(yukichi_need, N+1):
        for higuchi in range(N+1):
            if yukichi + higuchi > N:
                break

            noguchi = N - yukichi - higuchi

            if yukichi + higuchi + noguchi == N:
                if yukichi*10000 + higuchi*5000 + noguchi*1000 == Y:
                    print(yukichi, higuchi, noguchi)
                    return

    print(-1, -1, -1)
    return

main()
### BUGGY CODE ###

n = int(input())
l = [int(input()) for i in range(n)]
#print(n,l)

L = 0
for i in range(n):
    cnt = 1
    x = l[i]
    for j in range(i+1,n):
        if l[j] <= x:
            cnt += 1
    if L <= cnt:
        L = cnt
print(L)

### FIXED CODE ###

import bisect

N = int(input())
A = [10**10 - int(input()) for i in range(N)]
INF = 10**12

dp = [INF for i in range(N+1)]
#print(A,dp)

for a in A:
    i = bisect.bisect_right(dp,a)
    dp[i] = a
#print(dp)
res = bisect.bisect_left(dp,INF)
print(res)
### BUGGY CODE ###

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

def f(A):
  D=[0]*(N+1)
  for j in range(N):
    mi=max(j-A[j],0)
    ma=min(j+A[j],N-1)
    D[mi]+=1
    D[ma+1]-=1   
  for i in range(1,N):
    D[i]+=D[i-1]
  A=D[:-1]
  return A 

for i in range(min(K,42)):
  A=f(A)
print(*A)

### FIXED CODE ###

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

def f(A):
  D=[0]*(N+1)
  for j in range(N):
    mi=max(j-A[j],0)
    ma=min(j+A[j],N-1)
    D[mi]+=1
    D[ma+1]-=1   
  for i in range(1,N):
    D[i]+=D[i-1]
  A=D[:-1]
  return A 

for i in range(min(K,42)):
  A=f(A)
print(*A)
### BUGGY CODE ###

from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
start = []
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            start.append(i*W+k)

for i in start:
    q.append(i)
    saitan[i] = 0
#print(start)
def bfs(h,w,q,Saitan):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0 and 1000000 in saitan:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if saitan[(my*w + mx)] != 1000000:
                #print('b')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            #Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,saitan))
#print(saitan)

### FIXED CODE ###

from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            q.append(i*W+k)
            saitan[i*W+k] = 0
len_q = len(q)

#print(start)
def bfs(h,w,q,Saitan,len_Q):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0 and len_Q < h * w:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            len_Q += 1
            #Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,saitan,len_q))
#print(saitan)
### BUGGY CODE ###

import bisect
from collections import defaultdict

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

a.sort()
memo = defaultdict(int)
for i in range(n):
    memo[a[i]] += 1

count = 0
for t in reversed(range(1, 31)):
    for i in reversed(range(n)):
        if memo[a[i]] == 0:
            continue
        front = bisect.bisect_left(a, (1 << t) - a[i])
        back = bisect.bisect_right(a, (1 << t) - a[i])
        if front == back:
            continue
        if a[front] == a[i] and memo[a[i]] <= 1:
            continue
        if memo[a[front]] >= 1:
            memo[a[front]] -= 1
            memo[a[i]] -= 1
            count += 1

print(count)

### FIXED CODE ###

from collections import defaultdict

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

a.sort()
memo = defaultdict(int)
for i in range(n):
    memo[a[i]] += 1

count = 0
for i in reversed(range(n)):
    if memo[a[i]] == 0:
        continue
    if (memo[(1 << (len(bin(a[i])) - 2)) - a[i]] > 0 and (1 << (len(bin(a[i])) - 2)) - a[i] != a[i]) or memo[(1 << (len(bin(a[i])) - 2)) - a[i]] > 1:
        memo[a[i]] -= 1
        memo[(1 << (len(bin(a[i])) - 2)) - a[i]] -= 1
        count += 1

print(count)
### BUGGY CODE ###

from collections import Counter
N = int(input())
X = str(input())
X10 = int(X,2)

one_num = Counter(X)["1"]

for i in range(N):
    target = int(X[i])
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        plus = -pow(2,N-i-1)
        ones = one_num-1
    
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    else:
        Xnow = Xnow%ones
        count+=1
        while Xnow > 0:
            Xnow2 = format(Xnow, 'b')
            ones = 0
            for j in range(len(Xnow2)):
                if Xnow2[j] == "1":
                    ones += 1
            Xnow = Xnow%ones
            count+=1
        print(count)

### FIXED CODE ###

N = int(input())
x2 = input()
x10 = int(x2, 2)
popc =  x2.count("1")
#print("x10", x10)
#print("popc", popc)
#popc: Nを2進数で表したときの1の個数

#以下で1つフリップさせた時の入力に対する余りを事前に計算
if popc <= 1:
    xp = x10%(popc+1)
    xm = 0
else:
    xp = x10%(popc+1)
    xm = x10%(popc-1)
#print("xp", xp)
#print("xm", xm)

#以下でフリップさせた場所のみを計算
for i in range(N):
    if x2[i] == "1":
        if popc == 1:
            print(0)
            continue
        tmp = (xm - pow(2, N-i-1, popc-1))%(popc-1)
    else:
        tmp = (xp + pow(2, N-i-1, popc+1))%(popc+1)
        
    #print("tmp", tmp)
    ans = 1
    while tmp > 0:
        tmp %= bin(tmp).count("1")
        ans += 1
    print(ans)
### BUGGY CODE ###

import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
data=[list(map(int,input().split())) for i in range(m)]
a.sort()
for b,c in data:
	point=bisect.bisect_left(a,c)
	if point<=b:
		a[:point]=[c]*point
	else:
		a[:b]=[c]*b
		a[:point]=a[b:point]+a[:b]
print(sum(a))





### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline()[:-1]
n,m=map(int,input().split())
a0=list(map(int,input().split()))
data=[list(map(int,input().split())) for i in range(m)]
for i in a0:
	data.append([1,i])
data.sort(key=lambda tup:-tup[1])
ans=0
for num,val in data:
	if n>=num:
		n-=num
		ans+=val*num
	else:
		ans+=val*n
		break
print(ans)
### BUGGY CODE ###

# import bisect
# import copy
import fractions
# import math
# import numpy as np
# from collections import Counter, deque
from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product

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

    def gcd(*numbers):
        return reduce(fractions.gcd, numbers)

    maxgcd=0
    for i in range(N):
        maxgcd=max(maxgcd,gcd(*(A[:i]+A[i+1:])))

    print(maxgcd)


resolve()

### FIXED CODE ###

# import bisect
# import copy
from fractions import gcd


# import math
# import numpy as np
# from collections import Counter, deque
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
import sys
sys.setrecursionlimit(10**9)


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

    # A[0:i]の最大公約数
    L=[0]*N
    for i in range(1,N):
        L[i]=gcd(L[i - 1], A[i - 1])

    # A[i:]の最大公約数
    R=[0]*(N+1)
    for i in reversed(range(N)):
        R[i]=gcd(R[i + 1], A[i])


    maxgcd = 0
    for i in range(N):
        maxgcd = max(maxgcd, gcd(L[i], R[i + 1]))

    print(maxgcd)


resolve()
### BUGGY CODE ###

n = input()
R = []
for i in range(n):
    R.append(input())

profit = R[n-1] - R[0]
after = R[n-1]
for i in range(n):
    if R[n-1-i] < after and i != 0:
        continue
    for j in range(n-i-1):
        if R[n-1-i] - R[j] > profit:
            profit = R[n-1-i] - R[j]
            after = R[n-1-i]
print "%d" % profit

### FIXED CODE ###

n = input()
R = []
for i in range(n):
    R.append(input())

maxv = R[1] - R[0]
minv = R[0]
for j in range(1, n):
    maxv = max(maxv, R[j] - minv)
    minv = min(minv, R[j])

print "%d" % maxv
### BUGGY CODE ###

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

ans = 0
for i in range(n-1):
    ans += (a[i] * sum(a[(i+1):]))

print(ans%(10**9+7))

### FIXED CODE ###

import numpy as np
n = int(input())
a = list(map(int,input().split()))
a_sum = sum(a)
aa = np.array(np.cumsum(a),dtype="object")
all_a = sum(a)

mod = 1000000007

ans = 0
for i in range(n-1):
    ans += (a[i]%mod * (all_a - aa[i])%mod)

print(ans%mod)
### BUGGY CODE ###


import sys

sys.setrecursionlimit(200000)

n,q = (int(num) for num in input().split())
neighbor = [[] for _ in range(n)]
visited = [0] * n
val = [0] * n
ab = []
for i in range(n-1):
    a,b = (int(num)-1 for num in input().split())
    ab.append((a,b))

    
for item in ab:
    a = item[0]
    b = item[1]
    neighbor[a].append(b)
    neighbor[b].append(a)
    
        
#print(par)
#print(neighbor)
#print(rank)

for _ in range(q):
    p,x = (int(num) for num in input().split())
    p -= 1
    val[p] += x
    
def calc(idx,neighbor,val,bias):
    val[idx] += bias
    for i in neighbor[idx]:
        if visited[i] == 0:
            visited[i] = 1
            calc(i,neighbor,val,val[idx])

visited[0] = 1
calc(0,neighbor,val,0)    
ans = ""    
for num in val:
    ans += str(num) + " "
print(ans)




### FIXED CODE ###

n,q = (int(num) for num in input().split())
par = [n] * n
visited = [0] * n
val = [0] * n
ab = []
for i in range(n-1):
    a,b = (int(num)-1 for num in input().split())
    par[b] = a
    
for _ in range(q):
    p,x = (int(num) for num in input().split())
    p -= 1
    val[p] += x

for i in range(1,n):
    val[i] += val[par[i]]
    
ans = ""
for num in val:
    ans += str(num) + " "
print(ans)
### BUGGY CODE ###

from itertools import combinations
def main():
    n=int(input())
    aa=list(map(int,input().split()))
    c=0
    for i,j in combinations(range(n), 2):
        if j-i==aa[i]+aa[j]:
            c+=1
    print(c)
main()

### FIXED CODE ###

def main():
    n=int(input())
    aa=list(map(int,input().split()))
    ll={}
    c=0
    for i,a in enumerate(aa,1):
        x=i-a
        if x in ll:
            c+=len(ll[x])
        y=i+a
        if y in ll:
            ll[y].append(i)
        else:
            ll[y]=[i]
    print(c)
main()
### BUGGY CODE ###

n=int(input())
a=[]
b=[]
for i in range(n):
  tmpa,tmpb=map(int,input().split())
  a.append(tmpa)
  b.append(tmpb)

for i in range(n):
  if sum(a)<=max(b):
    index=b.index(max(b))
    del a[index]
    del b[index]
  else:
    print('No')
    exit()
print('Yes')

### FIXED CODE ###

n = int(input())
tasks = [list(map(int, input().split())) for i in range(n)]
tasks.sort(key=lambda x: x[1])

time = 0
for task in tasks:
    time += task[0]
    if time > task[1]:
        print("No")
        exit()
print("Yes")
### BUGGY CODE ###

def main():
    N = int(input())
    P = list(map(int, input().split()))
    
    count = 0
    for i in range(N):
        flag = True
        for j in range(i):
            if P[i] > P[j]: 
                flag = False
                break

        if flag:
            count += 1
    print(count)
if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    P = list(map(int, input().split()))
    
    count = 0
    k = 0
    for i in range(N):
        flag = True
        for j in range(k, i):
            if P[i] > P[j]: 
                flag = False
                break

        if flag:
            count += 1
            k = i
            
    print(count)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import fractions
from functools import reduce

n = int(input())

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


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


gcd_l = [0]
gcd_r = []
for i in range(1,n+1):
    a_l = a[:i-1]
    a_r = a[i:]
    if a_l:
        gcd_l.append(gcd_list(a_l))
    if a_r:
        gcd_r.append(gcd_list(a_r))
gcd_r = gcd_r + [0]

ans = 0
for i in range(n):
    if gcd_l[i] == 0:
        gcd = gcd_r[i]
    if gcd_r[i] == 0:
        gcd = gcd_l[i]
    else:
        gcd = fractions.gcd(gcd_l[i],gcd_r[i])
    ans = max(gcd,ans)

print(ans)

### FIXED CODE ###

import fractions
from functools import reduce

n = int(input())

a = list(map(int,input().split()))
#
# a = [4,8,12,9,16]


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


gcd_l = [a[0]]
gcd_r = [a[-1]]
for i in range(1,n):
    gcd_l.append(fractions.gcd(gcd_l[i-1],a[i]))
    gcd_r.append(fractions.gcd(gcd_r[i-1],a[-i-1]))

gcd_r.reverse()

ans = max(gcd_r[1],gcd_l[-2])
for i in range(1,n-1):
    gcd = fractions.gcd(gcd_l[i-1],gcd_r[i+1])
    ans = max(ans,gcd)

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

n = int(input())
v = [int(_) for _ in input().split()]
x = v[::2]
y = v[1::2]
if len(set(x)) == 1 and len(set(y)) == 1:
    if x[0] == y[0]:
        print(len(y))
    else:
        print(0)
elif len(set(x)) != 0 and len(set(y)) == 1:
    u = sorted([[x[i],x.count(x[i])] for i in range(len(x))],key=lambda t:-t[1])
    max1 = u[0][1]
    moji1 = u[0][0]
    max2 = 0
    moji2 = 0
    for i in range(len(x)):
        if u[i][0] != moji1:
            moji2 = u[i][0]
            max2 = u[i][1]
            break
    if moji1 != y[0]:
        print(len(x) - max1)
    else:
        print(len(x) - max2)
elif len(set(y)) != 0 and len(set(x)) == 1:
    v = sorted([[y[i],y.count(y[i])] for i in range(len(y))],key=lambda t:-t[1])
    max3 = v[0][1]
    moji3 = v[0][0]
    max4 = 0
    moji4 = 0
    for i in range(len(y)):
        if v[i][0] != moji3:
            moji4 = v[i][0]
            max4 = v[i][1]
            break
    if moji3 != y[0]:
        print(len(x) - max3)
    else:
        print(len(x) - max4)
else:
    u = sorted([[x[i],x.count(x[i])] for i in range(len(x))],key=lambda t:-t[1])
    max1 = u[0][1]
    moji1 = u[0][0]
    max2 = 0
    moji2 = 0
    for i in range(len(x)):
        if u[i][0] != moji1:
            moji2 = u[i][0]
            max2 = u[i][1]
            break
    v = sorted([[y[i],y.count(y[i])] for i in range(len(y))],key=lambda t:-t[1])
    max3 = v[0][1]
    moji3 = v[0][0]
    max4 = 0
    moji4 = 0
    for i in range(len(y)):
        if v[i][0] != moji3:
            moji4 = v[i][0]
            max4 = v[i][1]
            break
    if moji1 != moji3:
        print(n - max1 - max3)
    else:
        print(min(n-max1-max4,n-max2-max3))

### FIXED CODE ###

import collections

n = int(input())
v = [int(_) for _ in input().split()]

v_even = v[::2]
v_odd = v[1::2]

a_even = collections.Counter(v_even)
a_odd = collections.Counter(v_odd)

li_even = a_even.most_common()
li_odd = a_odd.most_common()

if li_even[0][0] != li_odd[0][0]:
    print(n - li_even[0][1] - li_odd[0][1])
else:
    if len(li_even) != 1 and len(li_odd) != 1:
        print(min(n - li_even[0][1] - li_odd[1][1],n - li_even[1][1] - li_odd[0][1]))
    elif len(li_even) != 1 and len(li_odd) == 1:
        print(int(n/2) - li_even[1][1])
    elif len(li_even) == 1 and len(li_odd) != 1:
        print(int(n/2) - li_odd[1][1])
    else:
        print(int(n/2))