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

S = input()
s = list(S)
for i in range(len(s)):
    s[i] = int(s[i])
p = []
p.append(s[len(s)-1])
for i in range(1,len(s)):
    p.append((p[i-1]+s[len(s)-i-1]*(10**i))%2019)
p.sort()
u = 0
for i in range(len(p)):
    if p[i] == 0:
        u = u+1
    else:
        break
r = 1
q = []
for i in range(len(p)-1):
    if p[i] == p[i+1]:
        r = r+1
    else:
        if r > 1:
            q.append(r)
            r = 1
w = 0
for i in range(len(q)):
    w = w + int(q[i]*(q[i]-1)/2)
print(w+u)

### FIXED CODE ###

S = input()
s = list(S)
for i in range(len(s)):
    s[i] = int(s[i])
p = []
p.append(s[len(s)-1])
for i in range(1,len(s)):
    p.append((p[i-1]+s[len(s)-i-1]*pow(10,i,2019))%2019)
p.sort()
u = 0
for i in range(len(p)):
    if p[i] == 0:
        u = u+1
    else:
        break
r = 1
q = []
for i in range(len(p)-1):
    if p[i] == p[i+1]:
        r = r+1
    else:
        if r > 1:
            q.append(r)
            r = 1
q.append(r)
w = 0
for i in range(len(q)):
    w = w + int(q[i]*(q[i]-1)/2)
print(w+u)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(4100000)
input = sys.stdin.readline


def f(l, c, s, n):
    if not l:
        if s == n:
            return -1
        return s

    if l[0] != c:
        return f(l[1:], c, s + 1, n)
    return f(l[1:], c + 1, s, n)

def main():
    n = int(input()[:-1])
    l = list(map(int, input()[:-1].split(" ")))

    c = 1
    s = 0
    while not l:
        if l[0] != c :
            del l[0]
            s += 1
        else:
            c += 1
        del l[0]


    res = s
    if s == n:
        res = -1

    print(f(l, 1, 0, n))

main()

### FIXED CODE ###

import sys

input = sys.stdin.readline

def main():
    n = int(input()[:-1])
    l = list(map(int, input()[:-1].split(" ")))

    c = 1
    s = 0
    tmp = 0
    while l:
        if tmp >= n:
            break
        if l[tmp] != c :
            s += 1
        else:
            c += 1
        tmp += 1

    res = s
    if s == n:
        res = -1

    print(res)

main()
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		m1 = match_dict[(x,y)]
		m2 = match_dict[(z,w)]
		edge[m1].append(m2)
		parent[m2].append(m1)
finish = [False for i in range(M)]
candidate = [(i, 0) for i in range(M) if len(parent[i]) == 0]
depth = [-1 for i in range(M)]
longest = 0
while len(candidate) > 0:
	x = candidate.pop()
	c,d = x[0], x[1]
	if depth[c] >= d:
		continue
	depth[c] = d
	if d > N*(N-1):
		break
	finish[c] = True
	e = None
	for e in edge[c]:
		x,y = min(c,e), max(c,e)
		candidate.append((e, d+1))
	if e == None:
		longest = max(longest, d)
all_finished = all(finish)
if all_finished:
	print(longest + 1)
else:
	print(-1)

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		m1 = match_dict[(x,y)]
		m2 = match_dict[(z,w)]
		edge[m1].append(m2)
		parent[m2].append(m1)
finish = [False for i in range(M)]
candidate = [i for i in range(M) if len(parent[i]) == 0]
depth = [-1 for i in range(M)]


day = 0
while len(candidate) > 0:
	new_candidate = []
	for c in candidate:
		finish[c] = True
		for e in edge[c]:
			parent[e].remove(c)
			if len(parent[e]) == 0:
				new_candidate.append(e)
		edge[c] = []
	candidate = new_candidate
	day += 1
print(day if all(finish) else -1)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque
n,q=map(int,input().split())
g=[deque([]) for i in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
add=[0]*n
for _ in range(q):
    a,b=map(int,input().split())
    add[a-1]+=b
st=set()  ; ans=[0]*n ; stack=[[0,add[0]]]
while stack:
    s=stack[-1]
    if s[0] not in st : 
        st.add(s[0])
        ans[s[0]]+=s[1]
    if not g[s[0]] : 
        stack.pop()
        continue
    while g[s[0]]:
        if g[s[0]][0] in st:
            g[s[0]].popleft()
        else:
            stack.append([g[s[0]][0],s[1]+add[g[s[0]][0]]])
            break
print(*ans)
        
      

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
n,q=map(int,input().split())
g=[[] for i in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
add=[0]*n
for _ in range(q):
    a,b=map(int,input().split())
    add[a-1]+=b
st=set() ; v=0 ; s=add[0]
ans=[0]*n
def dfs(g,v,s):
    global ans,st
    if v not in st:
        st.add(v)
        ans[v]+=s
    else: return
    for p in g[v]:
        dfs(g,p,s+add[p])
dfs(g,v,s)
print(*ans)
### BUGGY CODE ###

n = int(input())
x = [int(i) for i in input().split()]
x_dict = {i:j for i,j in enumerate(x)}
x.sort()
n_dict = {i:x.index(x_dict[i]) for i in range(n)}
for i in range(n):
    num = n_dict[i]
    if num < n//2:
        print(x[int(n//2)])
    else:
        print(x[int(n//2)-1])

### FIXED CODE ###

n = int(input())
x = [int(i) for i in input().split()]
y = x.copy()
y.sort()
y_e = y[n//2]
y_o = y[n//2 - 1]
for xx in x:
    if xx >= y_e:
        print(y_o)
    else:
        print(y_e)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

N = int(input())
E = [tuple(map(int,input().split())) for _ in range(N-1)]
#print(E)
V = [set() for _ in range(N+1)]
for a,b in E:
  V[a].add(b)
  V[b].add(a)
#print(V)
maxc = 0
for v in V:
  maxc = max(maxc,len(v))
#print(maxc)
CM = set(range(1,maxc+1))
CE = {}
for e in E:
  CE[e] = 0
#print(CE)

def dfs(u,t,c):
  CU = set()
  if t > 0:
    CE[(min(u,t),max(u,t))] = c
    CU.add(c)
  for v in V[u]:
    if CE[(min(u,v),max(u,v))] != 0:
      CU.add(CE[(min(u,v),max(u,v))])
  CC = CM-CU
  for v in V[u]:
    if CE[(min(u,v),max(u,v))] == 0:
      dfs(v,u,CC.pop())

dfs(1,0,1)
print(maxc)
for e in E:
  print(CE[e])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

N = int(input())
E = [tuple(map(int,input().split())) for _ in range(N-1)]
#print(E)
V = [set() for _ in range(N+1)]
for a,b in E:
  V[a].add(b)
  V[b].add(a)
#print(V)
maxc = 0
for v in V:
  maxc = max(maxc,len(v))
#print(maxc)
CE = {}
for e in E:
  CE[e] = 0
#print(CE)

def dfs(u,t,c):
  if t > 0:
    CE[(min(u,t),max(u,t))] = c
  cc = c+1
  if cc > maxc:
    cc = 1
  for v in V[u]:
    if CE[(min(u,v),max(u,v))] == 0:
      dfs(v,u,cc)
      cc += 1
      if cc > maxc:
        cc = 1

dfs(1,0,1)
print(maxc)
for e in E:
  print(CE[e])
### BUGGY CODE ###

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

for _ in range(k):
    tmp = [0 for _ in range(n + 1)]
    for i, num in enumerate(alst):
        min_ind = max(i - num, 0)
        max_ind = min(i + num + 1, n)
        tmp[min_ind] += 1
        tmp[max_ind] -= 1
    next_num = 0
    for i, num in enumerate(tmp[:-1]):
        next_num += num
        alst[i] = next_num
    if tmp[0] == n and tmp[-1] == -n:
        break
print(*alst)

### FIXED CODE ###

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

for _ in range(k):
    tmp = [0 for _ in range(n + 1)]
    for i, num in enumerate(alst):
        min_ind = max(i - num, 0)
        max_ind = min(i + num + 1, n)
        tmp[min_ind] += 1
        tmp[max_ind] -= 1
    next_num = 0
    for i, num in enumerate(tmp[:-1]):
        next_num += num
        alst[i] = next_num
    if tmp[0] == n and tmp[-1] == -n:
        break
print(*alst)
### BUGGY CODE ###

import numpy as np
s = input()
# s = "R"+"RL"*10000+"L"
step = np.max(list(map(len, s.split("RL"))))

n = len(s)
pop = [1]*n

if step%2 == 1:
    step = step+1
else:
    step = step

for t in range(step):
    new_pop = [0]*n
    for i in range(n):
        if s[i] == "R":
            new_pop[i+1] += pop[i]
        else:
            new_pop[i-1] += pop[i]
    pop = new_pop
print(" ".join(map(str, pop)))

### FIXED CODE ###

import numpy as np
s = input()
n = len(s)

pop = [0]*n

lastR = 0
for i in range(n):
    if s[i] == "L":
        if (lastR - i)%2 == 1:
            pop[lastR+1] += 1
        else:
            pop[lastR] += 1
    else:
        lastR = i
            
lastL = n
for i in range(n-1, -1, -1):  
    if s[i] == "R":
        if (lastL - i)%2 == 1:
            pop[lastL-1] += 1
        else:
            pop[lastL] += 1
    else:
        lastL = i
        
print(" ".join(map(str, pop)))
### BUGGY CODE ###

n= int(input())
s = str(input())

r = []
g = []
b = []
for i in range(n):
    if s[i]=="R":
        r.append(i)
    elif(s[i]=="G"):
        g.append(i)
    elif(s[i]=="B"):
        b.append(i)
# print(r)
# print(b)
score = len(r)*len(g)*len(b)
count_ = 0
for i in r:
    for j in g:
        if (i>j)and(2*i-j in b):
            count_ +=1
        if (i>j)and(2*j-i in b):
            count_+=1
        if(j>i)and(2*j-i in b):
            count_ +=1
        if(j>i)and(2*i-j in b):
            count_+=1
        if((i+j)/2 in b):
            count_ +=1
# print(count_)
print(score-count_)

### FIXED CODE ###

n= int(input())
s = str(input())

r=set()
g=set()
b=set()
for i in range(n):
    if s[i]=='R':
        r.add(i)
    if s[i]=='G':
        g.add(i)
    if s[i]=='B':
        b.add(i)
score = len(r)*len(g)*len(b)
for i in r:
    for j in g:
        dist=abs(j-i)
        if (i>j):
            bi = i+dist
            if bi in b:
                score -=1
            bi = j-dist
            if bi in b:
                score -=1
        else:
            bi = j+dist
            if bi in b:
                score-=1
            bi = i-dist
            if bi in b:
                score-=1
        if((i+j)%2==0 and (i+j)/2 in b):
            score-=1
# print(count_)
print(score)
### BUGGY CODE ###

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)

    # divisors.sort()
    return divisors


N = int(input())
A = [int(x) for x in input().split()]
ans = []
score = [0] * N

for i in range(N - 1, -1, -1):
    if score[i] % 2 != A[i]:
        ans.append(i + 1)
        divisors = make_divisors(i + 1)
        for v in divisors:
            score[v - 1] += 1



print(len(ans))
if len(ans) != 0:
    for v in ans:
        print(v, end=" ")

### FIXED CODE ###

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)

    # divisors.sort()
    return divisors


N = int(input())
A = [int(x) for x in input().split()]
ans = []
score = [0] * N

for i in range(N - 1, -1, -1):
    if score[i] % 2 != A[i]:
        ans.append(i + 1)
        divisors = make_divisors(i + 1)
        for v in divisors:
            score[v - 1] += 1



print(len(ans))
if len(ans) != 0:
    for v in ans:
        print(v, end=" ")
### BUGGY CODE ###

from itertools import product


X, Y, Z, K = map(int, input().split())
lst_A = list(map(int, input().split()))
lst_B = list(map(int, input().split()))
lst_C = list(map(int, input().split()))


lst_AB = [a + b for a, b in product(lst_A, lst_B)]
lst_AB.sort(reverse=True)


lst_ABC = [ab + c for ab, c in product(lst_AB[:min(3000, X*Y*Z)], lst_C)]
lst_ABC.sort(reverse=True)


print(*lst_ABC[:K], sep="\n")



### FIXED CODE ###

import sys
from itertools import product


X, Y, Z, K = map(int, input().split())
lst_A = list(map(int, input().split()))
lst_B = list(map(int, input().split()))
lst_C = list(map(int, input().split()))
lst_A.sort(reverse=True)
lst_B.sort(reverse=True)
lst_C.sort(reverse=True)

# lst_A_K = lst_A[:K]
# lst_B_K = lst_B[:K]
lst_C_K = lst_C[:K]


lst_AB = sorted([a+b for a, b in product(lst_A, lst_B)], reverse=True)
lst_AB_K = lst_AB[:K]

lst_ABC = sorted([ab+c for ab, c in product(lst_AB_K, lst_C_K)], reverse=True)
lst_ABC_K = lst_ABC[:K]

print(*lst_ABC_K, sep="\n")
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 998244353


def resolve():
    """ 愚直解 """
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        a = A[i - 1]
        for prev in range(i):
            for j in range(s + 1):
                dp[i][j] += dp[prev][j]
                if a + j > s:
                    continue
                dp[i][a + j] += dp[prev][j]
                dp[i][a + j] %= mod
    print(dp)
    res = 0
    for i in range(1, n + 1):
        res += dp[i][-1]
        res %= mod
    print(res)


def resolve2():
    """ DP + 累積和 """
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    cnt_num = [0] * (s + 1)
    cnt_num[0] = 1
    for i in range(1, n + 1):
        a = A[i - 1]
        for j in range(s + 1):
            dp[i][j] += cnt_num[j]
            if a + j > s:
                continue
            dp[i][a + j] += cnt_num[j]
            dp[i][a + j] %= mod
        for k in range(s + 1):
            cnt_num[k] = cnt_num[k] + dp[i][k]

    res = 0
    for i in range(1, n + 1):
        res += dp[i][-1]
        res %= mod
    print(res)


if __name__ == '__main__':
    n, s = map(int, input().split())
    A = list(map(int, input().split()))
    resolve2()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 998244353


def resolve():
    """ 愚直解 """
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        a = A[i - 1]
        for prev in range(i):
            for j in range(s + 1):
                dp[i][j] += dp[prev][j]
                if a + j > s:
                    continue
                dp[i][a + j] += dp[prev][j]
                dp[i][a + j] %= mod
    print(dp)
    res = 0
    for i in range(1, n + 1):
        res += dp[i][-1]
        res %= mod
    print(res)


def resolve2():
    """ DP + 累積和 """
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    cnt_num = [0] * (s + 1)
    cnt_num[0] = 1
    res = 0
    for i in range(1, n + 1):
        a = A[i - 1]
        for j in range(s + 1):
            dp[i][j] += cnt_num[j]
            dp[i][j] %= mod
            if a + j > s:
                continue
            dp[i][a + j] += cnt_num[j]
            dp[i][a + j] %= mod
        for k in range(s + 1):
            cnt_num[k] = cnt_num[k] + dp[i][k]
            cnt_num[k] %= mod
        res += dp[i][-1]
        res %= mod
    print(res)


if __name__ == '__main__':
    n, s = map(int, input().split())
    A = list(map(int, input().split()))
    resolve2()
### BUGGY CODE ###

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

A.sort()
#print(a)
A = A[::-1]
res = 0
while len(A) >= 2:
    for a in A[1:]:
        if not (A[0] + a & (A[0] + a - 1)):
            res += 1
            A.remove(a)
            break
    A.pop(0)
            
print(res)
    



### FIXED CODE ###

from collections import Counter

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

A.sort(reverse=True)
c = Counter(A)
res = 0
for a in A:
    n = 2 ** a.bit_length() - a
    if n in c.keys():
        if a == n and c[a] > 1:
            c[a] -= 2
            res += 1
        elif a != n and c[a] > 0 and c[n] > 0:
            c[a] -= 1
            c[n] -= 1
            res += 1
    
print(res)
### BUGGY CODE ###

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

mod=10**9+7
ans=0
for i in range(N-1):
    for j in range(i+1,N):
        ans+=A[i]^A[j]
        ans%=mod
print(ans)

### FIXED CODE ###

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

mod=10**9+7
ans=0
cnt=[[0]*2 for _ in range(60)]

for x in A:
    for i in range(60):
        a=x%2
        x//=2
        cnt[i][a]+=1

for p,q in enumerate(cnt):
    i,j=q
    ans+=((i*j)%mod)*pow(2,p,mod)
    ans%=mod
    
print(ans)
### BUGGY CODE ###

import numpy as np

S = input()
MOD = 10 ** 9 + 7

dp = np.zeros(13, dtype=int)
dp[0] = 1

for s in S:
    # 4 == pow(10, -1, 13)
    dp = dp[np.arange(0, 52, 4) % 13]
    if s == '?':
        new_dp = np.zeros(13, dtype=int)
        for i in range(13):
            new_dp[np.arange(i, i + 10) % 13] += dp[i]
            new_dp %= MOD
        dp = new_dp
    else:
        dp = np.roll(dp, int(s))
print(dp[5])


### FIXED CODE ###

import numpy as np
from numba import njit, i8

S = input()
MOD = 10 ** 9 + 7

dp = np.zeros(13, dtype=int)
dp[0] = 1


@njit(cache=True)
def q_mark(dp):
    new_dp = np.zeros(13, dtype=i8)
    for i in range(13):
        new_dp[np.arange(i, i + 10) % 13] += dp[i]
        new_dp %= MOD
    return new_dp


for s in S:
    # 4 == pow(10, -1, 13)
    dp = dp[np.arange(0, 52, 4) % 13]
    if s == '?':
        dp = q_mark(dp)
    else:
        dp = np.roll(dp, int(s))
print(dp[5])
### BUGGY CODE ###

from bisect import bisect_left, bisect_right

N = int(input())
A = sorted([int(x) for x in input().split()])
B = sorted([int(x) for x in input().split()])
C = sorted([int(x) for x in input().split()])

ans = 0
for b in B:
    ans += len(A[:bisect_right(A, b - 1)]) * len(C[bisect_left(C, b + 1):])
print(ans)


### FIXED CODE ###

from bisect import bisect_left, bisect_right

N = int(input())
A = sorted([int(x) for x in input().split()])
B = sorted([int(x) for x in input().split()])
C = sorted([int(x) for x in input().split()])

ans = 0
for b in B:
    ans += bisect_right(A, b - 1) * (N - bisect_left(C, b + 1))
print(ans)
### BUGGY CODE ###

import math

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

total = 0

for i in range(n-m+1):
    p = n - i - 1
    q = m - 1

    c = math.factorial(p) // math.factorial(p-q) // math.factorial(q)

    total -= c * a[i]
    total += c * a[-1-i]

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


### FIXED CODE ###

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
mod = 10**9 + 7

f = [1, 1]
for i in range(2, n):
    f.append((f[i-1] * i) % mod)

total = 0
for i in range(n - k + 1):
    p = n - i - 1
    q = k - 1

    c = f[p] * pow(f[p-q], mod-2, mod) * pow(f[q], mod-2, mod) % mod
    total += c * (a[-1-i] - a[i])
    total = total % mod

print(total)
### BUGGY CODE ###

if __name__ == "__main__":

    N = int(input())

    P = (map(int,input().split()))

    mult = 1
    for i in P:
        mult *= i

    if(mult > 10 ** 18):
        print(-1)
    else:
        print(mult)



### FIXED CODE ###

import sys

if __name__ == "__main__":
 
    N = int(input())
 
    P = list(map(int,input().split()))

    if(0 in P):
        print(0)
    else:
        P.sort()

        mult = 1
        for i in P:
            mult *= i 
            if (mult > 10 ** 18):
                print(-1)
                sys.exit()

        print(mult)
### BUGGY CODE ###

from collections import Counter

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

# bc = [list(map(int,input().split())) for _ in range(q)]

c = Counter(a)

ans = []

for i in range(q):
    bi,ci = list(map(int,input().split()))
    c[ci] = c[bi]+c[ci]
    c[bi] = 0
    csum = 0
    for k,v in c.items():
        csum += k*v
    ans.append(csum)
    
for i in ans:
    print(i)

### FIXED CODE ###

from collections import Counter

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

# bc = [list(map(int,input().split())) for _ in range(q)]

c = Counter(a)

allsum = 0
for k,v in c.items():
    allsum += k*v
    
ans = []

for i in range(q):
    bi,ci = list(map(int,input().split()))
    allsum += ci*c[bi] - bi*c[bi]
    c[ci] = c[ci] + c[bi]
    c[bi] = 0
    ans.append(allsum)
    
for i in ans:
    print(i)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
K = 0
S = 0
T = []
if sum(A) < sum(B):
    print('-1')
else:
    for i in range(N):
        if A[i] < B[i]:
            K += 1
            S = S + B[i] - A[i]
        elif A[i] > B[i]:
            T.append(A[i] - B[i])
        else:
            continue
    while S > 0:
        S -= max(T)
        T.remove(max(T))
        K += 1
    print(K)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
K = 0
S = 0
T = []
if sum(A) < sum(B):
    K = -1
else:
    for i in range(N):
        if A[i] < B[i]:
            K += 1
            S = S + B[i] - A[i]
        elif A[i] > B[i]:
            T.append(A[i] - B[i])
        else:
            continue
T.sort()
L = 0
while S > L:
    L += T.pop()
    K += 1
print(K)
### BUGGY CODE ###

#DAGの最長有向パスをトポロジカルソートで解く
from collections import defaultdict

N,M=map(int,input().split(' '))
se=set()
d=defaultdict(int)
for i in range(M):
    x,y=map(int,input().split(' '))
    se.add(x*(10**5)+y)
n=set(i for i in range(1,N+1))
while N>0:
    m=set([x%10**5 for x in se])
    for i in n-m:
        n.remove(i)
        N-=1
        de=set([x for x in se if x//10**5==i])
        for j in de:
            k=j%10**5
            se.remove(j)
            if d[k]<=d[i]:
                d[k]=d[i]+1
print(max(d.values()))

### FIXED CODE ###

from collections import defaultdict, deque

N, M = map(int, input().split())
es = [[int(x) for x in input().split()] for _ in range(M)]

outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1
length=defaultdict(int)

q = deque(set(i for i in range(1,N+1))-set(ins.keys()))
length=defaultdict(int)
while q:
    v1 = q.popleft()
    for v2 in outs[v1]:
        ins[v2] -= 1
        if length[v2]<=length[v1]:
            length[v2]=length[v1]+1
        if ins[v2] == 0:
            q.append(v2)

print(max(length.values()))
### BUGGY CODE ###




import math
from functools import reduce

def f(*numbers):
    return reduce(math.gcd, numbers)
n=int(input())



def sigma2(frm, to):
    r = 0;
    for i in range(frm, to+1):
        for j in range(frm, to+1):
            for k in range(frm, to+1):
                r+=f(i,j,k)
    return r

print(sigma2(1,n))
# print(sum(sigma2(1,n)+sigma2(1,n)+sigma2(1,n)))


### FIXED CODE ###




import math
from functools import reduce

def f(*numbers):
    return reduce(math.gcd, numbers)
n=int(input())



def sigma2(frm, to):
    r = 0;
    for i in range(frm, to+1):
        for j in range(frm, to+1):
            for k in range(frm, to+1):
                r+=f(i,j,k)
    return r

print(sigma2(1,n))
# print(sum(sigma2(1,n)+sigma2(1,n)+sigma2(1,n)))
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for i in range(q):
    l,r=map(int,input().split())
    print(s[l-1:r].count('AC'))


### FIXED CODE ###

n,q=map(int,input().split())
s=input()
t=[0]*n
a=0
for i in range(n-1):
    if s[i:i+2]=='AC':
        a+=1
    t[i+1]=a
for i in range(q):
    l,r=map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

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


for i in range(N):
    SUM=0
    XOR=0
    for j in range(i,N):
        SUM=SUM+A[j]
        XOR=XOR ^ A[j]

        if SUM==XOR:
            count+=1


print(count)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
count=0
F=0
B=0
SUM=0



while F<N:
    while True:
        SUMtest=SUM+A[B]
        XORtest=SUM^A[B]

        if SUMtest==XORtest:
            if B==N-1:
                for i in range(F,N):
                    count=count+(N-i)
                F=N
                break
                
            else:
                B+=1
                SUM=SUMtest

        else:
            count=count+(B-F)
            SUM=SUM-A[F]
            F+=1
            break


print(count)