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

n,m,l=map(int,input().split())
inf=10000000000
g=[[inf for i in range(n)] for j in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    g[a-1][b-1]=c
    g[b-1][a-1]=c
for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])
r=[[inf for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(n):
        if g[i][j]<=l:
            r[i][j]=1
        elif g[i][j]>=inf:
            r[i][j]=inf
for k in range(n):
    for i in range(n):
        for j in range(n):
            r[i][j]=min(r[i][j],r[i][k]+r[k][j])
q=int(input())
for i in range(q):
    s,e=map(int,input().split())
    if r[s-1][e-1]>=inf:
        print(-1)
    else:
        print(r[s-1][e-1]-1)

### FIXED CODE ###

n,m,l=map(int,input().split())
inf=10000000000
g=[[inf for i in range(n)] for j in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    g[a-1][b-1]=c
    g[b-1][a-1]=c
for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])
r=[[inf for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(n):
        if g[i][j]<=l:
            r[i][j]=1
        elif g[i][j]>=inf:
            r[i][j]=inf
for k in range(n):
    for i in range(n):
        for j in range(n):
            r[i][j]=min(r[i][j],r[i][k]+r[k][j])
q=int(input())
for i in range(q):
    s,e=map(int,input().split())
    if r[s-1][e-1]>=inf:
        print(-1)
    else:
        print(r[s-1][e-1]-1)
### BUGGY CODE ###

import math
n = int(input())
l = sorted(list(map(int, input().split())), reverse=True)
ans = 0
temp = 0
base = l[0]

for i in range(1, n):
  combo = math.factorial(base) / math.factorial(l[i]) / math.factorial(base-l[i])
  if combo > temp:
    temp = combo
    ans = l[i]

print(base, ans)

### FIXED CODE ###

n = int(input())
l = sorted(list(map(int, input().split())))
base = l[-1]
ans = 0
if base % 2 == 0:
  half = base //2
else:
  half = base // 2 + 1

diff = float('Inf')
for i in l:
  if abs(half-i) < diff:
    diff = abs(half-i)
    ans = i

print(base, ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import itertools

N, M = map(int, input().split())
a = []
for i in range(N):
    a.append(list(map(int, input().split())))

all_list = [i for i in range(N)]
target_list = list(itertools.combinations(all_list, M))

max_total = 0
for indices in target_list:
    kirei = 0
    oishi = 0
    ninki = 0
    for index in indices:
        tmp = a[index]
        kirei += tmp[0]
        oishi += tmp[1]
        ninki += tmp[2]
    tmp_max = abs(kirei) + abs(oishi) + abs(ninki)
    if max_total < tmp_max:
        max_total = tmp_max

print(max_total)



### FIXED CODE ###

# -*- coding: utf-8 -*-
import itertools
import numpy as np

N, M = map(int, input().split())
input_list = []
for i in range(N):
    input_list.append(list(map(int, input().split())))

converted_list = np.empty((0, 8), int)
for i in input_list:
    tmp_list = []
    for k_i in [1, -1]:
        for o_i in [1, -1]:
            for n_i in [1, -1]:
                tmp_list.append(i[0] * k_i + i[1] * o_i + i[2] * n_i)
    converted_list = np.append(converted_list, np.array([tmp_list]), axis=0)

max_total = 0
for i in range(8):
    tmp_total = 0
    indices = np.argsort(converted_list[:, i])[::-1][:M]
    for ii in indices:
        tmp_total += converted_list[:, i][ii]
    if max_total < tmp_total:
        max_total = tmp_total
print(max_total)
### BUGGY CODE ###

import fractions
import functools

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

def lcm(*numbers):
    return functools.reduce(lcm_base, numbers, 1)

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

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

lcm_A = lcm_list(A)

B = [None]*N
B = [lcm_A//a for a in A]
print(sum(B)%(10**9 + 7))

### FIXED CODE ###

import fractions
import functools
import sys

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

def lcm(*numbers):
    return functools.reduce(lcm_base, numbers, 1)
"""
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
"""
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

lcm_A = functools.reduce(lcm_base, A, 1)
B = [None]*N
B = [lcm_A//a for a in A]
#B[i] = lcm_A//A[i]

print(sum(B)%(10**9+7))
### BUGGY CODE ###

L, R = map(int, input().split())
ans = float("inf")
frag = False
if R - L >= 2018:
    ans = 0
for i in range(L, R):
    for j in range(i+1, R+1):
        ans = min(ans, (i*j)%2019)

print(ans)

### FIXED CODE ###

L, R = map(int, input().split())
if R - L >= 2018:
	print(0)
else:
	ans = 2019
	for i in range(L, R):
		for j in range(i + 1, R + 1):
			ans = min(ans, i * j % 2019)
	print(ans)
### BUGGY CODE ###

import re
s=input()
m=0
for i in range(len(s)//2):
  dst = re.sub(r'01|10', "", s)
  if dst == s:
    break
  m += len(s) - len(dst)
  s=dst
print(m)

### FIXED CODE ###

s=input();print(min(s.count("0"), s.count("1"))*2)
### BUGGY CODE ###

s = input() + "T"
x, y = map(int, input().split())
X = [[], [0]]
d = 0
t = 0
for i in range(len(s)):
    if s[i] == "F":
        t += 1
    else:
        X[d].append(t)
        d = 1-d
        t = 0
def calc(l):
    if len(l) == 0: return [0] 
    post = [l[0]]
    for i in range(1, len(l)):
        if l[i]:
            pre = post
            post = []
            for j in pre:
                post.append(j+l[i])
                post.append(j-l[i])
            # print(pre, post)
    return post

if x in calc(X[0]) and y in calc(X[1]):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = input() + "T"
x, y = map(int, input().split())
X = [[], [0]]
d = 0
t = 0
for i in range(len(s)):
    if s[i] == "F":
        t += 1
    else:
        X[d].append(t)
        d = 1-d
        t = 0
def calc(l):
    if len(l) == 0: return [0] 
    post = [l[0]]
    for i in range(1, len(l)):
        if l[i]:
            pre = sorted(post)
            post = []
            for j in range(len(pre)):
                if j==0 or pre[j] != pre[j-1]:
                    post.append(pre[j]+l[i])
                    post.append(pre[j]-l[i])
            # print(pre, post)
    return post

if x in calc(X[0]) and y in calc(X[1]):
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import numpy as np
INF = 10**15
def solve(n, k, h):
    dp = np.full((n+1, n+1), INF, dtype=int)
    dp[0, 0] = 0
    h = np.array([0] + h, dtype=int)
    for x in range(1, n+1):
        for y in range(n+1):
            t = np.maximum(h[x] - h[:x], 0)
            dp[x, y] = np.min(dp[:x, y-1] + t)
    return np.min(dp[:, n-k])

n, k = map(int, input().split())
h = list(map(int, input().split()))
print(solve(n, k, h))

### FIXED CODE ###

import numpy as np
INF = 10**15
def solve(n, k, h):
    dp = np.full((n+1, n+1), INF, dtype=int)
    dp[0, 0] = 0
    h = np.array([0] + h, dtype=int)
    for i, h_i in enumerate(h[1:], 1):
        t = np.maximum(h_i - h[:i], 0)
        dp[i,1:] = np.min(dp[:i,:-1]+t[:,None], axis=0)
    return np.min(dp[:, n-k])

n, k = map(int, input().split())
h = list(map(int, input().split()))
print(solve(n, k, h))
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline
h, w = [int(x) for x in input().strip().split()]
g = [[x for x in list(input().strip())] for _ in range(h)]

ans = -1
q = set()
for i in range(h):
    for j in range(w):
        if g[i][j] == '#':
            q.add((i, j))
vec = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while q:
    q_ = q
    q = set()
    ans += 1
    while q_:
        i, j = q_.pop()
        for x, y in vec:
            ti, tj = i+x, j+y
            if 0 <= ti < h and 0 <= tj < w:
                if g[ti][tj] == '.' and (ti, tj) not in q:
                    g[ti][tj] = '#'
                    q.add((ti, tj))
print(ans)

### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
h, w = [int(x) for x in input().strip().split()]
g = [[x for x in list(input().strip())] for _ in range(h)]

ans = -1
q = []
for i in range(h):
    for j in range(w):
        if g[i][j] == '#':
            q.append((i, j))
vec = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while q:
    q_ = deque(q)
    q = deque([])
    ans += 1
    while q_:
        i, j = q_.pop()
        for x, y in vec:
            ti, tj = i+x, j+y
            if 0 <= ti < h and 0 <= tj < w:
                if g[ti][tj] == '.':
                    g[ti][tj] = '#'
                    q.append((ti, tj))
print(ans)
### BUGGY CODE ###

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

ans = 1
x = int(p ** (1/n)) +1

while x > 1:
    y = x ** n
    if p % y == 0:
        p //= y
        ans *= x
    else:
        x -= 1

print(ans)

### FIXED CODE ###

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

ans = 1
x = int(p ** (1/n))

while x > 1:
    y = x ** n
    if p % y == 0:
        p //= y
        ans *= x
        if p == 1:
            break
    else:
        x -= 1

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

a, b, k = map(int, input().split())
for i in range(k):
    if a > 0:
        a -= 1
    elif b > 0:
        b -= 1
    else:
        break

print(a, b)

### FIXED CODE ###

a, b, k = map(int, input().split())

if a <= k:
    k -= a
    a = 0
    if b <= k:
        b = 0
        print(a, b)
    else:
        b -= k
        print(a, b)
else:
    a -= k
    print(a, b)
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()
t_sum = 0
for i in range(N):
  for j in range(i+1,N-1):
    num = L[i]+L[j]
    search_list = L[j+1:]
    le = 0
    ri = len(search_list)-1
    mid = le + (ri -le)//2
    while le <= ri:
      mid = le + (ri -le)//2
      if search_list[mid] == num:
        break
      if search_list[mid] < num:
        le = mid+1
      else:
        ri = mid -1
        
    if search_list[mid] < num:
      mid+=1
    t_sum += mid
print(t_sum)

### FIXED CODE ###

import bisect

n = int(input())

l = sorted(list(map(int, input().split())))
ans = 0

for i in range(n):
  for j in range(i+1, n):
    k = bisect.bisect_left(l, l[i]+l[j])
    #if k > j:
    ans += k - j - 1

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

import sys

def is_ok(mid, gen=None, diff=0):
    print(mid, flush=True)
    res = input()
    if res == "Vacant":
        sys.exit()
    if gen is None:
        return res
    if diff % 2 == 0:
        return gen == res
    else:
        return gen != res


def meguru_bisect_kai(ng, ok, gen):
    cnt = 0
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if is_ok(mid, gen, ok - mid):
            ok = mid
        else:
            ng = mid
        cnt += 1
    return ok


n = int(input())
gen = is_ok(n - 1)
meguru_bisect_kai(0, n - 1, gen)

### FIXED CODE ###

n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid
### BUGGY CODE ###

import itertools


L, R = map(int, input().split())
num_list = [i for i in range(L, R + 1)]
l = list(itertools.combinations(num_list, 2))
INF = float('inf')
ans = INF
for i in range(len(l)):
    if ans > (l[i][0] * l[i][1]) % 2019:
        ans = (l[i][0] * l[i][1]) % 2019
print(ans)

### FIXED CODE ###

ans = 2020
L, R = map(int, input().split())
for i in range(L, R + 1):
    for j in range(i + 1, R + 1):
        mod = i * j % 2019
        if mod == 0:
            print(0)
            exit(0)
        ans = min(ans, mod)
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from bisect import bisect_right

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

aN.sort()
# 単体で条件を満たすものは必要確定なので除く
aN2 = aN[:bisect_right(aN, K)]
aN2.reverse()

need = [False] * len(aN2)
for i in range(1 << len(aN2)):
    sm = 0
    for j in range(len(aN2)):
        if 1 & i>>j == 1:
            sm += aN2[j]
        # 複数で条件を満たせば、それに含まれるものは必要
        if sm >= K:
            for k in range(j+1):
                if 1 & i>>k == 1:
                    need[k] = True
            break
print(need.count(False))


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

N, K = MAP()
A = LIST()

def check(omit):
    # 部分和DP
    dp = np.zeros((N+1, K), dtype=np.bool)
    dp[0,0] = 1
    for i in range(N):
        # まとめて遷移
        dp[i+1] |= dp[i]
        if i != omit and A[i] < K:
            dp[i+1,A[i]:] |= dp[i,:K-A[i]]
    # 今回の値A[omit]を足してKに到達できるような部分和があれば、これは必要
    for j in range(max(0, K-A[omit]), K):
        if dp[N,j]:
            return True
    # なければ不要
    return False

A.sort()
print(bisearch_min(-1, N, check))
### BUGGY CODE ###

from fractions import gcd

N, A, B, K = map(int, input().split())
if K == 0:
    print(1)
    exit()
c = gcd(A, B)
if K % c != 0:
    print(0)
    exit()
A //= c; B //= c; K //= c
mod = 998244353

fact = [1] * (N+1)
fact_inv = [1] * (N+1)
for i in range(1, N+1):
    fact[i] = i * fact[i-1] % mod
fact_inv[N] = pow(fact[N], mod-2, mod)
for i in range(1, N+1)[::-1]:
    fact_inv[i-1] = i * fact_inv[i] % mod


ans = 0
for x in range(N+1):
    if (K - A * x) % B != 0:
        continue
    y = (K - A * x) // B
    tmp = 0
    for g in range(max(0, x + y - N), min(x, y, N)+1):
        r = x - g
        b = y - g
        if r < 0 or b < 0:
            break
        tmp = (tmp + fact_inv[r] * fact_inv[b] * fact_inv[g] * fact_inv[N - r - g - b]) % mod
    ans = (ans + tmp) % mod
ans = ans * fact[N] % mod
print(ans)

### FIXED CODE ###

from fractions import gcd

N, A, B, K = map(int, input().split())
if K == 0:
    print(1)
    exit()
c = gcd(A, B)
if K % c != 0:
    print(0)
    exit()
A //= c; B //= c; K //= c
mod = 998244353

fact = [1] * (N+1)
fact_inv = [1] * (N+1)
for i in range(1, N+1):
    fact[i] = i * fact[i-1] % mod
fact_inv[N] = pow(fact[N], mod-2, mod)
for i in range(1, N+1)[::-1]:
    fact_inv[i-1] = i * fact_inv[i] % mod
comb = lambda n, k: fact[n] * fact_inv[k] * fact_inv[n-k] % mod

ans = 0
for x in range(N+1):
    y, r = divmod(K - A * x, B)
    if r != 0:
        continue
    if 0 <= y <= N:
        ans = (ans + comb(N, x) * comb(N, y)) % mod
print(ans)
### BUGGY CODE ###

#解説チラ見
n,m = map(int,input().split())
ans = n
pre = [i for i in range(n)]
for _ in range(m):
  x,y,z = map(lambda x: int(x)-1, input().split())
  while pre[x] != x:
    x = pre[x]
  while pre[y] != y:
    y = pre[y]
  if x != y:
    ans -= 1
    pre[x] = y
print(ans)

### FIXED CODE ###

#解説チラ見
n,m = map(int,input().split())
ans = n
pre = [i for i in range(n)]
for _ in range(m):
  x,y,z = map(lambda x: int(x)-1, input().split())
  X = [x]
  while pre[x] != x:
    x = pre[x]
    X.append(x)
  Y = [y]
  while pre[y] != y:
    y = pre[y]
    Y.append(y)
  if x != y:
    ans -= 1
    for xx in X:
      pre[xx] = y
    for yy in Y:
      pre[yy] = y
    pre[x] = y
print(ans)
### BUGGY CODE ###

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

dp = [0] * (S + 1)
ans = 0
for a in A:
    dp[0] += 1
    for s in range(S + 1)[::-1]:
        if a + s <= S:
            dp[a + s] = (dp[a + s] + dp[s]) % MOD
    ans += dp[S]
    ans %= MOD

print(ans)


### FIXED CODE ###

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

dp = [0] * (S + 1)
ans = 0

for i, a in enumerate(A):
    for s in range(S + 1)[:: -1]:
        if s + a <= S:
            dp[s + a] += dp[s]
    if a <= S:
        dp[a] += (i + 1)
    ans += dp[S]

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

n, a, b = map(int, input().split())
ans = 0
mod = 10**9 + 7
ncr = 1
ans = 0
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
N = n
g1 = [1, 1]
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
for i in range(1, n+1):
  if i == a or i == b:
    continue
  else:
    ans = (ans + cmb(n, i, mod))%mod
print(ans)

### FIXED CODE ###

n, a, b = map(int, input().split())
mod = 10**9 + 7
def comb(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%mod
    for i in range(2,k+1):
        inv[i]=mod-inv[mod%i]*(mod//i)%mod
        ans=ans*(n-k+i)*inv[i]%mod
    return ans
c = comb(n, a)
d = comb(n, b)
answer = pow(2, n, mod) - 1
print((answer-c-d)%mod)
### BUGGY CODE ###

n, m = map(int, input().split())
MOD = 1000000007
ans = 1
if abs(n - m) == 1:
    for i in range(1, min(n, m) + 1):
        ans *= (i ** 2) % MOD
    ans = (ans * max(n, m)) % MOD
elif n == m:
    for i in range(1, min(n, m) + 1):
        ans *= (i ** 2) % MOD
    ans =  (ans * 2) % MOD
else:
    ans = 0
print(ans)


### FIXED CODE ###

from math import factorial
n, m = map(int, input().split())
MOD = 1000000007
if abs(n - m) == 1:
    ans = max(n, m)
elif n == m:
    ans = 2
else:
    ans = 0
ans *= ((factorial(min(n, m)) % MOD)) ** 2
ans %= MOD
print(ans)
### BUGGY CODE ###

import math
k = int(input())
ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            ans = ans +  math.gcd(math.gcd(i,j), l)
print(ans)

### FIXED CODE ###

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

def main():
    N,W=map(int,input().split())
    dp=[0]*(W+1)
    for _ in range(1,N+1):
        w,v=map(int,input().split())
        for i in range(w,W+1)[::-1]:
            can1=dp[i-w]+v
            can2=dp[i]
            dp[i]=max(can1,can2)
    print(max(dp))
main()

### FIXED CODE ###

import numpy as np
N,W=map(int,input().split())
dp=np.zeros(W+1,dtype=int)
for i in range(N):
    w,v=map(int,input().split())
    dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
print(dp[-1])
### BUGGY CODE ###

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

result = 3 * 10 ** 5
for i in range(N):
    W = S[:i]
    E = S[i+1:]
    flip_count = W.count('W') + E.count('E')
    result = min(flip_count, result)
print(result)


### FIXED CODE ###

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

result = 10 ** 6
E = S.count('E')
W = S.count('W')
for i in range(N):
    temp = 0
    if 'E' == S[i]:
        temp = E-1
    else:
        temp = E
    if 'W' == S[i]:
        E += 1
    else:
        E -= 1
    result = min(temp, result)
print(result)
### BUGGY CODE ###

import heapq
import copy

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

ante, post = alist[:n], alist[-n:]
startante = sum(ante)
startpost = sum(post)
post = list(map(lambda x: -x, post))
heapq.heapify(ante)
heapq.heapify(post)

ans = None
for k in range(n+1):
  _ante = copy.deepcopy(ante)
  _post = copy.deepcopy(post)
  antesum = startante
  postsum = startpost
  for a in alist[n: n+k]:
    minante = heapq.heappushpop(_ante, a)
    antesum = antesum + a - minante
  for a in alist[n+k: 2*n]:
    maxpost = heapq.heappushpop(_post, -a)
    postsum = postsum + a + maxpost
  if ans is None:
    ans = antesum - postsum
  elif ans < antesum - postsum:
    ans = antesum - postsum
print(ans)


### FIXED CODE ###

import heapq

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

ante, post = alist[:n], alist[-n:]
antesums = [0 for _ in range(n+1)]
postsums = [0 for _ in range(n+1)]
antesums[0] = sum(ante)
postsums[0] = sum(post)
post = list(map(lambda x: -x, post))
heapq.heapify(ante)
heapq.heapify(post)

for k in range(n):
  minante = heapq.heappushpop(ante, alist[n+k])
  antesums[k+1] = antesums[k] + alist[n+k] - minante
  maxpost = heapq.heappushpop(post, -alist[2*n-k-1])
  postsums[k+1] = postsums[k] + alist[2*n-k-1] + maxpost

ans = -sum(alist)
for k in range(n+1):
  if ans < antesums[k] - postsums[-k-1]:
    ans = antesums[k] - postsums[-k-1]
print(ans)
### BUGGY CODE ###


n = int(raw_input())
stack = []
for i in range(n):
	i = raw_input()
	if "insert" in i:
		try:
		    stack.insert(0, int(i[7:]))
		except:
			pass
	elif "delete " in i:
		try:
		    stack.remove(int(i[7:]))
		except:
			pass
	elif "deleteFirst" in i:
		stack.pop(0)
	elif "deleteLast" in i:
		stack.pop()
if len(stack) > 0:
    print " ".join(map(str, stack))

### FIXED CODE ###

from collections import deque
n = int(raw_input())
stack = deque()
for i in range(n):
	i = raw_input()
	if "insert" in i:
		stack.appendleft(int(i[7:]))
	elif "delete " in i:
		if int(i[7:]) in stack:
		    stack.remove(int(i[7:]))
	elif "deleteFirst" in i:
		stack.popleft()
	elif "deleteLast" in i:
		stack.pop()
print " ".join(map(str, stack))
### BUGGY CODE ###

from functools import cmp_to_key
import heapq
N = int(input())
A = list(map(int,input().split()))
B = [(A[i],i+1) for i in range(0,len(A))]
B.sort()
st = ""
for i in B:
    st = st + " " + str(i[1])
print(st[1:])

### FIXED CODE ###

from functools import cmp_to_key
import heapq
N = int(input())
A = list(map(int,input().split()))
B = [(A[i],i+1) for i in range(0,len(A))]
B.sort()
print(' '.join([str(n[1]) for n in B]))
### BUGGY CODE ###

N = int(input())
A = input()
split = A.split(" ")
count = 0
for i in range(N):
    split[i] = int(split[i])

for i in range(N):
    i -= count
    if i + 1 != split[i]:
        del split[i]
        count += 1

if split == []:
    print(-1)
else:
    print(count)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
count = 0
num = 1

for i in range(N):
    if A[i] == num:
        num += 1
    else:
        count += 1

if count == N:
    print(-1)
else:
    print(count)