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

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

dic = {}
for num in a:
    if num not in dic.keys():
        dic[num] = 0
    dic[num] += 1

dic = sorted(dic.items(), key=lambda x:x[1])

ans = 0

for i in range(len(dic)- k):
    ans += dic[i][1]

print(ans)

### FIXED CODE ###

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

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

b.sort(reverse=True)

ans = 0

for i in range(k):
    ans +=b[i] 

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

import sys

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    N = II()
    P = LI()
    ans = 0

    for i in range(N):
        for j in range(0,i+1):
            if P[j]<P[i]:
                break
            elif j == i:
                ans += 1

    
    print(ans)

if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    N = II()
    P = LI()
    ans = 0
    min = N+1

    for i in range(N):
        if P[i]<min:
            ans += 1
            min = P[i]

    print(ans)

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

a, b, k = map(int, input().split())
for i in range(a, b + 1):
    if i <= a + k - 1 or b - k + 1 <= i:
        print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())
l = list()
for i in range(a, a + k):
    if i <= b:
        l.append(i)
for i in range(b - k + 1, b + 1):
    if i >= a:
        l.append(i)
l = sorted(list(set(l)))
for i in range(len(l)):
    print(l[i])
### BUGGY CODE ###

from itertools import product

N = int(input())

for h, n in product(range(1, 3501), range(1, 3501)):
    if ((4 * h * n) - (N * n) - (N * h)) > 0:
        if (N * h * n) % ((4 * h * n) - (N * n) - (N * h)) == 0:
            w = (N * h * n) // ((4 * h * n) - (N * n) - (N * h))
            ans = [w, h, n]
            print(*ans)
            break

### FIXED CODE ###

N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        if ((4 * h * n) - (N * n) - (N * h)) > 0:
            if (N * h * n) % ((4 * h * n) - (N * n) - (N * h)) == 0:
                print(h, n, (N * h * n) // ((4 * h * n) - (N * n) - (N * h)))
                exit()
### BUGGY CODE ###

N =int(input())
H = [int(x) for x in input().split()]
memo = 0
for i in range(N):
    if i==N-1:
        break
    elif H[i]-min(H[i+1:])>=2:
        memo+=1
if memo>=1:
    print('No')
else:
    print('Yes')  

### FIXED CODE ###

N =int(input())
H = [int(x) for x in input().split()]
h=0
l=0
memo = 0
for i in range(N):
    if H[i]>=h:
        h=H[i]
    elif H[i]<h and H[i]>=l:
        l=H[i]
    else:
        memo+=1
for i in range(N):
    if i==N-1:
        break
    elif H[i]-H[i+1]>=2:
        memo+=1

if memo>=1:
    print('No')
else:
    print('Yes')
### BUGGY CODE ###

import itertools

N, M, R = map(int, input().split())
r = [a-1 for a in list(map(int, input().split()))]
d = [[float('inf')]*N for _ in range(N)]

for _ in range(M):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
    
for i in range(N):
    d[i][i] = 0
    
for k in range(N):
    for i in range(N):
        for j in range(N):
            dd = d[i][k] + d[k][j]
            if dd < d[i][j]:
                d[i][j] = dd

ans = float("inf")

for perm in itertools.permutations(r):
    a = 0
    for i in range(len(perm)-1):
        a += d[perm[i]][perm[i+1]]
    ans = min(a, ans)
    
print(ans)

### FIXED CODE ###

import itertools

def main() :
    N, M, R = map(int, input().split())
    r = [a-1 for a in list(map(int, input().split()))]
    d = [[float('inf')]*N for _ in range(N)]

    for _ in range(M):
        a, b, c = map(int, input().split())
        d[a-1][b-1] = c
        d[b-1][a-1] = c

    for i in range(N):
        d[i][i] = 0

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dd = d[i][k] + d[k][j]
                if dd < d[i][j]:
                    d[i][j] = dd

    ans = float("inf")

    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += d[perm[i]][perm[i+1]]
        ans = min(a, ans)

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

import math

K = int(input())

sum = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for l in range(1,K+1):
            sum += math.gcd(math.gcd(i,j),l)

print(sum)


### FIXED CODE ###

import math

K = int(input())

sum = 0
# for i in range(1,K+1):
#     for j in range(1,K+1):
#         for l in range(1,K+1):
#             sum += math.gcd(math.gcd(i,j),l)
for i in range(1,K+1):
    for j in range(1,K+1):
        if math.gcd(i,j)==1:
            sum += K
        else:
            for l in range(1,K+1):
                sum += math.gcd(math.gcd(i,j),l)


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

import sys
n,k=map(int,input().split())
a=list(map(int,input().split()))
I=10**9+7

if sum(a)<k:
    print(0)
    sys.exit()

dp=[[float("inf")]*(k+1) for _ in range(n+1)]
for p in range(k+1):
    dp[0][p]=0
    if a[0]<p:
        dp[1][p]=0
    else:
        dp[1][p]=1
for i in range(1,n):
    s=[0]*(k+2)
    for j in range(k+1):
        s[j+1]=s[j]+dp[i][j]
        dp[i+1][j]=s[j+1]-s[max(0,j-a[(i+1)-1])]

print(dp[n][k]%I)

### FIXED CODE ###

import sys
n,k=map(int,input().split())
a=list(map(int,input().split()))
I=10**9+7

if sum(a)<k:
    print(0)
    sys.exit()

dp=[[float("inf")]*(k+1) for _ in range(n+1)]
for p in range(k+1):
    dp[0][p]=0
    if a[0]<p:
        dp[1][p]=0
    else:
        dp[1][p]=1
for i in range(1,n):
    s=[0]*(k+2)
    for j in range(k+1):
        s[j+1]=s[j]+dp[i][j]%I
        dp[i+1][j]=s[j+1]-s[max(0,j-a[(i+1)-1])]

print(dp[n][k]%I)
### BUGGY CODE ###

import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
x=10**9+7
if len(set(a))!=len(a) or len(set(b))!=len(b):
  print(0)
else:
  a.sort()
  b.sort()
  L=[]
  for i in range(n):
    l=[]
    for j in range(m):
      l.append(0)
    L.append(l)
  if m*n in a and m*n in b:
    L[a.index(m*n)][b.index(m*n)]=m*n
    ct=1
    for k in range(m*n-1,0,-1):
      if k in a and k in b:
        L[a.index(k)][b.index(k)]=k
        ct*=1
      elif k in a or k in b:
        if k in a:
          ct*=(m-bisect.bisect_left(b,k))
        if k in b:
          ct*=(n-bisect.bisect_left(a,k))
      else:
        ct*=((m-bisect.bisect_left(b,k))*(n-bisect.bisect_left(a,k))-m*n+k)
      if ct==0:
        break
      ct=ct%x
    print(ct)
  else:
    print(0)

### FIXED CODE ###

import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
x=10**9+7
if len(set(a))!=len(a) or len(set(b))!=len(b):
  print(0)
else:
  a.sort()
  b.sort()
  L=[]
  for i in range(n):
    l=[]
    for j in range(m):
      l.append(0)
    L.append(l)
  if m*n in a and m*n in b:
    L[a.index(m*n)][b.index(m*n)]=m*n
    ct=1
    ctn=1
    ctm=1
    A=set(a)
    B=set(b)
    for k in range(m*n-1,0,-1):
      if k in A and k in B:
        L[bisect.bisect_left(a,k)][bisect.bisect_left(b,k)]=k
        ct*=1
        ctn+=1
        ctm+=1
      elif k in A:
          ct*=ctm
          ctn+=1
      elif k in B:
          ct*=ctn
          ctm+=1
      else:
        ct*=(ctm*ctn-m*n+k)
      if ct==0:
        break
      ct=ct%x
    print(ct)
  else:
    print(0)
### BUGGY CODE ###

S=input()
l=len(S)
t=0
p=0
for i in range(l-1,2,-1):

    p=0
    for j in range(i+1):
        p=(p+int(S[i-j])*(10**j))%2019

        if p==0:

            t+=1

print(t)

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

from queue import Queue

INF=float('inf')

n=int(input())
g=[[] for _ in range(n)]
for _ in range(n-1):
    u,v,w=map(int,input().split())
    g[u-1].append((v-1,w))
    g[v-1].append((u-1,w))

q,k=map(int,input().split())
ds=[INF]*n
que=Queue()
que.put((k-1,0))
while not que.empty():
    u,d=que.get()
    if ds[u] != INF:
        continue
    ds[u]=d
    for v,w in g[u]:
        que.put((v,d+w))

for _ in range(q):
    u,v=map(int,input().split())
    print(ds[u-1]+ds[v-1])


### FIXED CODE ###

from queue import Queue

INF=float('inf')

n=int(input())
g=[[] for _ in range(n)]
for _ in range(n-1):
    u,v,w=map(int,input().split())
    g[u-1].append((v-1,w))
    g[v-1].append((u-1,w))

q,k=map(int,input().split())
ds=[INF]*n
ds[k-1]=0
que=Queue()
que.put((k-1,0))
while not que.empty():
    u,d=que.get()
    for v,w in g[u]:
        if ds[v]==INF:
            ds[v]=d+w
            que.put((v,d+w))

for _ in range(q):
    u,v=map(int,input().split())
    print(ds[u-1]+ds[v-1])
### BUGGY CODE ###

N,K=map(int,input().split())
l=list(map(int,input().split()))
from itertools import combinations

ans=0
for c in combinations(range(N),K):
  ans=max(ans,sum([l[i] for i in c]))
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
l=sorted(list(map(int,input().split())),reverse=True)

print(sum(l[:K]))
### BUGGY CODE ###

'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,m = map(int,ipt().split())
    s = [int(i) for i in ipt().split()]
    t = [int(i) for i in ipt().split()]
    ans = 0

    dp = [[1]*(m+1) for i in range(n+1)]
    for i,si in enumerate(s):
        for j,tj in enumerate(t):
            if si == tj:
                dp[i+1][j+1] = dp[i][j+1]+dp[i+1][j]
            else:
                dp[i+1][j+1] = dp[i][j+1]+dp[i+1][j]-dp[i][j]

    print(dp[n][m]%mod)

    return None

if __name__ == '__main__':
    main()


### FIXED CODE ###

'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,m = map(int,ipt().split())
    s = [int(i) for i in ipt().split()]
    t = [int(i) for i in ipt().split()]
    ans = 0

    dp = [[1]*(m+1) for i in range(n+1)]
    for i,si in enumerate(s):
        for j,tj in enumerate(t):
            if si == tj:
                dp[i+1][j+1] = dp[i][j+1]+dp[i+1][j]

            else:
                dp[i+1][j+1] = dp[i][j+1]+dp[i+1][j]-dp[i][j]
            dp[i+1][j+1] %= mod

    print(dp[n][m])

    return None

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

from collections import Counter

num = int(input())

# tmp = []
# for n in range(num):
#   tmp.append(input())

tmp = [input() for i in range(num)]

count = Counter(tmp)

tmp2 = []
for k, v in count.items():
  if count.most_common(1)[0][1] == v:
    tmp2.append(k)

for t in sorted(tmp2):
  print(t)
  

### FIXED CODE ###

def main():
  num = int(input())

  tmp = [input() for i in range(num)]

  tmp2 = {}
  for t in tmp:
    if len(tmp2) == 0:
      tmp2[t] = 1
    else:
      if t in tmp2:
        tmp2[t] += 1
      else:
        tmp2[t] = 1

  _tmp2 = sorted(tmp2.items(), key=lambda x:x[1])
  tmp3 = sorted(tmp2.items())
  for t in tmp3:
    if _tmp2[-1][1] == t[1]:
      print(t[0])

main()
### BUGGY CODE ###

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

S1 = S[:N]
S2 = S[N:]
S2 = S2[::-1]
rb1 = {}
rb2 = {}
for i in range(2 ** N):
    flag = bin(i)[2:].zfill(N)
    r = ''
    b = ''
    for j in range(N):
        if flag[j] == '0':
            r += S1[j]
        else:
            b = S1[j] + b
    key = r + '&' + b
    if key in rb1.keys():
        rb1[key] += 1
    else:
        rb1[key] = 1

for i in range(2 ** N):
    flag = bin(i)[2:].zfill(N)
    r = ''
    b = ''
    for j in range(N):
        if flag[j] == '0':
            r += S2[j]
        else:
            b = S2[j] + b
    key = r + '&' + b
    if key in rb2.keys():
        rb2[key] += 1
    else:
        rb2[key] = 1

ans = 0
for key in rb1.keys():
    if key in rb2.keys():
       ans += rb1[key] * rb2[key]

print(ans)


### FIXED CODE ###

from collections import Counter

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

S1 = S[:N]
S2 = S[N:]
S2 = S2[::-1]
rb1 = Counter()
rb2 = Counter()
for i in range(2 ** N):
    flag = bin(i)[2:].zfill(N)
    r1 = ''
    b1 = ''
    r2 = ''
    b2 = ''
    for j in range(N):
        if flag[j] == '0':
            r1 += S1[j]
            r2 += S2[j]
        else:
            b1 = S1[j] + b1
            b2 = S2[j] + b2
    key1 = r1 + '&' + b1
    key2  =r2 + '&' + b2
    rb1[key1] += 1
    rb2[key2] += 1

ans = 0
for key in rb1.keys():
    ans += rb1[key] * rb2[key]

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

def solve(p,q):
  return sorted(i+j for i in p for j in q)[-k:]
x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
for i in solve(solve(a,b),c)[::-1]:
  print(i)

### FIXED CODE ###

I=lambda:list(map(int,input().split()));x,y,z,k=I();s=lambda a,b:sorted(i+j for i in a for j in b)[:-k-1:-1];print(*s(s(I(),I()),I()))
### BUGGY CODE ###

N,M = map(int,input().split())
d=[0]*M
res = []
for i in range(M):
    P,Y = map(int,input().split())
    res.append((P,Y,i))
c=1
for i in sorted(res):
    x = str(i[0])
    tmp = (6-len(x))*'0'+x+(6-len(str(c)))*'0'+str(c)
    if(tmp in d):
        c+=1
    else:
        c = 1
    d[i[2]] = (6-len(x))*'0'+x+(6-len(str(c)))*'0'+str(c)

for i in d:
    print(i)

### FIXED CODE ###

N,M = map(int,input().split())
d=[0]*M
res = []
for i in range(M):
    P,Y = map(int,input().split())
    res.append((P,Y,i))
c=0
res.sort()
t = str(res[0][0])
for i in res:
    x = str(i[0])
    tmp = (6-len(x))*'0'+x+(6-len(str(c)))*'0'+str(c)
    if x == t:
        c+=1
    else:
        c=1
        t = x
    d[i[2]] = (6-len(x))*'0'+x+(6-len(str(c)))*'0'+str(c)

for i in d:
    print(i)
### BUGGY CODE ###

n = input()
n = int(n)

li = [int(input()) for i in range(n)]
m = max(li)
for j in range(n):
  if m < li[j]:
    print(m)
  else:
    buf=li.pop(j)
    print(max(li))
    li.insert(j,buf)

### FIXED CODE ###

n = input()
n = int(n)

li = [int(input()) for i in range(n)]
m = max(li)
m2 = sorted(li)[-2]

for j in range(n):
  if m == li[j]:
    print(m2)
  else:
    print(m)
### BUGGY CODE ###

n=int(input())
alis=sorted(list(map(int,input().split())))
p=alis[0]
if p==0:
  print(0)
  exit()
for i in range(1,n):
  p*=alis[i]
  
if len(list(str(p)))>18:
  sa=list(map(int,list(str(p))))
    
  if sum(sa)!=1:
    print(-1)
    exit()
print(p)

### FIXED CODE ###

n=int(input())
alis=sorted(list(map(int,input().split())))
p=alis[0]
if p==0:
  print(0)
  exit()
bre=False
for i in range(1,n):
  p*=alis[i]
  
  
  if len(list(str(p)))>18:
    bre=True
    break


if bre:
  sa=list(map(int,list(str(p))))
  if sum(sa)!=1:print(-1)
  else:print(p)
else:print(p)
### BUGGY CODE ###

def m():
    n, m = map(int, input().split())
    bridge = [1 for _ in range(n)]
    g = []
    for _ in range(m):
        a, b = map(int, input().split())
        g.append((a, b))
    g.sort(key=lambda x: x[1])
    cnt = 0
    for e in g:
        if bridge[e[0]:e[1]].count(0):
            continue
        bridge[e[1]-1] = 0
        cnt += 1
    return cnt

print(m())

### FIXED CODE ###

def m():
    n, m = map(int, input().split())
    bridge = [1 for _ in range(n)]
    g = []
    for _ in range(m):
        a, b = map(int, input().split())
        g.append((a, b))
    g.sort(key=lambda x: x[1])
    cnt = 0
    for e in g:
        f = 0
        for j in range(e[1]-1, e[0]-1, -1):
            if bridge[j] == 0:
                f = 1
                break
        if f:
            continue
        # if bridge[e[0]:e[1]].count(0):
        #     continue
        bridge[e[1]-1] = 0
        cnt += 1
    return cnt

print(m())
### BUGGY CODE ###


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

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

ans = []
for i in A:
    ans.append(i)
    ans.reverse()

print(*ans)

### FIXED CODE ###


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

from collections import deque

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

if N == 1:
    print(A[0])
    exit()

d = deque()
if N % 2 == 0:
    for i in range(N):
        if i%2 == 1:
            d.appendleft(A[i])
        else:
            d.append(A[i])
else:
    for i in range(N):
        if i%2 == 0:
            d.appendleft(A[i])
        else:
            d.append(A[i])

print(*d)
### BUGGY CODE ###

def resolve():
    # 整数 1 つ
    n = int(input())
    # 整数複数個
    # a, b = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    A = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    A = sorted(A)

    cntmax = 0
    for x in range(min(A), max(A)+1):
        cnt = 0
        for a in A:
            if x-1 <= a and a <= x+1:
                cnt += 1
            elif a < x-1:
                continue
            else:
                break
                
        if cntmax < cnt:
            cntmax = cnt

    print(cntmax)


resolve()

### FIXED CODE ###

def resolve():
    # 整数 1 つ
    n = int(input())
    # 整数複数個
    # a, b = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    A = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    A = sorted(A)

    Cnt = [0] * 100002
    for a in A:
        Cnt[a] += 1
        Cnt[a+1] += 1
        Cnt[a+2] += 1

    print(max(Cnt))
resolve()
### BUGGY CODE ###

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

tmp = 1
for num in A:
    tmp *= num
if tmp <= 1e18:
    print(tmp)
else:
    print(-1)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
tmp = 1
for num in A:
    tmp *= num
    if tmp > 1e18:
      break
  
if tmp <= 1e18:
    print(tmp)
elif 0 in A:
    print(0)
else:
    print(-1)
### BUGGY CODE ###

import sys


def test():
    A, B, C, K = map(int, input().split())
    ans = 0
    for _ in range(K):
        if A > 0:
            ans += 1
            A -= 1
        elif B > 0:
            B -= 1
        elif C > 0:
            ans -= 1
            C -= 1
        else:
            break
    print(ans)


if __name__ == "__main__":
    test()


### FIXED CODE ###

import sys


def test():
    A, B, C, K = map(int, input().split())
    ans = 0
    if A > 0 and (K - A) > 0:
        ans += A
        K -= A
    elif A > 0 and (K - A) <= 0:
        ans += K
        print(ans)
        sys.exit()

    if B > 0 and (K - B) > 0:
        K -= B
    elif B > 0 and (K - B) <= 0:
        print(ans)
        sys.exit()

    ans -= K
    print(ans)


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

n = int(input())
s = input()
list = []
ans = n

for i in range(n):
    list.append(s[i])

for j in range(n):
    L = list[:j]
    R = list[j+1:]
    turn = L.count("W") + R.count("E")
    if turn < ans:
        ans = turn

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
list = []
E = s.count("E")
L = 0
check = 0 # 直前がWだったかの記憶装置

for i in s:
    if i == "E":
        E -= 1
        if check == 0:
            list.append(E+L) # E+Lが答えの候補
        elif check == 1:
            check = 0
            L += 1
            list.append(E+L)
    elif i == "W":
        if check == 0: # 一つ前がEのとき
            check = 1
            list.append(E+L)
        elif check == 1: # 一つ前がWのとき
            L += 1
            list.append(E+L)

print(min(list))
### BUGGY CODE ###

from collections import deque
n = int(input())
edges = {}
lst = [[]for i in range(n)]
vert = [[]for i in range(n)]
ans = [0 for i in range(n-1)]
for i in range(n-1):
    a,b = map(int,input().split())
    lst[a-1].append(b)
    lst[b-1].append(a)
    if a > b:
        a,b = b,a
    edges[(a,b)] = i
q = deque([1])
while q:
    x = q.popleft()
    q.extend(lst[x-1])
    for i in lst[x-1]:
        lst[x-1].remove(i)
        lst[i-1].remove(x)
        a = min(x,i)
        b = max(x,i)
        for j in range(1,n):
            if not (j in vert[x-1] or j in vert[i-1]):
                vert[x-1].append(j)
                vert[i-1].append(j)
                ans[edges[(a,b)]] = j
                break
print(max(ans))
for i in range(len(ans)):
    print(ans[i])


### FIXED CODE ###

n = int(input())
graph = [[] for _ in range(n+1)]
for i in range(1,n):
    a,b = map(int,input().split())
    graph[a].append((i,b))
    graph[b].append((i,a))
colors = [0 for _ in range(n)]
parents = [0]*(n+1)
stack = [(1,0)]
while stack:
    x,c = stack.pop()
    color = 1
    for i,y in graph[x]:
        if parents[x] == y:
            continue
        else:
            parents[y] = x
            if color == c:
                color += 1
            colors[i] = color
            stack.append((y,color))
            color += 1
print(max(colors))
for i in range(1,n):
    print(colors[i])
### BUGGY CODE ###

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

mod = 10 ** 9 + 7

combi = list(itertools.combinations(range(N), 2))

S = 0
for x in combi:
    S += A[x[0]] * A[x[1]]
print(S % mod)


### FIXED CODE ###

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

mod = 10 ** 9 + 7

sumA = sum(A)
S = 0

for x in range(N):
    sumA -= A[x]
    S = (S + A[x] * (sumA)) % mod

print(S)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mi = min(a)
ma = max(a)
c = 0
for i in range(1, n-2*mi+1):
    st = max(i+a[i-1], i+2*mi)
    for j in range(st, min(n+1, st+2*ma)):
        if j-i == a[i-1]+a[j-1]:
            c += 1
            
print(c)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
l = {}
r = {}
for i in range(n):
    if i+1+a[i] in l:
        l[i+1+a[i]] += 1
    else:
        l[i+1+a[i]] = 1
        
    if i+1-a[i] in r:
        r[i+1-a[i]] += 1
    else:
        r[i+1-a[i]] = 1

c = 0
for i in range(2, n):
    if i in l and i in r:
        c += l[i]*r[i]
print(c)
### BUGGY CODE ###

a,b,c=map(int,input().split())
ans=0
for i in range(a,b+1):
    if i%c==0:
        ans+=1
print(ans)

### FIXED CODE ###

a,b,c=map(int,input().split())
n=a//c
m=b//c
o=0
if a%c==0:
    o=1
print(m-n+o)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    md = 10 ** 9 + 7
    n, k = map(int, input().split())
    aa = list(map(int, input().split()))
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    dpi = dp[0]
    for i, a in enumerate(aa):
        dpi1 = dp[i + 1]
        s = 0
        for j in range(k + 1):
            s += dpi[j]
            if j - a - 1 >= 0: s -= dpi[j - a - 1]
            s %= md
            dpi1[j] = s
        dpi = dpi1
    # p2D(dp)
    print(dp[n][k])

main()


### FIXED CODE ###

def f(n, k, a_s):
    md = 10 ** 9 + 7
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in a_s[:-1]:
        ndp = [0] * (k + 1)
        ndp[0] = s = dp[0] % md
        for j in range(1, a + 1):
            ndp[j] = s = (s + dp[j]) % md
        for j in range(a + 1, k + 1):
            ndp[j] = s = (s + dp[j] - dp[j - a - 1]) % md
        dp = ndp
    return sum(dp[k - a_s[-1]:]) % md


n, k = map(int, input().split())
a_s = list(map(int, input().split()))
print(f(n, k, a_s))