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

import sys
input=sys.stdin.readline
def main():
  n=int(input())
  b=[0]*n
  w=[0]*n
  for i in range(2*n):
    c,a=input().split()
    if c=="B":b[int(a)-1]=i
    else:w[int(a)-1]=i
  bit=[2*n*[0]for _ in range(n+1)]
  dp=[(n+1)*[10**10]for _ in range(n+1)]
  dp[0][0]=0
  for i in range(n+1):
    dp[i][0]=0
    for k in range(i):
      a=0
      ind=2*n
      while ind:
        a+=bit[i][ind-1]
        ind-=ind&-ind
      if w[k]!=0:
        ind=w[k]
        while ind:
          a-=bit[i][ind-1]
          ind-=ind&-ind
      dp[i][0]+=w[k]+a-k
      ind=w[k]+1
      while ind<=2*n:
        bit[i][ind-1]+=1
        ind+=ind&-ind
  for j in range(n):
    for i in range(n+1):
      ba=0
      ind=2*n
      while ind:
        ba+=bit[i][ind-1]
        ind-=ind&-ind
      if b[j]!=0:
        ind=b[j]
        while ind:
          ba-=bit[i][ind-1]
          ind-=ind&-ind
      if i==0:
        dp[i][j+1]=dp[i][j]+b[j]+ba-(i+j)
      else:
        dp[i][j+1]=dp[i][j]+(b[j]+ba-(i+j))
        wa=0
        ind=2*n
        while ind:
          wa+=bit[i-1][ind-1]
          ind-=ind&-ind
        if w[i-1]!=0:
          ind=w[i-1]
          while ind:
            wa-=bit[i-1][ind-1]
            ind-=ind&-ind
        dp[i][j+1]=min(dp[i][j+1],dp[i-1][j+1]+(w[i-1]+wa-(i+j)))
      ind=b[j]+1
      while ind<=2*n:
        bit[i][ind-1]+=1
        ind+=ind&-ind
  print(dp[n][n])

if __name__ == "__main__":
  main()

### FIXED CODE ###

n=int(input())
b=[0]*n
w=[0]*n
for i in range(2*n):
  c,a=input().split()
  if c=="B":b[int(a)-1]=i
  else:w[int(a)-1]=i
bit=[0]*2*n
dp=[(n+1)*[10**10]for _ in range(n+1)]
dp[0][0]=0
for i in range(n+1):
  bitt=bit[:]
  for j in range(n):
    a=0
    k=2*n
    while k:
      a+=bitt[k-1]
      k-=k&-k
    if w[j]!=0:
      k=w[j]
      while k:
        a-=bitt[k-1]
        k-=k&-k
    dp[i][j+1]=min(dp[i][j+1],dp[i][j]+a+w[j]-(i+j))
    k=w[j]+1
    while k<=2*n:
      bitt[k-1]+=1
      k+=k&-k
    if i!=n:
      a=0
      k=2*n
      while k:
        a+=bitt[k-1]
        k-=k&-k
      if b[i]!=0:
        k=b[i]
        while k:
          a-=bitt[k-1]
          k-=k&-k
      dp[i+1][j+1]=dp[i][j+1]+a+b[i]-(i+j+1)
  if i!=n:
    a=b[i]-i
    k=2*n
    while k:
      a+=bit[k-1]
      k-=k&-k
    if b[i]!=0:
      k=b[i]
      while k:
        a-=bit[k-1]
        k-=k&-k
    dp[i+1][0]=dp[i][0]+a
    k=b[i]+1
    while k<=2*n:
      bit[k-1]+=1
      k+=k&-k
print(dp[n][n])
### BUGGY CODE ###

n, k = [int(i) for i in input().split()]
arr = [int(i) for i in input().split()]


dp = [float('inf')] * n
dp[0] = 0

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

### FIXED CODE ###

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

def frog(n, k, h):
    d = [float('inf')] * n
    d[0] = 0

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


print(frog(n, k, h))
### BUGGY CODE ###

n=int(input())
l = list(map(int,input().split()))	
l.sort()
ans=0
if l[0]+l[1]>l[n-1]:
    print((n*(n-1)*(n-2))//6)
    exit()
else:
    for i in range(n-2):
        for j in range(n-i-2):
            j+=i+1
            if l[i]+l[j]>l[n-1]:
                ans+=((n-j-1)*(n-j))//2
                break
            for k in range(n-j-1):
                k+=j+1
                if l[i]+l[j]>l[k]:
                    ans+=1
                else:
                    break
print(ans)


### FIXED CODE ###

def main():
    n = int(input())
    l = list(map(int,input().split()))
    l.sort()
    l.append(10**7)
    ans=0

    for i in range(n-2):
        for j in range(i+1,n-1):
            ok=j
            ng=n
            while ng-ok>1:
                mid = (ok + ng)//2
                if l[mid] < l[i] + l[j]:
                    ok=mid
                else:
                    ng=mid  
            ans+=ok-j
            
    print(ans)

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

n,k = map(int,input().split())
a = list(map(int, input().split()))
dp = [0 for _ in range(n)]
dp[1] = abs(a[1] - a[0])
for i in range(2, n):
    dp[i]=dp[i-1]+abs(a[i]-a[i-1])
    for j in range(2,k+1):
        if j>i:
            break
        else:
            dp[i] = min(dp[i],dp[i-j]+abs(a[i]-a[i-j]))
print(dp[-1])

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int, input().split()))
dp = [0 for _ in range(n)]
dp[1] = abs(a[1] - a[0])
for i in range(2, n):
    dp[i]=dp[i-1]+abs(a[i]-a[i-1])
    for j in range(2,k+1):
        if j>i:
            break
        else:
            dp[i] = min(dp[i],dp[i-j]+abs(a[i]-a[i-j]))
print(dp[-1])
### BUGGY CODE ###

N = input()
M = [map(int, raw_input().split()) for i in xrange(N)]
cache = {}
for i in xrange(N):
    cache[(i, i+1)] = 0
def dfs(left, right):#[left, right)
    if (left, right) in cache:
        return cache[(left, right)]
    min_cost = float("inf")
    for mid in xrange(left+1, right):
        tmp = M[left][0] * M[mid-1][1] * M[right-1][1]
        tmp += dfs(left, mid)
        tmp += dfs(mid, right)
        if min_cost > tmp:
            min_cost = tmp
    return min_cost
print dfs(0, len(M))

### FIXED CODE ###

N = input()
M = [map(int, raw_input().split()) for i in xrange(N)]
cache = {}
for i in xrange(N):
    cache[(i, i+1)] = 0
def dfs(left, right):
    if (left, right) in cache:
        return cache[(left, right)]
    min_cost = float("inf")
    for mid in xrange(left+1, right):
        tmp = M[left][0] * M[mid-1][1] * M[right-1][1]
        tmp += dfs(left, mid)
        tmp += dfs(mid, right)
        if min_cost > tmp:
            min_cost = tmp
    cache[(left, right)] = min_cost
    return min_cost
print dfs(0, len(M))
### BUGGY CODE ###

import sys

R, C, K = map(int, sys.stdin.readline().split())

grid = [[-1 for _ in range(C)] for _ in range(R)]
for _ in range(K):
    r, c, v = map(int, sys.stdin.readline().split())
    grid[r-1][c-1] = v

# r行目、c列目にいるときに、その行でアイテムをi個取得している場合の最大価値
dp = [[[0 for _ in range(3+1)] for _ in range(C+1)] for _ in range(R+1)]
# print(dp)
for r in range(R):
    for c in range(C):
        for i in range(4):
            # 取らない
            if r < R:
                dp[r+1][c][0] = max(dp[r][c][i], dp[r+1][c][0])
            if c < C:
                dp[r][c+1][i] = max(dp[r][c][i], dp[r][c+1][i])

            # 取る
            if i < 3:
                # print(r, c, i)
                dp[r+1][c][0] = max(dp[r][c][i] + grid[r][c], dp[r+1][c][0])
                dp[r][c+1][i+1] = max(dp[r][c][i] + grid[r][c], dp[r][c+1][i+1])

# print(dp[R][C])
print(max(dp[R-1][C]))

### FIXED CODE ###

import sys

R, C, K = map(int, sys.stdin.readline().split())

grid = [[0 for _ in range(C)] for _ in range(R)]
for _ in range(K):
    r, c, v = map(int, sys.stdin.readline().split())
    grid[r-1][c-1] = v

# r行目、c列目にいるときに、その行でアイテムをi個取得している場合の最大価値
dp0 = [[0 for _ in range(C+1)] for _ in range(R+1)]
dp1 = [[0 for _ in range(C+1)] for _ in range(R+1)]
dp2 = [[0 for _ in range(C+1)] for _ in range(R+1)]
dp3 = [[0 for _ in range(C+1)] for _ in range(R+1)]
# print(dp)
for r in range(R):
    for c in range(C):
        # 取らない
        dp0[r+1][c] = max((dp0[r][c], dp1[r][c], dp2[r][c], dp3[r][c]))
        dp1[r][c+1] = max(dp1[r][c], dp1[r][c])
        dp2[r][c+1] = max(dp2[r][c], dp2[r][c])
        dp3[r][c+1] = max(dp3[r][c], dp3[r][c])

        if grid[r][c] == 0:
            continue
        # 取る
        dp0[r+1][c] = max(dp0[r][c] + grid[r][c], dp0[r+1][c])
        dp0[r+1][c] = max(dp1[r][c] + grid[r][c], dp0[r+1][c])
        dp0[r+1][c] = max(dp2[r][c] + grid[r][c], dp0[r+1][c])

        dp1[r][c+1] = max(dp0[r][c] + grid[r][c], dp1[r][c+1])
        dp2[r][c+1] = max(dp1[r][c] + grid[r][c], dp2[r][c+1])
        dp3[r][c+1] = max(dp2[r][c] + grid[r][c], dp3[r][c+1])

# print(dp0)
# print(dp1)
# print(dp2)
# print(dp3)
# print(max((dp0[R][C], dp1[R][C], dp2[R][C], dp3[R][C])))
print(dp0[R][C-1])
### BUGGY CODE ###

n=int(input())
l=[int(x) for x in input().split()]
l.sort()
s=0
for a in range(0,n-2):
    for b in range(a+1,n-1):
        c=b+1
        while l[c]<l[a]+l[b]:
            s=s+1
            c=c+1
            if c==n:
                break
print(s)

### FIXED CODE ###

def bis_right(lis,dev):
    a=0
    b=len(lis)-1
    while a<b:
        c=(a+b)//2
        if lis[c]>dev:
            b=c
        else:
            a=c+1
    if lis[a]<=dev:
        return a
    return a-1



n=int(input())
l=[int(x) for x in input().split()]
l.sort()
s=0
for a in range(n-2):
    for b in range(a+1,n-1):
        c=bis_right(l[b+1:],l[a]+l[b]-1)
        s+=c+1
print(s)
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
while True:
    if A.count(0) == n - 1:
        print(max(A))
        exit()
    else:
        B = [ _  for _ in A if _ != 0  ]
        attack = min(B)
        sn = A.index(attack)
        
        for i in range(n):
            if A[i] == 0:
                pass
            else:
                if i != sn:
                    A[i] = A[i] - attack
                else:
                    pass


### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
while True:
    if A.count(0) == n - 1:
        print(max(A))
        exit()
    else:
        B = [ _  for _ in A if _ != 0  ]
        attack = min(B)
        sn = A.index(attack)
        
        for i in range(n):
            if A[i] == 0:
                pass
            else:
                if i != sn:
                    A[i] = A[i] % attack
                else:
                    pass
### BUGGY CODE ###

from itertools import product

def sol():
    N = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]
    P = [p for _, _, p in XYP]
    INF = 10**18

    def calcCost(AP, A):
        ret = [[INF] * N for _ in range(1 << N)]
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i, (a, p) in enumerate(AP):
                cost = abs(a)
                for z in useA:
                    cost = min(cost, abs(a - z))
                ret[state][i] = cost * p
        return ret

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    ans = [INF] * (N + 1)
    for state in product((0, 1, 2), repeat=N):
        stateX = 0
        stateY = 0
        M = N
        for s in state:
            stateX <<= 1
            stateY <<= 1
            if s == 0: M -= 1
            if s == 1: stateX |= 1
            if s == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for s in map(min, zip(cx, cy)):
            cost += s
            if cost >= ans[M]:
                break
        else:
            ans[M] = cost

    print(*ans, sep='\n')

sol()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:])')
def solve(N, XYP):
    X = XYP[:, 0]
    Y = XYP[:, 1]

    def calcCost(sign, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i in range(N):
                xyp = XYP[i]
                cost = abs(xyp[sign])
                for z in useA:
                    cost = min(cost, abs(xyp[sign] - z))
                ret[state][i] = cost * xyp[2]
        return ret

    costX = calcCost(0, X)
    costY = calcCost(1, Y)
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = np.asarray([list(map(int, input().split())) for _ in range(N)])
    solve(N, XYP)

sol()
### BUGGY CODE ###

import itertools

N = int(input())
V = list(map(int,input().split()))
C = list(map(int,input().split()))
temp = itertools.product([0, 1], repeat=N)
ans = 0
for T in temp:
    an = 0
    for i, e in enumerate(T):
        if e == 1:
            an += V[i] - C[i]
    ans = max(ans,an)
print(ans)


### FIXED CODE ###

import itertools

N = int(input())
V = list(map(int,input().split()))
C = list(map(int,input().split()))
temp = itertools.product([0, 1], repeat=N)
ans = 0
for T in temp:
    an = 0
    for i, e in enumerate(T):
        if e == 1:
            an += V[i] - C[i]
    ans = max(ans,an)
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
s=set(a)
l=len(s)
data=[0]*(2*l)
t=0
for i in s:
  if a.count(i)>=4:
    if data.count(i)!=2:
      data[t]=i
      t+=1
      data[t]=i
      t+=1
  elif 2<=a.count(i)<4:
    if data.count(i)!=1:
      data[t]=i
      t+=1
data.sort(reverse=True)
print(data[0]*data[1])

### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
A=Counter(a)
s=set(a)
S=sorted(list(s))
S.reverse()
h=0
w=0
for i in S:
  res=A[i]
  if res>=4:
    if h==0:
      h=i
    if w==0:
      w=i
  elif 2<=res<4:
    if w==0:
      w=i
    elif w!=0 and h==0:
      h=i
print(h*w)
### BUGGY CODE ###

n,k = map(int,input().split())
s = input()

if s[0] == '1':
    length_01 = []
else:
    length_01 = [0]

a = 1
for i in range(n-1):
    if s[i] == s[i+1]:
        a += 1
    else:
        length_01.append(a)
        a = 1

length_01.append(a)
if s[n-1] == '0':
    length_01.append(0)

num_0 = int((len(length_01)+1)/2)
if num_0 - 1 >= k:
    answer = 0
    for i in range(num_0):
        if answer < sum(length_01[2*i:2*(i+k)+1]):
            answer = sum(length_01[2*i:2*(i+k)+1])
else:
    answer = len(s)

print(answer)


### FIXED CODE ###

n,k = map(int,input().split())
s = input()

if s[0] == '1':
    length_01 = [0]
else:
    length_01 = [0,0]

for i in range(n-1):
    if s[i] != s[i+1]:
        length_01.append(i+1)

if s[n-1] == '1':
    length_01.append(n)
else:
    length_01.append(n)
    length_01.append(n)

num_0 = int(len(length_01)/2)
if num_0 - k >= 1:
    answer = 0
    for i in range(num_0 - k):
        if answer < length_01[2*(i+k)+1] - length_01[2*i]:
            answer = length_01[2*(i+k)+1] - length_01[2*i]
else:
    answer = n

print(answer)
### BUGGY CODE ###

S = input()
Q = int(input())
for _ in range(Q):
    q = input()
    if q!='1':
        tmp = []
        if q[2]=='1':
            tmp.append(q[4])
            tmp.append(S)
        else:
            tmp.append(S)
            tmp.append(q[4])
        S = ''.join(tmp)
    else:
        S = S[::-1]
print(S)

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
s = 1
for _ in range(Q):
    q = input()
    if q!='1':
        if (q[2]=='1' and s==1) or (q[2]!='1' and s!=1):
            S.extendleft(q[4])
        else:
            S.extend(q[4])
    else:
        s *= -1
S = ''.join(list(S))
if s==1:
    print(S)
else:
    print(S[::-1])
### BUGGY CODE ###

import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")

import fractions
from functools import reduce

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

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



N=int(input())
A = [int(i) for i in input().split()]	# 1 2 3 4 5 ...

#p(N)
#p(A)

ans=0
for i in range(len(A)):
	#p(i, A[i], A[:i], A[i+1:])
	B=A[:i]+A[i+1:]
	#p(B)
	c=gcd_list(B)
	ans=max(ans,c)

print(ans)


### FIXED CODE ###

import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")

import fractions
from functools import reduce

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

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



N=int(input())
A=[int(i) for i in input().split()]	# 1 2 3 4 5 ...

p("N", N)
p("A", A)


if N==2:
	print( max(A) )
	exit()


L=[0]*(N)		#左側用
R=[0]*(N)		#右側用



L[0]=A[0]		#初項は、Aの左端
p("L", L)
for i in range(1,N):
	L[i]=gcd(L[i-1],A[i])
	p(i, L[i])
p("L", L)



R[N-1]=A[N-1]		#初項は、Aの右端
p("R", R)
for i in range(N-2,-1,-1):
	R[i]=gcd(R[i+1],A[i])
	p(i, R[i+1])
p("R", R)



M=[0]*N
for i in range(1,N-1):
	M[i]=gcd(L[i-1],R[i+1])		#A[i]を起点に、左側(L[i-1])、右側(R[i+1])
p("M", M)

M[0]=R[1]				#左端は、右側のみ
M[N-1]=L[N-2]		#右端は、左側のみ

p("M", M)

print( max(M) )
### BUGGY CODE ###

n, p = map(int, input().split())
s = input()

ans = 0
mod = {0: 0}

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    s = int(s)
    for i in range(1, n+1):
        m = s % (10**i) % p
        mod[m] = mod.get(m, -1)+1
    for m in mod.values():
        ans += m*(m+1)//2

print(ans)


### FIXED CODE ###

n, p = map(int, input().split())
s = input()

ans = 0
mod = [-1 for i in range(p)]
mod[0] = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    mp = 0
    m10 = 1
    for i in range(n-1, -1, -1):
        m10 = (10 * m10) % p
        mp = (mp + int(s[i]) * m10) % p
        mod[mp] += 1

    for m in mod:
        ans += m*(m+1)//2

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

def putty(n):
    if (n == 0):
        return "P"
    return "B"+putty(n-1)+"P"+putty(n-1)+"B"

n, x = map(int, input().split())
a = putty(n)
a = a[:x]
print(a.count("P"))

### FIXED CODE ###

def f(n, x):
    if n == 0:
        return 0 if x <= 0 else 1
    elif x <= (a[n-1] + 1):
        return f(n - 1, x - 1)
    else:
        return p[n - 1] + 1 + f(n - 1, x - 2 - a[n - 1])


n, x = map(int, input().split())

a, p=[1],[1]
for i in range(n):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)
    
print(f(n, x))
### BUGGY CODE ###

from functools import reduce
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))


def lcm_base(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


lcm = A[0]
for i in range(1, N):
    lcm = lcm * A[i] // gcd(lcm, A[i])

y = lcm_list(A)
MOD = 10 ** 9 + 7
ans = 0
for i, a in enumerate(A):
    ans += y // a
    ans %= MOD

print(ans)


### FIXED CODE ###

from functools import reduce
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))


lcm = A[0]
for a in A[1:]:
    lcm = lcm * a // gcd(lcm, a)


MOD = 10 ** 9 + 7
lcm %= MOD
ans = 0
for a in A:
    ans += lcm * pow(a, MOD-2, MOD)
    ans %= MOD

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

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

#初期値が0の辞書
from collections import defaultdict
xyz = defaultdict(lambda: set([]))
for _ in range(m):
    x,y,z=map(int,input().split())
    xyz[x].add(y)
    xyz[y].add(x)

checked=set([])

cnt=0
for i in range(1,n+1):
    if i not in checked:
        cnt+=1
        temp=set([])
        temp.add(i)
        checked.add(i)
        while len(list(temp))>0:
            v=temp.pop()
            for item in xyz[v]:
                if item not in checked:
                    checked.add(item)
                    temp.add(item)
                    xyz[item].remove(v)
    #print(i,checked)
print(cnt)



### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

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

#初期値が0の辞書
from collections import defaultdict
xyz = defaultdict(lambda: set([]))
for _ in range(m):
    x,y,z=map(int,input().split())
    xyz[x].add(y)
    xyz[y].add(x)

no_checked=[0]*n

def DFS(x):
    global no_checked
    global xyz
    no_checked[x-1]=1
    for item in xyz[x]:
        if no_checked[item-1]==0:
            DFS(item)

cnt=0
for i in range(1,n+1):
    if no_checked[i-1]==0:
        cnt+=1
        DFS(i)

    #print(i,no_checked)
print(cnt)
### BUGGY CODE ###

import heapq

N, M = map(int, input().split())
dic = {}
for i in range(N):
    A, B = map(int, input().split())
    if A not in dic:
        dic[A] = [-B]
    else:
        dic[A] += [-B]

ans = 0
heap = []

for i in range(M):
    # print(i)
    if i + 1 in dic:
        heap += dic[i + 1]
    heapq.heapify(heap)
    # print(heap)
    if heap:
        ans += -heapq.heappop(heap)

print(ans)


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
dic = {}
for i in range(N):
    A, B = map(int, input().split())
    if A not in dic:
        dic[A] = [-B]
    else:
        dic[A].append(-B)
# print(dic, sorted(dic.keys()))

ans = 0
heap = []

for i in range(M):
    # print(i)
    if i + 1 in dic:
        for j in dic[i + 1]:
            heapq.heappush(heap, j)
    # print(heap)
    if heap:
        ans = ans - heapq.heappop(heap)

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

from sys import stdin, stdout
def readLine_int_list():return list(map(int, stdin.readline().split()))


def main():
    n = int(input())
    a = readLine_int_list()
    set_a = sorted(list(set(a)), reverse=True)
    
    pair = []
    
    ans = 0
    for i in set_a:
        c = a.count(i)
        if c > 3:
            pair.append(i)
            pair.append(i)
        elif c > 1:
            pair.append(i)
            
        if len(pair) >= 2:
            ans = pair[0] * pair[1]
            break

    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin, stdout
def readLine_int_list():return list(map(int, stdin.readline().split()))


def main():
    n = int(input())
    a = sorted(readLine_int_list(),reverse=True)
    a.append(-1)
    pair = []
    ans = 0
    t = 1
    
    for i in range(n):
        
        if a[i] == a[i+1]:
            t += 1
        else:
            if t > 1:
                pair.append(a[i])
                if len(pair) == 2:
                    ans = pair[0] * pair[1]
                    break
            t = 1
        
        if t > 3:
            if pair:
                ans = max(a[i-1]*a[i], pair[0]*a[i])
            else:
                ans = a[i]**2
            break

        
        

    print(ans)


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

n = int(input())
cnt = [0] * (n + 1)

for i in range(1, n + 1):
    for j in range(1, n // i + 1):
        cnt[i * j] += 1

ans = 0
for i in range(1, n + 1):
    ans += cnt[i] * i

print(ans)

### FIXED CODE ###

n = int(input())
cnt = [0] * (n + 1)

for i in range(1, n + 1):
    for j in range(1, n // i + 1):
        cnt[i * j] += 1

ans = 0
for i in range(1, n + 1):
    ans += cnt[i] * i

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

import bisect

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for m in range(M):

    B, C = map(int, input().split())
    assi = min(len(A), B)-1

    if A[assi] <= C:
        A[0:assi+1] = [C for c in range(assi+1)]
        A.sort()
    else:
        assi = bisect.bisect_left(A, C)
        A[0:assi] = [C for c in range(assi)]

print(sum(A))


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
p = [(A[i], 1) for i in range(N)]
for m in range(M):
    B, C = map(int, input().split())
    p.append((C, B))

p.sort()
p.reverse()

ans = 0
for v, n in p:
    use = min(N, n)
    ans += use * v
    N -= use
    if N == 0:
        break
print(ans)
### BUGGY CODE ###

n = int(input())

nums = list(map(int, input().split()))
l = [int(x) for x in range(1, n + 1)]

i = 1
bb = 0
ANS = 1
while True:
    if (i == 1) and (nums == l):
        ANS = 0
        break
    if i in nums:
        i_index = nums.index(i)
        bb += len(nums[:i_index])
        nums = nums[i_index + 1:]
        i += 1
    else:
        bb += len(nums)
        break

if ((bb > 0) and bb != n) or ((ANS == 0)):
    print(bb)
else:
    print(-1)

### FIXED CODE ###

n = int(input())

nums = list(map(int, input().split()))
l = [int(x) for x in range(1, n + 1)]

remain = [0]
count = 0

for i in nums:
    if i == remain[-1] + 1:
        remain.append(i)
    else:
        count += 1

if nums == l:
    print(0)
elif (count > 0) and (count != n):
    print(count)
else:
    print(-1)