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

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

h,w = map(int, input().split())
ch,cw = map(int, input().split())
ch,cw = ch-1, cw-1
dh,dw = map(int, input().split())
dh,dw = dh-1,dw-1
s = [list(map(lambda x: x==".", input())) for i in range(h)]

inf = 2**32-1
count = [[inf]*w for i in range(h)]

from collections import deque
que = deque()
que.append((ch,cw,0))

dxdy = [(0,1),(1,0),(0,-1),(-1,0)]

while que:
    x,y,c = que.pop()
    if count[x][y] <= c:
        continue
    count[x][y] = c
    kabe = False
    for dx,dy in dxdy:
        nx, ny = x+dx, y+dy
        if not (0<=nx<h and 0<=ny<w):
            continue
        if s[nx][ny]:
            que.appendleft((nx,ny,c))
        else:
            kabe = True
    if not kabe:
        continue
    nc = c+1
    for kx in range(-2,3):
        for ky in range(-2,3):
            nx = x+kx
            ny = y+ky
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > nc:
                que.append((nx,ny,nc))

ans = count[dh][dw]
if ans == inf:
    ans = -1
print(ans)



### FIXED CODE ###

h,w = map(int, input().split())
ch,cw = map(int, input().split())
ch,cw = ch-1, cw-1
dh,dw = map(int, input().split())
dh,dw = dh-1,dw-1
s = [list(map(lambda x: x==".", input())) for i in range(h)]

inf = 2**32-1
count = [[inf]*w for i in range(h)]

from collections import deque
que = deque()
que.append((ch,cw,0))

dxdy = [(-1,0),(0,1),(1,0),(0,-1)]
dxdy1 = [(-1,-1),(-1,-2),(-2,-1),(-2,-2)]
dxdy2 = [(-1,1),(-1,2),(-2,1),(-2,2)]
dxdy3 = [(1,1),(1,2),(2,1),(2,2)]
dxdy4 = [(1,-1),(1,-2),(2,-1),(2,-2)]
while que:
    x,y,c = que.popleft()
    if count[x][y] <= c:
        continue
    count[x][y] = c
    state = [False]*4
    for i, (dx,dy) in enumerate(dxdy):
        nx, ny = x+dx, y+dy
        if not (0<=nx<h and 0<=ny<w):
            continue
        if s[nx][ny]:
            que.appendleft((nx,ny,c))
        else:
            state[i] = True
            nx,ny = nx+dx, ny+dy
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > c+1:
                que.append((nx,ny,c+1))

    if state[-1] and state[0]:
        for dx,dy in dxdy1:
            nx, ny = x+dx, y+dy
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > c+1:
                que.append((nx,ny,c+1))

    if state[0] and state[1]:
        for dx,dy in dxdy2:
            nx, ny = x+dx, y+dy
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > c+1:
                que.append((nx,ny,c+1))
    if state[1] and state[2]:
        for dx,dy in dxdy3:
            nx, ny = x+dx, y+dy
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > c+1:
                que.append((nx,ny,c+1))
    if state[2] and state[3]:
        for dx,dy in dxdy4:
            nx, ny = x+dx, y+dy
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > c+1:
                que.append((nx,ny,c+1))

ans = count[dh][dw]
if ans == inf:
    ans = -1
print(ans)
### BUGGY CODE ###

import heapq
N = int(input())
a = list(map(int, input().split()))
m = len(a) // 2

cumsumA = []
prefix = [x for x in a[:N]]
heapq.heapify(prefix)
cumsumA.append(sum(prefix))
for k in range(N, 2*N):
  heapq.heappush(prefix, a[k])
  heapq.heappop(prefix)
  cumsumA.append(sum(prefix))

cumsumB = []
suffix = [-x for x in a[2*N:]]
heapq.heapify(suffix)
cumsumB.append(-sum(suffix))
for k in range(2*N-1, N-1, -1):
  heapq.heappush(suffix, -a[k])
  heapq.heappop(suffix)
  cumsumB.append(-sum(suffix))

res = -float('inf')
for i in range(0, len(cumsumA)):
  res = max(res, cumsumA[i] - cumsumB[len(cumsumA)-i-1])

print(res)
  


### FIXED CODE ###

import heapq
N = int(input())
a = list(map(int, input().split()))
m = len(a) // 2

cumsumA = []
prefix = [x for x in a[:N]]
heapq.heapify(prefix)
cumsumA.append(sum(prefix))
cursum = sum(prefix)
for k in range(N, 2*N):
  heapq.heappush(prefix, a[k])
  ele = heapq.heappop(prefix)
  cursum = cursum + a[k] - ele
  cumsumA.append(cursum)
  # cumsumA.append(sum(prefix))

cumsumB = []
suffix = [-x for x in a[2*N:]]
heapq.heapify(suffix)
cumsumB.append(-sum(suffix))
cursum = -sum(suffix)
for k in range(2*N-1, N-1, -1):
  heapq.heappush(suffix, -a[k])
  ele = heapq.heappop(suffix)
  cursum = cursum + a[k] + ele
  cumsumB.append(cursum)

res = -float('inf')
for i in range(0, len(cumsumA)):
  res = max(res, cumsumA[i] - cumsumB[len(cumsumA)-i-1])

print(res)
### BUGGY CODE ###

#!/usr/bin/env python3

MOD = 10**9
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

N = int(input())
A = list(map(int, input().split()))
dic = {}
for a in A:
    if a in dic: dic[a] += 1
    else: dic[a] = 1

C = {0:0}

for i in range(1, 2*10**5+1):
    C[i] = i*(i-1)//2

ans = []
for i in range(N):
    dic2 = dic.copy()
    dic2[A[i]] -= 1
    a = 0

    for k, v in dic2.items():
        a += C[v]

    ans.append(a)


for a in ans:
    print(a)


### FIXED CODE ###

#!/usr/bin/env python3

MOD = 10**9
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

N = int(input())
A = list(map(int, input().split()))
dic = {}
for a in A:
    if a in dic: dic[a] += 1
    else: dic[a] = 1

C = {0:0}

sum_ni = 0
for i in range(1, N+1):
    C[i] = i*(i-1)//2

D = {}
for k, v in dic.items():
    sum_ni += C[v]


for k, v in dic.items():
    D[k] = sum_ni - C[dic[k]] + C[dic[k]-1]

for i in range(N):
    print(D[A[i]])
### BUGGY CODE ###

def main():
    N = int(input())
    S = [input() for i in range(N)]
    set_S = set(S)
    cnt = 0
    ll = []
    for s in set_S:
        s_num = S.count(s)
        if cnt < s_num:
            cnt = s_num
            ll = [s]
        elif cnt == s_num:
            ll.append(s)
        elif cnt > s_num:
            pass

    lll = sorted(ll)
    for l in lll:
        print(l)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    import sys
    import collections
    input = sys.stdin.readline
    N = int(input())
    S = [input() for i in range(N)]
    c = collections.Counter(S)
    max_num = c.most_common(1)[0][1]
    ss = [cc[0] for cc in c.most_common() if cc[1] == max_num]
    ss.sort()
    for s in ss:
        print(s,end="")

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

R, G, B, N = map(int, input().split())

rgb = []
for r in range(N//R + 1):
    for g in range((N - r*R)//G + 1):
        tmp = N-r*R-g*G
        if tmp >= 0 and tmp%B == 0:
            rgb.append((r,g,tmp//B))

print(len(set(rgb)))

### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(N//R + 1):
    for g in range((N - r*R)//G + 1):
        tmp = N-r*R-g*G
        if tmp%B == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

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

sei=[1]*2
b=1
for i in range(k):
  sei[0]*=a[i]
for i in range(n-k):
  sei[1]=sei[0]/a[i]*a[i+k]

  if sei[0]<sei[1]:
    print("Yes")
  else:
    print("No")
  sei[0]=sei[1]




### FIXED CODE ###

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

for i in range(n-k):

  if  a[i]<a[i+k]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

import sys
from collections import Counter
read = sys.stdin.buffer.read
n, *lst = map(int, read().split())

def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


al = lst[:n]
bl = lst[n:]
a = convert(al)
b = convert(bl)

alal, aa = al + al, a + a
k = 0
klst = []
while k < n:
    i = 0
    while i < n and aa[k + i] == b[i]:
        i += 1
    if i == n:
        klst.append(k)
    k += 1
for i in klst:
    print(i, al[i] ^ bl[0])

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())

A = list(map(int, readline().split()))
B = list(map(int, readline().split()))


def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


C = convert(A)
D = convert(B)


def Z_algorithm(S):
    # 共通接頭辞の長さを返す
    N = len(S)
    arr = [0] * N
    arr[0] = N
    i, j = 1, 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        arr[i] = j
        if not j:
            i += 1
            continue
        k = 1

        while i + k < N and k + arr[k] < j:
            k += 1
        i += k
        j -= k

    return arr


Z = Z_algorithm(D + [-1] + C + C)[N + 1:N + N + 1]

K = [i for i, x in enumerate(Z) if x == N]
X = [A[k] ^ B[0] for k in K]

print('\n'.join('{} {}'.format(k, x) for k, x in zip(K, X)))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = False
b = [False] * 1000010
for i in range(n - 1):
    if a[i] == a[i + 1]:
        for j in range(a[i], 1000010, a[i]):
            b[j] = True

ans = 0
for i in range(n):
    if not b[a[i]]:
        ans += 1
        for j in range(a[i], 1000010, a[i]):
            b[j] = True

print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = False
b = [False] * 1000010
for i in range(n - 1):
    if a[i] == a[i + 1]:
        if b[a[i]]:
            continue
        for j in range(a[i], 1000010, a[i]):
            b[j] = True

ans = 0
for i in range(n):
    if not b[a[i]]:
        ans += 1
        for j in range(a[i], 1000010, a[i]):
            b[j] = True

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

S = input()
i = S.find("ABC")
c = 0
while i >= 0:
    S = "".join([S[:i], "BCA", S[i+3:]])
    i = S.find("ABC")
    c += 1
print(c)


### FIXED CODE ###

S = input()
c = 0
i = 0
ac = 0
while i < len(S):
    if S[i] == "A":
        ac += 1
    elif S[i:i+2] == "BC":
        c += ac
        i += 1
    else:
        ac = 0
    i += 1
print(c)
### BUGGY CODE ###

l,r = map(int,input().split())
ans = l*(l+1)
for i in range(l,r):
    for j in range(i+1,r+1):
        mod = (i*j)%2019
        if mod < ans:
            ans = mod
        if ans == 0:
            break
print(ans)

### FIXED CODE ###


l,r = map(int,input().split())
ans = l*(l+1)
if int(l/2019) < int(r/2019):
    print(0)
else:
    for i in range(l,r):
        for j in range(i+1,r+1):
            mod = (i*j)%2019
            if mod < ans:
              ans = mod
            if ans == 0:
                break
    print(ans)
### BUGGY CODE ###

def get_item(L,i): return L[i] if len(L) > i else -2
def left(i): return i*2 + 1
def right(i): return (i+1)*2
def parent(i): return i//2 if i%2 == 1 else i//2 - 1

def maxHeapify(A,i):
    l = left(i)
    r = right(i)
    largest = i
    if get_item(A,l) > A[largest]: largest = l
    if get_item(A,r) > A[largest]: largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i] 
        maxHeapify(A, largest)


def maxHeapInsert(A,i):
    if i==0: return
    p = parent(i)
    if A[i] > A[p]:
        A[i], A[p] = A[p], A[i] 
        maxHeapInsert(A,p)


def insert(A,k):
    A.append(k)
    maxHeapInsert(A,len(A)-1)


def extract(A):
    max_item, A[0] = A[0], -1
    maxHeapify(A,0)
    for i in range(A.index(-1),len(A)-1):
        A[i], A[i+1] = A[i+1], A[i]
        maxHeapInsert(A,i)
    A.pop()
    return max_item


if __name__=='__main__':
    hp = []
    while True:
        op = input().split() 
        if   op[0] == 'end': break
        if   op[0] == 'insert': insert(hp,int(op[1]))
        else: print(extract(hp))

### FIXED CODE ###

from sys import stdin

def dw_heap(A,i):
    largest = i
    while True:
        l = i*2
        r = l + 1
        if A[l] > A[largest]: largest = l
        if A[r] > A[largest]: largest = r
        if largest == i: return
        A[i], A[largest] = A[largest], A[i] 
        i = largest

def up_heap(A,i):
    p = i//2
    while A[i] > A[p]:
        A[i], A[p] = A[p], A[i] 
        i = p
        p = i//2

if __name__=='__main__':
    hp = [-1]*(4000000)
    hp[0] = 2000000001
    i = 1
    j = -1 
    for op in stdin:
        if op[0] == 'i':# insert
            hp[i] = int(op[7:])
            up_heap(hp,i)
            i += 1
        elif op[1] == 'x':# extract
            hp[j],hp[1],hp[i-1] = hp[1],hp[i-1],-1
            dw_heap(hp,1)
            i -= 1
            j -= 1
        else:# end
            break
    print(*hp[:j:-1],sep='\n')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

for _ in range(m):
    b, c = map(int, input().split())
    for i in range(b):
        a[i] = max(a[i], c)
    a.sort()
print(sum(a))

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict
n, m = map(int, input().split())
a = list(map(int, input().split()))

cards = defaultdict(int)
for num in a:
    cards[num] += 1

for _ in range(m):
    b, c = map(int, input().split())
    cards[c] += b

count = n
ans = 0
for key, val in sorted(cards.items(), key=lambda x: -x[0]):
    if count - val < 0:
        ans += key * count
        break
    else:
        ans += key * val
        count -= val
print(ans)
### BUGGY CODE ###

num, poi, ans = [int(x) for x in input().split()]

list01 = []
while num > 0:
  list01.append(poi)
  num -= 1

i = 1
while i <= ans:
  j = int(input())
  for n, v in enumerate(list01):
    if n != j -1:
      list01[n] -= 1
  i += 1

  
for k in list01:
  if k <= 0:
    print("No")
  else:
    print("Yes")


### FIXED CODE ###

num, poi, ans = [int(x) for x in input().split()]

list01 = [poi for x in range(num)]
list02 = [0 for x in range(num)]

for i in range(ans):
  j = int(input())
  list02[j-1] += 1

for i in range(num):
  list02[i] = list02[i] + list01[i] - ans

for k in list02:
  if k <= 0:
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

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

minimumCostToReach = [0] * 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 ###

K,S = map(int,input().split())
count = 0
for x in range(K + 1):
  for y in range(K + 1):
    for z in range(K + 1):
      total = x + y + z
      if total == S:
        count += 1
print(count)

### FIXED CODE ###

K,S = map(int,input().split())
count = 0
for x in range(K + 1):
  for y in range(K + 1):
    z = S - x - y
    if 0 <= z and z <= K:
      count += 1
print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# モジュールのインポート
import math
import itertools

# 標準入力を取得
N = int(input())

# 求解処理


def has_z(n: int, x: int, y: int) -> bool:
    d = 4 * n - 3 * x**2 - 3 * y**2 - 2 * x * y
    if d < 0:
        return False
    z = (-(x + y) + math.sqrt(d)) / 2
    return (z.is_integer()) and (z >= 1)


for n in range(1, N + 1):
    ans = 0
    max_v = int(math.sqrt(n))
    for x, y in itertools.product(range(1, max_v + 1), repeat=2):
        ans += has_z(n, x, y)
    print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# モジュールのインポート
import math
import itertools

# 標準入力を取得
N = int(input())

# メイン処理


def g(x: int, y: int, z: int) -> int:
    return x**2 + y**2 + z**2 + x*y + y*z + z*x


l = [0 for n in range(N)]
for x, y, z in itertools.product(range(1, int(math.sqrt(N)) + 1), repeat=3):
    v = g(x, y, z)
    if v <= N:
        l[v - 1] += 1

# 結果出力
for ans in l:
    print(ans)
### BUGGY CODE ###

t=list(map(int,input().split()))
s=input()
u=[list(map(int,input().split())) for _ in range(t[1])]
list=[0 for i in range(len(s))]
a=0
for i in range(len(s)-1):
  if s[i]=='A':
    list[i]+=1
  elif s[i]=='C':
    list[i]+=2
for i in range(t[1]):
  a=0
  for j in range(u[i][0]-1,u[i][1]-1):
    if list[j]==1:
      if list[j+1]==2:
        a+=1
  print(a)

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
res=0
dp=[0]*N
a=0
for i in range(1,N):
  if S[i]=='C':
    if S[i-1]=='A':
      res+=1
  dp[i]=res
for _ in range(Q):
  l,r=map(int,input().split())
  if l==1:
    print(dp[r-1])
  else:
    print(dp[r-1]-dp[l-1])
### BUGGY CODE ###

N,K = map(int,input().split())
cc = list(map(int,input().split()))
aa = [1]
flag = True
a = 1
while flag:
  aa.append(cc[a-1])
  a = cc[a-1]
  if aa.count(a) == 2 or len(aa)==K+1:
    flag = False
if len(aa) == K+1:
  print(aa[-1])
else:
  b = aa.index(a)
  m = len(aa)-b-1
  mm = (K-b) % m
  del aa[:b]
  del aa[-1]
  print(aa[mm])

### FIXED CODE ###

N,K = map(int,input().split())
cc = list(map(int,input().split()))
memo = []
aa = ['.']*N
a = 1
while aa[a-1] == '.':
  memo.append(a)
  aa[a-1] = 'v'
  a = cc[a-1]
if len(memo)>K:
  print(memo[K])
else:
  b = memo.index(a)
  m = len(memo)-b
  mm = (K-b) % m
  del memo[:b]
  print(memo[mm])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

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


def solve(t):
    if len(t) <= m + 1:
        return [len(t) - 1]
    for i in reversed(range(1, m + 1)):
        if t[len(t) - 1 - i] == '0':
            cand = solve(t[:-i])
            if len(cand) != 0:
                cand.append(i)
                return cand

    return []


cnt1_continuous = 0
cnt = 0
for i in range(n + 1):
    if s[i] == '1':
        cnt += 1
    else:
        cnt1_continuous = max(cnt1_continuous, cnt)
        cnt = 0

if cnt1_continuous >= m:
    print(-1)
else:
    print(*solve(s))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

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


def solve(t):
    if len(t) <= m + 1:
        return [len(t) - 1]
    for i in reversed(range(1, m + 1)):
        if t[len(t) - 1 - i] == '0':
            cand = solve(t[:-i])
            if len(cand) != 0:
                cand.append(i)
                return cand

    return []


cnt1_continuous = 0
cnt = 0
for i in range(n + 1):
    if s[i] == '1':
        cnt += 1
        if i == n:
            cnt1_continuous = max(cnt1_continuous, cnt)
    else:
        cnt1_continuous = max(cnt1_continuous, cnt)
        cnt = 0

if cnt1_continuous >= m:
    print(-1)
else:
    if m == 1:
        ans = [1] * n
    else:
        ans = solve(s)
    print(*ans)
### BUGGY CODE ###

N = int(input())
l = list(map(int, input().split()))
set_l = set(l)

dictionary = {ll: l.count(ll) for ll in set_l}
ll_dict = {}
for ll in set_l:
  cnt = 0
  for k, v in dictionary.items():
    if k==ll:
      v -=1
    cnt += v*(v-1)/2
  ll_dict[ll] = cnt

for n in range(N):
  print(int(ll_dict[l[n]]))

### FIXED CODE ###

from collections import Counter

N = int(input())
l = list(map(int, input().split()))
set_l = set(l)

dictionary = Counter(l)
ll_dict = {}

cnt = 0
for k, v in dictionary.items():
  cnt += v*(v-1)//2

for n in range(N):
  print(cnt-(dictionary[l[n]]-1))
### BUGGY CODE ###

N, M, Q = map(int, input().split())

range_array = [[0 for _ in range(N)] for _ in range(N)]
ans = [[0 for _ in range(N)] for _ in range(N)]

for _ in range(M):
    l, r = map(int, input().split())
    range_array[l - 1][r - 1] += 1

for i in range(N):
    sum = 0
    for j in range(N):
        sum += range_array[i][j]
        range_array[i][j] = sum
'''
for i in range(N):
    for j in range(i, N):
        sum = 0
        for k in range(i, j + 1):
            sum += range_array[k][j]
        ans[i][j] = sum
'''
for _ in range(Q):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    sum = 0
    for k in range(p, q + 1):
        sum += range_array[k][q]
    print(sum)


### FIXED CODE ###

N, M, Q = map(int, input().split())

range_array = [[0 for _ in range(N)] for _ in range(N)]
ans = [[0 for _ in range(N)] for _ in range(N)]

for _ in range(M):
    l, r = map(int, input().split())
    range_array[l - 1][r - 1] += 1

for i in range(N):
    sum = 0
    for j in range(N):
        sum += range_array[i][j]
        range_array[i][j] = sum
'''
for i in range(N):
    for j in range(i, N):
        sum = 0
        for k in range(i, j + 1):
            sum += range_array[k][j]
        ans[i][j] = sum
'''
for _ in range(Q):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    sum = 0
    for k in range(p, q + 1):
        sum += range_array[k][q]
    print(sum)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]

i = 0
ans = 0
while i < len(a):
    if not a[i] == i + 1:
        del a[i]
        ans += 1
        i -= 1
    i += 1
if len(a) == 0:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]

i = 0
ans = 0
tmp = 1
for i in range(n):
    if a[i] == tmp:
        tmp += 1
    else:
        ans += 1

if ans == n:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

N = int(input())

A = list(map(int,input().split()))
B = list(map(int,input().split()))
L = [A[i] - B[i] for i in range(N)]
ans = 0
if sum(A) < sum(B) :
    ans = -1
else :
    debt = []
    deposit = []
    for i in range(N) :
        if L[i] < 0 :
            debt.append(-L[i])
        elif L[i] > 0 :
            deposit.append(L[i])
        
    debt = sorted(debt)
    deposit = sorted(deposit,reverse=True)
    
    debt_duplicated = debt.copy()
    deposit_duplicated = deposit.copy()
    
    
    for i in range(len(debt)) :
        for j in range(len(deposit)) :
            if debt[i] <= deposit[j] :
                deposit[j] -= debt[i]
                debt[i] = 0
                break
            else :
                debt[i] -= deposit[j]
                deposit[j] = 0
    
    for i in range(len(debt)) :
        if debt[i] != debt_duplicated[i] :
            ans += 1
    for i in range(len(deposit)) :
        if deposit[i] != deposit_duplicated[i] :
            ans += 1

print(ans)
#print(debt)
#print(deposit)



### FIXED CODE ###

N = int(input())

A = list(map(int,input().split()))
B = list(map(int,input().split()))
L = [A[i] - B[i] for i in range(N)]
ans = 0
if sum(A) < sum(B) :
    ans = -1
else :
    debt = []
    deposit = []
    for i in range(N) :
        if L[i] < 0 :
            debt.append(-L[i])
        elif L[i] > 0 :
            deposit.append(L[i])
        
    debt = sorted(debt)
    deposit = sorted(deposit,reverse=True)
    
    debt_duplicated = debt.copy()
    deposit_duplicated = deposit.copy()
    
    deposit_trash = []
    
    #print(debt)
    #print(deposit)
    
    for i in range(len(debt)) :
        
        while True :
            if debt[i] == 0 :
                break
            else :
                if debt[i] <= deposit[0] :
                    deposit[0] -= debt[i]
                    debt[i] = 0
                else :
                    debt[i] -= deposit[0]
                    deposit[0] = 0
                    deposit_trash.append(deposit.pop(0))
        
            
        
#        for j in range(len(deposit)) :
#            if debt[i] <= deposit[j] :
#                deposit[j] -= debt[i]
#                debt[i] = 0
#                break
#            else :
#                debt[i] -= deposit[j]
#                deposit[j] = 0
    deposit = deposit_trash + deposit
    for i in range(len(debt)) :
        if debt[i] != debt_duplicated[i] :
            ans += 1
    for i in range(len(deposit)) :
        if deposit[i] != deposit_duplicated[i] :
            ans += 1

print(ans)
#print(debt)
#print(deposit)