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

import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
n = int(readline())
a = list(map(int, readline().split()))
b = defaultdict(list)
c = defaultdict(list)

for i, v in enumerate(a, 1):
  b[i + v].append(i)
  c[i - v].append(i)

ans = 0
for v, L in b.items():
  for i in L:
    for j in c[v]:
      if i < j:
        ans += 1
print(ans)

### FIXED CODE ###

import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
n = int(readline())
a = list(map(int, readline().split()))
b = defaultdict(list)
c = defaultdict(list)

for i, v in enumerate(a, 1):
  b[i + v].append(i)
  if 2 <= i - v <= 100000001:
    c[i - v].append(i)
c = dict(c)

ans = 0
for v, L in b.items():
  for j in L:
    if v in c:
      ans += len(c[v])
print(ans)
### BUGGY CODE ###

from bisect import bisect_left
def main():
    h, w, m = map(int, input().split())
    bombs = set()
    cnt_row, cnt_col = [0]*(h+1), [0]*(w+1)
    for _ in range(m):
        y, x = map(int, input().split())
        cnt_row[y] += 1
        cnt_col[x] += 1
        bombs.add((y, x))
    ans = 0
    for y, x in bombs:
        ans = max(ans, cnt_row[y]+cnt_col[x]-1)
    col_indexs = [i for i in range(w+1)]
    col_indexs.sort(key=lambda x: cnt_col[x])
    cnt_col.sort()
    row_indexs = [i for i in range(h+1)]
    row_indexs.sort(key=lambda x: cnt_row[x])
    cnt_row.sort()
    for i, row_val in zip(reversed(row_indexs), reversed(cnt_row)):
        p = ans - row_val
        idx = bisect_left(cnt_col, p)
        for k in reversed(range(idx, w+1)):
            j = col_indexs[k]
            if (i, j) in bombs:
                continue
            if ans < row_val + cnt_col[k]:
                ans = row_val + cnt_col[k]
                break
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from bisect import bisect_left
def main():
    h, w, m = map(int, input().split())
    bombs = set()
    cnt_row, cnt_col = [0]*(h+1), [0]*(w+1)
    for _ in range(m):
        y, x = map(int, input().split())
        cnt_row[y] += 1
        cnt_col[x] += 1
        bombs.add((y, x))
    max_cnt_row = max(cnt_row)
    max_cnt_col = max(cnt_col)
    idx_row = []
    idx_col = []
    for i in range(h+1):
        if cnt_row[i] == max_cnt_row:
            idx_row.append(i)
    for j in range(w+1):
        if cnt_col[j] == max_cnt_col:
            idx_col.append(j)
    ans = max_cnt_row + max_cnt_col - 1
    for i in idx_row:
        for j in idx_col:
            if not (i, j) in bombs:
                ans = max_cnt_row + max_cnt_col
                break
    print(ans)

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

x = int(input())
ans = 2

p = [2]
i = 1
Flag = True
if x > 2:
    while Flag:
        i += 2
        for j in p:
            if i%j == 0:
                break
            elif j == p[-1]:
                p.append(i)
                if i >= x:
                    ans = i
                    Flag = False

print(ans)


### FIXED CODE ###

x = int(input())
ans = 2

p = [2]
i = 1
Flag = True
while i**2 < 100001:
    i += 2
    for j in p:
        if i%j == 0:
            break
        elif j == p[-1]:
            p.append(i)
for i in range(100000):
    if x+i in p:
        ans = x+i
        break
    elif x+i > p[-1]:
        for j in p:
            if (x+i)%j == 0:
                break
            elif j == p[-1]:
                ans = x+i
                break
        if ans == x+i:
            break

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

import fractions

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

x=int(input())
a=list(map(int, input().split()))
ans=0
if x==1:
	print(1)
else:
	chk=lcm(a[0],a[1])
	for i in range(x):
		chk=lcm(chk,a[i])
	for i in range(x):
		ans=(ans+(chk//a[i]))%(10**9+7)
	print(ans)

### FIXED CODE ###

import fractions

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

x=int(input())
a=list(map(int, input().split()))
ans=0
if x==1:
	print(1)
else:
	chk=lcm(a[0],a[1])
	for i in range(x):
		chk=lcm(chk,a[i])
	for i in range(x):
		ans=ans+(chk//a[i])
	print(ans%(10**9+7))
### BUGGY CODE ###

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

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

### FIXED CODE ###

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

sums = [0] * N
sums[0] = A[0]
for i in range(N - 1):
    sums[i + 1] = sums[i] + A[i + 1]  # sums[i] stores the sum of A0~Ai

sum = 0
for i in range(N):
    sum += A[i] * (sums[N-1] - sums[i])

print(sum % 1000000007)
### BUGGY CODE ###

S = list(map(str, input()))
Q = int(input())
f = 0
for i in range(Q):
  Query = input().split()
  if Query[0] == '1':
    f = 1 - f
  else:
    if int(Query[1]) - f == 1:
      S = [Query[2]] + S
    else:
      S = S + [Query[2]]
if f == 0:
  for i in S:
    print(i, end="")
else:
  for i in range(len(S)-1, -1, -1):
    print(S[i], end="")
print("")

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
d = 0 # d=0:right, d=1:left
for i in range(Q):
  I = list(input().split())
  if I[0] == "1":
    d ^= 1
  else:
    if d + int(I[1]) == 2:
      S.append(I[2])
    else:
      S.appendleft(I[2])
if d == 1:
  S.reverse()
for s in S:
  print(s, end="")
print()
### BUGGY CODE ###

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

lis = list()

for i in range(1, len(P)+1):
    for j in range(1, i+1):
        if P[i-1] <= P[j-1]:
            pass
        else:
            lis.append(P[i-1])

lis

print(N - int(len(set(lis))))

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
m = float("inf")
count = 0

for i in P:
    if m > i:
        m = i
    if m == i:
        count += 1
print(count)
### BUGGY CODE ###

n,m=map(int,input().split())
a = list(map(int, input().split()))
b=[0]*m
c=[0]*m
for i in range(m):
    b[i],c[i] = map(int, input().split())

for i in range(m):
    for _ in range(b[i]):
        a.append(c[i])
a.sort(reverse=True)

print(sum(a[:n]))

### FIXED CODE ###

n,m=map(int,input().split())
a = list(map(int, input().split()))
bc=[list(map(int,input().split())) for _ in range(m)]
#print(bc)
bc=sorted(bc,key= lambda x:x[1],reverse=True)
#print(bc)

bc2=[]
for i in range(m):
    bc2.extend([bc[i][1]]*bc[i][0])
    if len(bc2)>n: break
#print(bc2)
a.extend(bc2)
a.sort(reverse=True)

print(sum(a[:n]))
### BUGGY CODE ###

#import time 

#t1 = time.time()
N, K = map(int, input().split())
#P_list = [i for i in map(int, input().split())]

def func(a):
	a_list = [i/a for i in range(1, a+1)]
	return sum(a_list)

ALL_dice = [i for i in range(1, 1001)]
ALL_exp = list(map(func, ALL_dice))



#P_exp = list(map(func, P_list))

P_exp = [ALL_exp[i-1] for i in map(int, input().split())]

#A_list = []
#sum_K = 0
#t1 = time.time()
A_list = [sum(P_exp[i:i+K]) for i in range(N-K+1)]
"""
for i in range(N-K+1):
	for j in range(K):
		sum_K += P_exp[i+j]

	A_list.append(sum_K)
	sum_K = 0
"""
print(max(A_list))
#print(A_list)
#t2 = time.time()
#print(t2-t1)


### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
P_exp = np.array([0] + [(1+i)/2 for i in map(int, input().split())])
E_sum = np.cumsum(P_exp)

print((E_sum[K:]-E_sum[:-K]).max())
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

dp = [float("inf")] * ((1<<n) + 1)
dp[0] = 0

for i in range(m):
    a, b = map(int, input().split())
    c = sum(1<<(ci-1) for ci in map(int, input().split()))

    for j in range(1<<n):
        dp[j | c] = min(dp[j] + a, dp[j | c])


if dp[(1<<n) - 1] == float("inf"):
    ans = -1
else:
    ans = dp[(1<<n) - 1]

print(ans)


### FIXED CODE ###

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

dp = [float("inf")] * ((1<<n) + 1)
dp[0] = 0

for i in range(m):
    a, b = map(int, input().split())
    c_list = list(map(int, input().split()))
    c = 0
    for j in range(b):
        c += 1 << (c_list[j]-1)

    for j in range(1<<n):
        dp[j | c] = min(dp[j] + a, dp[j | c])

if dp[(1<<n) - 1] == float("inf"):
    ans = -1
else:
    ans = dp[(1<<n) - 1]

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

S = input()
leng = len(S)
S = S[::-1]

count = [0] * 2019
count[0] = 1

num = 0
d = 1

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


res = 0
for cnt in count:
    res += cnt * (cnt - 1) // 2

print(res)

### FIXED CODE ###

s = input()[::-1]

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

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

p=10**9+7
ans=0
for i in range(1,n+1):
    if i==1:
        now=n%p
    else:
        now=now*(n+1-i)*pow(i,p-2,p)%p
    if i==a or i==b:
        continue
    else:
        ans+=now
        ans%=p



print(ans)


### FIXED CODE ###

n, a, b=map(int, input().split())
mod = 10 ** 9 + 7 
def cmb(n, r, mod):
    r = min(r, n -r)
    if r == 0: return 1
    over, under = 1, 1
    for i in range(1, r+1):
        over = over * (n-i+1) % mod
        under = under * i % mod
    
    inv=pow(under, mod-2, mod)
    
    return over*inv % mod
  
print((pow(2,n,mod)-1 - cmb(n, a,mod)-cmb(n,b,mod))%mod)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

import sys

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

    nw = 1
    lp0 = [1]
    for i in range(N):
        nw = A[nw-1]
        if nw in lp0:
            break
        else:
            lp0.append(nw)
    lpc = i+1 - lp0.index(nw)
    lp = lp0[-lpc:]

    if K<=len(lp0)-1:
        print(lp0[K])
    else:
        K-= len(lp0)-1
        K=K%lpc - 1
        print(lp[K])

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

import sys

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

    nw = 1
    lp0 = [1]
    lpl = {1}
    for i in range(N):
        nw = A[nw-1]
        if nw in lpl:
            break
        else:
            lp0.append(nw)
            lpl.add(nw)
    lpc = i+1 - lp0.index(nw)
    lp = lp0[-lpc:]

    if K<=len(lp0)-1:
        print(lp0[K])
    else:
        K-= len(lp0)-1
        K=K%lpc - 1
        print(lp[K])

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

# coding: utf-8

import sys
input = sys.stdin.readline

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()))

bimi = []
for a in range(X):
        for b in range(Y):
                bimi.append(A[a] + B[b])

bimi.sort(reverse=True)
ans = []
for x in range(min(3000, len(bimi))):
        for c in range(Z):
                ans.append(bimi[x] + C[c])

ans.sort(reverse=True)

for i in range(K):
        print(ans[i])



### FIXED CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

bimi = []

for a in range(X):
        for b in range(Y):
                if (a + 1) * (b + 1) > K:
                                break

                for c in range(Z):
                        if (a + 1) * (b + 1) * (c + 1) > K:
                                break

                        bimi.append(A[a] + B[b] + C[c])

bimi.sort(reverse=True)

for i in range(K):
        print(bimi[i])
### BUGGY CODE ###

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

ans_set=set(a)
for i in range(len(a)):
    if(a[i] not in ans_set):
        continue
    else:
        for j in range(i+1,len(a)):
            if(a[j] in ans_set and a[j]%a[i]==0):
                ans_set.remove(a[j])
#print(ans_set)
print(len(ans_set))


### FIXED CODE ###

import numpy as np
n=int(input())
a=sorted(list(map(int,input().split())))

dp=np.array([0 for _ in range(max(a)+1)])
for i in range(n):
    ai=a[i]
    if(dp[ai]>=2):
        continue

    j=1
    while(ai*j<=a[-1]):
        dp[ai*j]+=1
        j+=1

print(sum(dp[ai]==1 for ai in a))
### BUGGY CODE ###

x,y,z,N =(int(i) for i in input().split())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]

sa=sorted(a,reverse=True)
sb=sorted(b,reverse=True)
sc=sorted(c,reverse=True)
l=[]#端点情報
n=0
i=0
j=0
k=0

while n<N:
  print(sa[i]+sb[j]+sc[k])
  l.append([i,j,k])
  maxl=0
  maxijk=[len(sa)-1,len(sb)-1,len(sc)-1]
  for w in l:
    if w[0]<len(sa)-1:
      if not ([w[0]+1,w[1],w[2]] in l):
        if maxl<=sa[w[0]+1]+sb[w[1]]+sc[w[2]]:
          maxl=sa[w[0]+1]+sb[w[1]]+sc[w[2]]
          maxijk=[w[0]+1,w[1],w[2]]
    if w[1]<len(sb)-1:
      if not([w[0],w[1]+1,w[2]] in l):
        if maxl<=sa[w[0]]+sb[w[1]+1]+sc[w[2]]:
          maxl=sa[w[0]]+sb[w[1]+1]+sc[w[2]]
          maxijk=[w[0],w[1]+1,w[2]]
    if w[2]<len(sc)-1:
      if not([w[0],w[1],w[2]+1] in l):
        if maxl<=sa[w[0]]+sb[w[1]]+sc[w[2]+1]:
          maxl=sa[w[0]]+sb[w[1]]+sc[w[2]+1]
          maxijk=[w[0],w[1],w[2]+1]
    i=maxijk[0]
  j=maxijk[1]
  k=maxijk[2]
  n+=1

### FIXED CODE ###

#解答を見た後


x,y,z,N =(int(i) for i in input().split())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]

sa=sorted(a,reverse=True)
sb=sorted(b,reverse=True)
sc=sorted(c,reverse=True)
answer=[]

for i in range(len(sa)):
  for j in range(len(sb)):
    if (i+1)*(j+1)>N:break
    for k in range(len(sb)):
      if (i+1)*(j+1)*(k+1)>N:break 
      answer.append(sa[i]+sb[j]+sc[k])
answer=sorted(answer,reverse=True)
for i in range(0,N):
  print(answer[i])
### BUGGY CODE ###

import sys
from math import factorial as fac

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

factor = {}
tmp = 2
while(M // tmp >= 1):
    if(M % tmp != 0):
        if(tmp == 2):
            tmp += 1
        else:
            tmp += 2
        continue

    M = M // tmp
    factor[tmp] = factor.get(tmp, 0) + 1

if(factor == {}):
    print(1)
    sys.exit()

ans = 1
max_a = 7 + 10 ** 9
tt = fac(N - 1)
# print(factor)
for i in factor.values():
    # print(i)
    a = 1
    for j in range(N, N + i):
        a = a * j
    tmp = a // fac(i)
    ans = (ans * tmp) % max_a
print(ans)

### FIXED CODE ###

import sys

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

factor = {}
tmp = 2
while(M // tmp >= 1):
    if(M % tmp != 0):
        if(tmp == 2):
            tmp += 1
        elif(M // tmp < tmp):
            tmp = M
        else:
            tmp += 2
        continue

    M = M // tmp
    factor[tmp] = factor.get(tmp, 0) + 1

if(factor == {}):
    print(1)
    sys.exit()

ans = 1
max_a = 7 + 10 ** 9
max_value = max(list(factor.values()))
aho = {0: 1}
fact = {0: 1}
abc = {}
for i in range(1, max_value + 1):
    # print(i)
    aho[i] = ((aho[i - 1] * (i + N - 1)))
    fact[i] = (fact[i - 1] * i)
    abc[i] = (aho[i] // fact[i]) % max_a


# print(factor)
# print(aho, fact)
for i in factor.values():
    # print(i)
    ans = (ans * abc[i]) % max_a
print(ans)
### BUGGY CODE ###

k = int(input())
a, b = map(int, input().split())
i = 1
flag = False

while i < b:
    dis = i * k
    if dis >= a and dis <= b:
        flag = True
        break


if flag:
    print("OK")
else:
    print("NG")


### FIXED CODE ###

k = int(input())
a, b = map(int, input().split())
i = 1
flag = False


while i < b:
    if k == 1:
        flag = True
        break
    dis = i * k
    if dis >= a and dis <= b:
        flag = True
        break

    i += 1


if flag:
    print("OK")
else:
    print("NG")
### BUGGY CODE ###

from collections import defaultdict
import sys
import resource
sys.setrecursionlimit(200000)
input = sys.stdin.readline


road_dict=defaultdict(list)

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

for _ in range(M):
    A,B=map(int,input().split())
    road_dict[A].append(B)
    road_dict[B].append(A)

result_dict=defaultdict(list)

def next_tansaku(kiten,counter):
    for i in road_dict[kiten]:
        if (i not in result_dict) or (result_dict[i][1]>counter):
            result_dict[i]=[kiten,counter]
            next_tansaku(i,counter+1)


next_tansaku(1,0)

print('Yes')
for k in range(2,N+1):
    print(result_dict[k][0])

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline


road_dict=defaultdict(list)

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

for _ in range(M):
    A,B=map(int,input().split())
    road_dict[A].append(B)
    road_dict[B].append(A)

result_dict=defaultdict(int)

next_list=[]
for i in road_dict[1]:
    if i not in result_dict:
        result_dict[i]=1
        next_list.append(i)

taisho_list=next_list[:]

while True:
    next_list=[]

    if len(taisho_list)==0:
        break

    for j in taisho_list:
        for k in road_dict[j]:
            if k not in result_dict:
                result_dict[k]=j
                next_list.append(k)
    taisho_list=next_list[:]


print('Yes')
for k in range(2,N+1):
    print(result_dict[k])
### BUGGY CODE ###

r1, c1, r2, c2 = map(int, input().split())
MOD = 10 ** 9 + 7


# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, r2 + c2 + 10):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


ans = 0
for r in range(r1, r2 + 1):
    ans += (nCr(r + c2 + 1, r + 1) - nCr(r + c1, r + 1)) % MOD
    ans %= MOD

print(ans % MOD)


### FIXED CODE ###

def main():
    r1, c1, r2, c2 = map(int, raw_input().split())
    MOD = 10 ** 9 + 7

    mod = 10 ** 9 + 7  # 出力の制限
    N = 10 ** 4
    g1 = [1, 1]  # 元テーブル
    g2 = [1, 1]  # 逆元テーブル
    inverse = [0, 1]  # 逆元テーブル計算用テーブル

    for i in range(2, r2 + c2 + 10):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    def cmb(n, r, mod):
        if (r < 0 or r > n):
            return 0
        r = min(r, n - r)
        return g1[n] * g2[r] * g2[n - r] % mod


    ans = 0
    for r in range(r1, r2 + 1):
        ans += ((cmb(r + c2 + 1, r + 1, MOD) % MOD) - (cmb(r + c1, r + 1, MOD) % MOD)) % MOD
        ans %= MOD

    print(ans % MOD)


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


from sys import stdin
import itertools

n = int(stdin.readline().rstrip())
ls = [int(x) for x in stdin.readline().rstrip().split()]

ans = 0
for v in itertools.permutations(ls, 3):
    #print(v)
    a=int(v[0])
    b=int(v[1])
    c=int(v[2])
    if a<b+c:
        if b<c+a:
            if c<a+b:
                ans += 1

print(int(ans/6))


### FIXED CODE ###

from sys import stdin
from collections import defaultdict, deque, Counter
import sys
from bisect import bisect_left
import heapq
import math

sys.setrecursionlimit(1000000000)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

n = int(stdin.readline().rstrip())
l = list(map(int, stdin.readline().rstrip().split()))
#A, B, C = map(int, stdin.readline().rstrip().split())
#S = [list(stdin.buffer.readline().decode().rstrip()) for _ in range(h)]

l.sort()
ans = 0

for i in range(n):
    for j in range(i+1, n):
        t = l[i] + l[j]
        idx = bisect_left(l,t)
        ans += max(0,idx-j-1)

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

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

def calc(a):
    for t in range(k):
        b = [0] * n
        for i in range(n):
            for j in range(n):
                if a[j] >=  abs(j - i):
                    b[i] += 1

        for i in range(n):
            if(max(n-i,i) > b[i]):
                break
            print("oh")
            for j in range(n):
                a[j] += n *(k-t)
            return a
        a = b
    return a

a = calc(a)
for i in a:
    print(i,end=" ")
        

### FIXED CODE ###

from math import log2
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0]*n

if(k > 10*log2(n) + 1):
    for i in range(n):
        print(n,end=" ")

else:
    for j in range(k):
        b = [0]*n
        for i in range(n):
            l = max(0,i-a[i])
            r = min(n-1,a[i]+i)
            b[l] += 1
            if(r+1<n):
                b[r+1] -= 1
        for i in range(1,n):
            b[i] += b[i-1]
        a = b


    for i in a:
        print(i,end=" ")
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    A = [int(x) for x in input().strip().split()]
    l = [0] * (N + 1)
    for i, a in enumerate(A):
        l[max(0, i-a)] += 1
        l[min(N, i+a+1)] -= 1
    p = 0
    cumsum = [0] * (N + 1)
    for i in range(N+1):
        p += l[i]
        cumsum[i] = p
    cumsum_ = A + [0]
    for k in range(min(K-1, 100)):
        p = 0
        for i in range(N+1):
            l[max(0, i-cumsum[i])] += 1
            l[min(N, i+cumsum[i]+1)] -= 1
            l[max(0, i-cumsum_[i])] -= 1
            l[min(N, i+cumsum_[i]+1)] += 1

        cumsum_ = cumsum[:]
        for i in range(N+1):
            p += l[i]
            cumsum[i] = p

    print(*cumsum[:-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    A = [int(x) for x in input().strip().split()]
    l = [0] * (N + 1)
    for i, a in enumerate(A):
        l[max(0, i-a)] += 1
        l[min(N, i+a+1)] -= 1
    p = 0
    cumsum = [0] * (N + 1)
    for i in range(N+1):
        p += l[i]
        cumsum[i] = p
    cumsum_ = A + [0]
    for k in range(min(K-1, 50)):
        p = 0
        for i in range(N+1):
            l[max(0, i-cumsum[i])] += 1
            l[min(N, i+cumsum[i]+1)] -= 1
            l[max(0, i-cumsum_[i])] -= 1
            l[min(N, i+cumsum_[i]+1)] += 1

        cumsum_ = cumsum[:]
        for i in range(N+1):
            p += l[i]
            cumsum[i] = p

    print(*cumsum[:-1])

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

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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

sum = pow(2,n,1000000007) -1

a = min(a, n-a)
b = min(b, n-b)
ans = sum - cmb(n,a)-cmb(n,b)

print(ans)

### FIXED CODE ###

n, a, b = map(int, input().split())
value_max = 2 * (10 ** 5)
com = [0 for _ in range(value_max + 1)]
com[1] = n
mod = 10 ** 9 + 7
mod_inverse = [pow(i, mod - 2, mod) for i in range(1, value_max + 1)]
ans = pow(2, n, mod)

for i in range(2, min(n, value_max) + 1):
    if (n - i + 1) == 0:
        break

    com[i] = com[i - 1] * (n - i + 1)
    com[i] *= mod_inverse[i - 1]
    com[i] %= mod

diff = (com[a] + com[b] + 1) % mod
print((ans - diff) % mod)
### BUGGY CODE ###

N=int(input())
S=list(map(int,input().split( )))
S = sorted(S)
tri_num=0
for i in range(N-2):
    k = i+2
    for j in range(i+1,N-1):
        while k < N:
            if S[i] + S[j] <= S[k]:
                tri_num = tri_num + k-j-1
                if k == i+2:
                    k+=1
                break
            elif k == N-1:
                tri_num = tri_num + k-j
            else:
                k+=1
print(tri_num)

### FIXED CODE ###

N=int(input())
S=list(map(int,input().split( )))
S = sorted(S)
tri_num=0
for i in range(N-2):
    k = i+2
    for j in range(i+1,N-1):
        while k < N:
            if S[i] + S[j] <= S[k]:
                tri_num = tri_num + k-j-1
                if k == i+2:
                    k+=1
                break
            if k == N-1:
                tri_num = tri_num + k-j
                break
            k+=1
print(tri_num)
### BUGGY CODE ###

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

for elem in a:
    ans *= elem
if 10 ** 18 < ans:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

if 0 in a:
    print(0)
else:
    for elem in a:
        ans *= elem
        if 10 ** 18 < ans:
            print(-1)
            exit()
    print(ans)