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

N=int(input())
f=0
fnew=0
A=list(map(int,input().split()))
def flag(n1,n2,f):
 if n1>n2:
  return -1
 elif n1<n2:
  return 1
 else:
  return f
cnt=0
l=[]
i=0
while i<N:
 l.append(A[i])
 if (l[0]+l[len(l)-1])!=(max(l)+min(l)):
  cnt=cnt+1
  l=[]
  i=i-1
 i=i+1
print(cnt+1)

### FIXED CODE ###

N=int(input())
f=0
fnew=0
A=list(map(int,input().split()))
cnt=0
i=0
l=0
r=0
downflag=0
upflag=0
ma=A[i]
mi=A[i]
while i<N:
 if ma>A[i]:
  downflag=1
 elif ma<A[i]:
  upflag=1
 if (upflag==1)and(A[i]>ma):
  ma=A[i]
 if (downflag==1)and(mi>A[i]):
  mi=A[i]
 if (ma+mi)!=(A[l]+A[i]):
  ma=A[i]
  mi=ma
  cnt=cnt+1
  l=i
  i=i-1
  upflag=0
  downflag=0
 i=i+1
print(cnt+1)
### BUGGY CODE ###

n = input()
li = list(map(int, input().split()))
a = 1
if 0 in li:
    print(0)
    quit()
else:
    for x in li:
        a *= x
    if a > 10**18:
        print(-1)
        quit()
    else:
        print(a)

### FIXED CODE ###

n = int(input())
ls = list(map(int, input().split()))
res = 1
if 0 in ls:
    print(0)
    quit()
for x in ls:
    res *= x
    if res > 10**18:
        print(-1)
        quit()
print(res)
### BUGGY CODE ###

import sys
import math
from collections import deque
import copy
from decimal import *

N = int(input())
p = list(map(float, input().split()))
for i in range(N):
    p[i] = Decimal(str(p[i]))
if N == 1:
    print(p[0])
    sys.exit()
dp = [[Decimal("0") for _ in range(N + 10)] for _ in range(N + 10)]
dp[2][0] = (Decimal("1") - p[0]) * (Decimal("1") - p[1])
dp[2][2] = p[0] * p[1]
dp[2][1] = Decimal("1") - dp[2][0] - dp[2][2]
for i in range(3, N + 1):
    dp[i][0] = dp[i - 1][0] * p[i - 1]
for i in range(3, N + 1):
    for l in range(1, N + 1):
        dp[i][l] = dp[i - 1][l] * (Decimal("1") - p[i - 1]) + dp[i - 1][l - 1] * p[i - 1]
ans = Decimal("0")
for i in range(N // 2 + 1, N + 1):
    ans += dp[N][i]
print(ans)


### FIXED CODE ###

import sys
import math
from collections import deque
import copy

N = int(input())
p = list(map(float, input().split()))
if N == 1:
    print(p[0])
    sys.exit()
dp = [[0 for _ in range(N + 10)] for _ in range(N + 10)]
dp[2][0] = (1.0 - p[0]) * (1.0 - p[1])
dp[2][2] = p[0] * p[1]
dp[2][1] = 1.0 - dp[2][0] - dp[2][2]
for i in range(2, N):
    for l in range(0, N + 1):
        dp[i + 1][l + 1] += dp[i][l] * p[i]
        dp[i + 1][l] += dp[i][l] * (1.0 - p[i])
ans = 0.0
for i in range(N // 2 + 1, N + 1):
    ans += dp[N][i]
print(ans)
### BUGGY CODE ###

import math
#import numpy as np
import queue
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)

def main():
    s = input()
    k = int(input())
    ss = set()
    alp = "abcdefghijklmnopqrstuvwxyz"
    for ai in alp:
        for i,si in enumerate(s):
            if si != ai:
                continue
            nw = ""
            for sj in s[i::]:
                nw += sj
                ss.add(nw)
        if len(ss) >= k:
            break
    print(sorted(ss)[k-1])



    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
#import numpy as np
import queue
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)

def main():
    s = input()
    k = int(input())
    ss = set()
    alp = "abcdefghijklmnopqrstuvwxyz"
    for ai in alp:
        for i,si in enumerate(s):
            if si != ai:
                continue
            nw = ""
            for sj in s[i::]:
                nw += sj
                if len(nw) > 5:
                    break
                ss.add(nw)
        if len(ss) >= k:
            break
    print(sorted(ss)[k-1])



    return

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

from collections import deque

num = int(input())

arr = deque([])

for i in range(num):
    arr.append(int(input()))

for i in range(num):
    a = arr.popleft()
    print(max(list(arr)))
    arr.append(a)

### FIXED CODE ###

from collections import deque

num = int(input())

arr = []

for i in range(num):
    arr.append(int(input()))

arr0 = sorted(arr,reverse=True)
arr00 = arr0[0]
arr01 = arr0[1]

for i in range(num):
    if arr[i] != arr00:
        print(arr00)
    else:
        print(arr01)
### BUGGY CODE ###

from itertools import accumulate


def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split())) + [0]
    for _ in range(k):
        l = [0] * (n + 1)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = list(accumulate(l))
    print(*A[:-1])


if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
from numba import jit


@jit("i8, i8, i8[:]")
def myfunc(n, k, A):
    for _ in range(k):
        l = np.zeros((n + 1,), dtype=np.int64)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.cumsum(l)
        if np.all(A[:-1] == n):
            break
    return A


def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    A = np.append(A, 0)
    print(*myfunc(n, k, A)[:-1])


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

num = input().split()
 
n = int(num[0])
y = int(num[1])

m = 0
g = 0
s = 0

flag = False


for i in range(n+1):
    if flag:
        break
    m = i
    
    for e in range(n+1):
        g = e
        
        me = m * 10000
        ge = g * 5000
        
        tmpS =  y - (me+ge)
        
        if (tmpS / 1000) + (m+g) == n and me+ge+tmpS == y and (tmpS / 1000) >= 0:
            flag = True
            ma = m
            ga = g
            if tmpS / 1000 > 0:
                sa = tmpS / 1000
                sa = int(sa)
            else: 
                sa = 0
if flag:
    print(ma,ga,sa)
else:
    print(-1,-1,-1)



### FIXED CODE ###

num = input().split()
 
n = int(num[0])
y = int(num[1])

m = 0
g = 0
s = 0

flag = False


for i in range(n+1):
    if flag:
        break
    m = i
    
    me = m * 10000
    
    if (y - me) / 5000 <= n: 
    
        for e in range(n+1):
            if flag:
                break
            g = e
            
            ge = g * 5000
            
            tmpS =  y - (me+ge)
            
            if (tmpS / 1000) + (m+g) == n and me+ge+tmpS == y and (tmpS / 1000) >= 0:
                flag = True
                ma = m
                ga = g
                if tmpS / 1000 > 0:
                    sa = tmpS / 1000
                    sa = int(sa)
                else: 
                    sa = 0
if flag:
    print(ma,ga,sa)
else:
    print(-1,-1,-1)
### BUGGY CODE ###

n = int(input())
rec = {}
for i in range(n):
    a = int(input())
    rec[i + 1] = a

i = 1
rec2  = [1]
num = 0
while i != 2:
    i = rec[i]
    if i not in rec2:
        rec2.append(i)
        num += 1
    else:
        num = -1
        break

print(num)

### FIXED CODE ###

n = int(input())
rec = {}
for i in range(n):
    a = int(input())
    rec[i + 1] = a

i = 1
rec2 = [1]
num = 0
while i != 2 and num < n:
    i = rec[i]
    num += 1

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

s = input()[::-1]

counts = [0] * 2019

num, d = 0, 0

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

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

ans += counts[0]

print(ans)

### 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 ###

import sys
input = sys.stdin.readline
INF = 10**10

h, n = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
dp = [INF]*(h+1)
dp[0] = 0
for i in range(n):
  a, b = AB[i]
  for j in range(h+1):
    if j <= a:
      dp[j] = min(dp[j], b)
    else:
      dp[j] = min(dp[j], dp[j-a]+b)
print(dp[h])

### FIXED CODE ###

import sys
input = sys.stdin.readline

h, n = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
dp = [float("inf")]*(h+1)
dp[0] = 0
for i in range(n):
  a, b = AB[i]
  for j in range(h+1):
    if j <= a:
      dp[j] = min(dp[j], b)
    else:
      dp[j] = min(dp[j], dp[j-a]+b)
print(dp[h])
### BUGGY CODE ###

import sys
import  math
import fractions
from collections import defaultdict
from functools import reduce
stdin = sys.stdin
         
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
     
INF=10**18
mod=10**9+7
N=int(input())
A=nl()
ans=0
min_bai=1
#for i in range(N):#最大公倍数
#    min_bai=min_bai*A[i]//fractions.gcd(min_bai,A[i])

lcm = reduce(lambda x,y: x//fractions.gcd(x,y)*y, A)
 
for i in range(N):
    ans+=lcm//A[i]


print(ans%mod)
    

### FIXED CODE ###

import sys
import  math
import fractions
from collections import defaultdict
from functools import reduce
stdin = sys.stdin
         
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
     
INF=10**18
mod=10**9+7
N=int(input())
A=nl()
ans=0
min_bai=1
#for i in range(N):#最大公倍数
#    min_bai=min_bai*A[i]//fractions.gcd(min_bai,A[i])

lcm = reduce(lambda x,y: x//fractions.gcd(x,y)*y, A)
 
#for i in range(N):
#    ans+=lcm//A[i]

ans = sum(lcm//x for x in A)
print(ans%mod)
### BUGGY CODE ###

n = int(input())
s = list(input())

R=[0]*n
G=[0]*n
B=[0]*n

for i in range(n):
    if s[i]=='R':
        R[i]=1
    elif s[i]=='G':
        G[i]=1
    elif s[i]=='B':
        B[i]=1

ans=0
for i in range(n):
    if R[i]==1:
        lG=sum(G[:i])
        lB=sum(B[:i])
        rG=sum(G[i:])
        rB=sum(B[i:])
        ans+=(lG+rG)*(lB+rB)
        for j in range(1,n//2+1):
            if R[i]==1:
                if 0<=i-j<n and 0<=i+j<n:
                    if G[i-j]==1 and B[i+j]==1:
                        ans-=1
                    if B[i-j]==1 and G[i+j]==1:
                        ans-=1
                if 0<=i-2*j<n:
                    if G[i-j]==1 and B[i-2*j]==1:
                        ans-=1
                    if B[i-j]==1 and G[i-2*j]==1:
                        ans-=1
                if 0<=i+2*j<n:
                    if G[i+j]==1 and B[i+2*j]==1:
                        ans-=1
                    if B[i+j]==1 and G[i+2*j]==1:
                        ans-=1

print(ans)


### FIXED CODE ###

n = int(input())
s = list(input())

R=[0]*n
G=[0]*n
B=[0]*n

for i in range(n):
    if s[i]=='R':
        R[i]=1
    elif s[i]=='G':
        G[i]=1
    elif s[i]=='B':
        B[i]=1

ans=0
for i in range(n):
    if R[i]==1:
        lG=sum(G[:i])
        lB=sum(B[:i])
        rG=sum(G[i:])
        rB=sum(B[i:])
        ans+=(lG+rG)*(lB+rB)
        for j in range(1,n//2+1):
            if R[i]==1:
                if 0<=i-j<n and 0<=i+j<n:
                    if G[i-j]==1 and B[i+j]==1:
                        ans-=1
                    if B[i-j]==1 and G[i+j]==1:
                        ans-=1
                if 0<=i-2*j<n:
                    if G[i-j]==1 and B[i-2*j]==1:
                        ans-=1
                    if B[i-j]==1 and G[i-2*j]==1:
                        ans-=1
                if 0<=i+2*j<n:
                    if G[i+j]==1 and B[i+2*j]==1:
                        ans-=1
                    if B[i+j]==1 and G[i+2*j]==1:
                        ans-=1

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

n = int(input())

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

cnt=0

for i in range(n-1):
    sum_a = sum(a[0:i+1])
    if abs(sum_a) >= abs(a[i+1]) or sum_a*a[i+1]>=0:
        if sum_a<0:
            cnt += abs(-sum_a+1 -a[i+1])
            a[i+1]=-sum_a+1
        elif sum_a>=0:
            cnt+=abs(-sum_a-1-a[i+1])
            a[i+1]=-sum_a-1
print(cnt)

### FIXED CODE ###

import numpy as np
import copy

n = int(input())

a = list(map(int,input().split()))
b=copy.deepcopy(a)

cntm=0
cntp=0
sum_a=0
sum_b=0

if a[0]<=0:
    cntp+=-a[0]+1
    a[0]=1
if b[0]>=0:
    cntm+=b[0]+1
    b[0]=-1
for i in range(n-1):
    sum_a += a[i]
    sum_b += b[i]
    if abs(sum_a) >= abs(a[i+1]) or sum_a*a[i+1]>=0:
            cntp += abs(-sum_a-np.sign(sum_a) -a[i+1])
            a[i+1]=-sum_a-np.sign(sum_a)
    if abs(sum_b) >= abs(b[i+1]) or sum_b*b[i+1]>=0:
            cntm += abs(-sum_b-np.sign(sum_b) -b[i+1])
            b[i+1]=-sum_b-np.sign(sum_b)
print(min(cntm, cntp))
### BUGGY CODE ###

X, N = map(int, input().split())
ans = X
if N>0:
  P = list(map(int, input().split()))
  P.sort()
  if X in P:
    ans = 0
    x = P.index(X)
    i = 1
    a = x-1
    b = x+1
    while ans == 0:
      if a < 0:
        a = 0
      if b > N-1:
        b = N-1
      if X-i != P[a]:
        ans = X-i
      elif X+i != P[b]:
        ans = X+i
        a -= 1
      else:
        a -= 1
        b += 1
        i += 1
print(ans)

### FIXED CODE ###

X, N = map(int, input().split())
ans = X
if N>0:
  P = list(map(int, input().split()))
  P.sort()
  if X in P:
    ans = 0
    x = P.index(X)
    i = 1
    a = x-1
    b = x+1
    m = min(P[N-1]-X, X-P[0])
    for i in range(1,m+2):
      if a < 0:
        a = 0
      if b > N-1:
        b = N-1
      if X-i != P[a]:
        ans = X-i
        break
      elif X+i != P[b]:
        ans = X+i
        break
      else:
        a -= 1
        b += 1
print(ans)
### BUGGY CODE ###

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

H = sorted(H, reverse=True)
while (K > 0) and (len(H) > 0):
    H.pop(0)
    K -= 1
print(sum(H))

### FIXED CODE ###

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

H = sorted(H, reverse=True)
if K >= len(H):
    print(0)
else:
    del H[0:K]
    print(sum(H))
### BUGGY CODE ###

from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
q=[0]*99*M
v=[[]for _ in q]
z=0
for a,b in t:v[a-1]+=[b]
for i in v[:M]:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)

### FIXED CODE ###

from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in range(M)]
for i in range(N):
	if t[2*i]<=M:
		v[t[2*i]-1].append(t[2*i+1])
z=0
q=[]
for i in range(M):
	for j in v[i]:
		heappush(q,-j)
	b=0
	if len(q):
		b=heappop(q)
	z-=b
print(z)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
S = []
A = []
for i in range(N):
    s = input()
    S.append(s)    

n = len(S)
for i in range(n):
    cnt = 0
    for j in range(n):
        if S[i] == S[j]:
            cnt += 1
            if cnt == 2:
                S[j] = 0
print(len([i for i in S if i != 0]))

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
S = []
for i in range(N):
    s = input()
    S.append(s)    
print(len(set(S)))
### BUGGY CODE ###

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

a.sort()
p = []
k = set()

while a:
    prime = a[ 0 ]

    p.append( prime )

    i = 0
    flag = 0
    while i < len( a ):
        if a[ i ] == prime and flag == 1:
            k.add( prime )
        flag = 1
        if a[ i ] % prime == 0:
            a.pop( i )
            continue
        i += 1

# print( p, k )
print( len( p ) - len( k ) )


### FIXED CODE ###

# 以下カンニング
n = int( input() )
a = list( map( int, input().split() ) )

max_a = max( a )

c = {} # c[ a_i ] = aに含まれるa_iの個数
d = {} # d[ a_i ] = aにa_iの約数( < a_i )があるか(bool)
for a_i in a:
    try:
        c[ a_i ] += 1
    except KeyError:
        c[ a_i ] = 1
        d[ a_i ] = False # 初期値

for a_i in a:
    if c[ a_i ] > 0:
        tmp = 2 * a_i
        while tmp <= max_a:
            d[ tmp ] = True
            tmp += a_i

ans = 0
for a_i in a:
    if c[ a_i ] == 1 and d[ a_i ] == False:
        ans += 1

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

n = int(input())
li = list(map(int, input().split()))
li.sort()
inf = (10**6)+1
isprime = [False]*(inf+1)
for i in li:
    isprime[i] = True
for i in li:
    if not isprime[i]:
        continue
    for k in range(i*2, inf+1, i):
        isprime[k] = False
prime_list = []
for i in range(len(li)):
      if i+1<len(li):
            if li[i] == li[i+1]:
                isprime[li[i]] = False
for i in range(1, inf+1):
    if isprime[i]:
        prime_list.append(i)
print(len(prime_list))


### FIXED CODE ###

n = int(input())
li = list(map(int, input().split()))
li.sort()
inf = (10**6)+1
isprime = [False]*(inf+1)
for i in li:
    isprime[i] = True
temp = 0
for i in li:
    if i == temp:
        isprime[i] = False
    if not isprime[i]:
        continue
    for k in range(i*2, inf+1, i):
        isprime[k] = False
    temp = i
prime_list = []
for i in range(len(li)):
      if i+1<len(li):
            if li[i] == li[i+1]:
                isprime[li[i]] = False
for i in range(1, inf+1):
    if isprime[i]:
        prime_list.append(i)
print(len(prime_list))
### BUGGY CODE ###

s = str(input())
N = len(s)
array = [0]*2019
array[0] += 1
count = 0
d = 0
for i in reversed(range(0, N)):
    x = s[i:N]
    y = int(x)
    d = ( d + int( s[i] ) * 10 ** ( N - i - 1 ) % 2019 ) % 2019
    array[d] += 1
for i in array:
    count += i*(i-1)/2
print(int(count))

### FIXED CODE ###

s = str(input())
N = len(s)
array = [0]*2019
array[0] += 1
count = 0
d = 1
r = 0
for i in reversed(range(0, N)):
    #x = s[i:N]
    #y = int(x)
    r = ( r + int( s[i] ) * d ) % 2019
    d = d * 10 % 2019
    array[r] += 1
for i in array:
    count += i*(i-1)/2
print(int(count))
### BUGGY CODE ###

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

"""
DPを考える
"""

result = [0] * (N+1)
result[0] = 1
mod = 10**9 + 7
for i in range(N+1):
    if i not in A:
        if i >= 2:
            result[i] = (result[i-1] + result[i-2])%mod
        if i == 1:
            result[i] = 1

print(result[N])

### FIXED CODE ###

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

"""
DPを考える
"""

result = [0] * (N+1)
result[0] = 1
if 1 not in A:
    result[1] = 1
mod = 10**9 + 7
for i in range(2,N+1):
    if i not in A:
        result[i] = (result[i-1] + result[i-2])

print(result[N]%mod)
### BUGGY CODE ###

S = input()
s = [0]*(len(S)+1)
for i in range(len(S)):
    s[i+1] = s[i] +int(S[i])
L1 = []
L2 = []
L3 = []
for i in range(len(s)):
    if s[i]%3==0:
        L1.append(i)
    if s[i]%3==1:
        L2.append(i)
    if s[i]%3==2:
        L3.append(i)

count = 0
for i in range(len(L1)):
    for j in range(i+1,len(L1)):
        if int(S[L1[i]:L1[j]])%2019 == 0:
            count += 1
for i in range(len(L2)):
    for j in range(i+1,len(L2)):
        if int(S[L2[i]:L2[j]])%2019 == 0:
            count += 1
for i in range(len(L3)):
    for j in range(i+1,len(L3)):
        if int(S[L3[i]:L3[j]])%2019 == 0:
            count += 1
print(count)

### FIXED CODE ###

s = input()[::-1]

sum_of_digits = 0
cnts = [0]*2019
cnts[0] = 1

d = 1

for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019
    cnts[sum_of_digits] += 1

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

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

N, K = list(map(int, input().split()))
S = input()
 
S += "X"
j = 0
count = 1
change = [] if S[0] != "0" else [0]
for j in range(len(S)-1):
  if S[j:j+2] == "10":
    change.append(count)
    count = 0
  elif S[j:j+2] == "01":
    change.append(count)
    count = 0
  count += 1

change.append(count-1)
#print(change)
max_len = max([sum(change[i:i+2*K+1]) for i in range(0, len(change), 2)])
  
print(max_len)

### FIXED CODE ###

N, K = list(map(int, input().split()))
S = input()
 
S += "X"
i = 0
j = 0
max_len = 0
change = 0 if S[0] != "0" else 1
while j < len(S)-1:
  if change <= K:
    #print(i, j)
    max_len = max([j-i+1, max_len])
    if S[j:j+2] == "10":
      change += 1
    j += 1
  else:
    if S[i:i+2] == "01":
      change -= 1
    i += 1

print(max_len)
### BUGGY CODE ###

n, m = [int(x) for x in input().split()]
a = [int(input()) for _ in range(m)]
# a = [int(x) for x in input().split()]

memo = [0]*(n + 1)

for i in range(n+1):
  if i in a:
    continue
  else:
    if i == 0 or i == 1:
      memo[i] = 1
    else:
      memo[i] = (memo[i-1] + memo[i-2])%((10**9)+7)

print(memo[n])

### FIXED CODE ###

n, m = [int(x) for x in input().split()]
a = set([int(input()) for _ in range(m)])
# a = [int(x) for x in input().split()]
 
memo = [0]*(n + 1)
 
for i in range(n+1):
  if i in a:
    continue
  else:
    if i == 0 or i == 1:
      memo[i] = 1
    else:
      memo[i] = (memo[i-1] + memo[i-2])%((10**9)+7)
 
print(memo[n])
### BUGGY CODE ###

import math
A,B,N = [int(i)for i in input().split()]
tmpmax=0
for i in range(N+1):
  tmp=math.floor(A*i/B)-A*math.floor(i/B)
  if tmp > tmpmax:
    tmpmax=tmp
    #print("{},{}".format(i,tmp))
print(tmpmax)

### FIXED CODE ###

import math
A,B,N = [int(i)for i in input().split()]

def func(A, B, N):
  if N>B-1:
    return math.floor(A*(B-1)/B)-A*math.floor((B-1)/B)
  else:
    return math.floor(A*N/B)-A*math.floor(N/B)


print(func(A,B,N))
### BUGGY CODE ###

import itertools
import math 
def C(n,r):
    if n-r < 0:
        return 0 
    return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

n = int(input())
a = list(map(int, input().split()))
d = {}
for i in a:
    d[i] = d.get(i, 0)+1

c = 0
cc = {}
for key, val in d.items():
    temp = C(val,2)
    c += temp
    if cc.get(key) is None:
        cc[key] = temp - C(val-1,2)
for i in a:
    print(c - cc[i])


### FIXED CODE ###

import itertools
import math 
def C(n,r):
    if n-r < 0:
        return 0 
    return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

n = int(input())
a = list(map(int, input().split()))
d = {}
for i in a:
    d[i] = d.get(i, 0)+1

c = 0
cc = {}
for key, val in d.items():
    temp = C(val,2)
    c += temp
    if cc.get(key) is None:
        cc[key] = temp - C(val-1,2)
for i in a:
    print(c - cc[i])
### BUGGY CODE ###

n = int(input())

for i in range(1,int(n**(1/2))+1):
    if n%i!=0:
        continue
    x,y = i,n//i
    a=1
    b=1-x
    while 1:
        tmp = a**5-b**5
        if tmp>n and b>0:
            break
        if tmp==n:
            print(a,b)
            exit()
        a+=1
        b+=1
    a=1
    b=1-y
    while 1:
        tmp = a**5-b**5
        if tmp>n and b>0:
            break
        if tmp==n:
            print(a,b)
            exit()
        a+=1
        b+=1


### FIXED CODE ###

n = int(input())

for a in range(500):
    for b in range(-500,500):
        if a**5-b**5==n:
            print(a,b)
            exit()
### BUGGY CODE ###

# coding: utf-8
# Your code here!
num = int(input())
s = list(map(int,input().split()))
res = 1
for i in s:
    res *= i
    
if res <= 10 ** 18:    
    print(res)
else:
    print(-1)
    


### FIXED CODE ###

# coding: utf-8
# Your code here!
num = int(input())
s = list(map(int,input().split()))
res = 1
for i in s:
    res *= i
    if res >= 10 ** 18:
        break

if 0 in s:
    print(0)
elif res <= 10 ** 18:    
    print(res)
else:
    print(-1)
### BUGGY CODE ###

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

for k in range(K):
  B = [0] * N
  for i in range(N):
    l = max(0, i - A[i])
    r = min(i + A[i] + 1, N)
    B[l] += 1
    if r < N:
      B[r] -= 1

  for j in range(N - 1):
    B[j + 1] += B[j]
  
  if k ** 2 >= N:
    break
  A = B
  
for b in B:
  print(b, end=" ")

### FIXED CODE ###

from numba import jit

@jit
def solve(N, K, A):
  for k in range(K):
    B = [0] * N
    for i in range(N):
      l = max(0, i - A[i])
      r = i + A[i] + 1
      B[l] += 1
      if r < N:
        B[r] -= 1

    for j in range(N - 1):
      B[j + 1] += B[j]
  
    if A == B:
      return B
    A = B
  return B
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = solve(N, K, A)
for b in B:
  print(b, end=" ")