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

def A():
    temp = [int(i) for i in input().split()]
    print(max(0, temp[0]-2*temp[1]))

def B():
    N = int(input())
    T = [int(i) for i in input().split()]
    s = 0
    for i in range(N):
        for j in range(i):
            s += T[i]*T[j]
    print(s)

def C():
    N = int(input())
    S = input()
    if N == 1:
        print(1)
    else:
        ans = 1
        cur_c = S[0]
        for c in S:
            if c != cur_c:
                ans += 1
                cur_c = c
        
        print(ans)

def D():
    N = int(input())
    L = sorted([int(i) for i in input().split()],reverse = True)
    # dp_sum = [[0 for i in range(N)] for j in range(N)]
    # for i in range(N):
    #     for j in range(i):
    #         dp_sum[i][j] = L[i]+L[j]
    count = 0
    for i in range(N):
        for j in range(i):
            for k in range(j):
                if L[k] < L[i]+L[j] and L[j] < L[i]+L[k] and L[i] < L[j]+L[k]:
                    count += 1
    print(count)

D()

### FIXED CODE ###

def A():
    temp = [int(i) for i in input().split()]
    print(max(0, temp[0]-2*temp[1]))

def B():
    N = int(input())
    T = [int(i) for i in input().split()]
    s = 0
    for i in range(N):
        for j in range(i):
            s += T[i]*T[j]
    print(s)

def C():
    N = int(input())
    S = input()
    if N == 1:
        print(1)
    else:
        ans = 1
        cur_c = S[0]
        for c in S:
            if c != cur_c:
                ans += 1
                cur_c = c
        
        print(ans)

from bisect import bisect_left, bisect_right
from itertools import combinations 

def D():
    N = int(input())
    L = sorted([int(i) for i in input().split()])
    count = 0
    for i in range(N):
        s = 0
        e = i-1
        while s<e:
            if L[i] < L[s]+L[e]:
                count += e-s
                e -= 1
            else:
                s += 1

    # dp_sum = [[0 for i in range(N)] for j in range(N)]
    # count = 0
    # for i in range(N):
    #     for j in range(i):
    #         print(L, L[i]+L[j])
    #         print(bisect_left(L, L[i]+L[j])-2, count)
    #         check_idx = bisect_left(L, L[i]+L[j])
    # count = 0
    # for i in range(N):
    #     for j in range(i):
    #         for k in range(j):
    #             if L[k] < L[i]+L[j] and L[j] < L[i]+L[k] and L[i] < L[j]+L[k]:
    #                 count += 1

    print(count)

D()
### BUGGY CODE ###

from functools import lru_cache
import sys 
sys.setrecursionlimit(2147483647)

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

#@lru_cache(None)
def dfs(d,pre):
    if (d,pre) in dic: return dic[(d,pre)]
    if d < 0:
        dic[(d,pre)] = 0 
        return 0
    ma = 0 
    for idx,a in enumerate(A[d]):
        if idx != pre:
            res = dfs(d - 1,idx) + a 
            ma = max(res,ma)
    dic[(d,pre)] = ma
    return dic[(d,pre)]
dic = {}
res = dfs(N-1,-1)
print(res)



### FIXED CODE ###

N = int(input())
A = []
for i in range(0,N):
    A.append(list(map(int,input().split())))

dp = [[0 for _ in range(3)] for _ in range(N)]
for i in range(N):
    for j in range(3):
        if i == 0:
            dp[i][j]= A[i][j]
        else:
            tmp = [0] 
            for k in range(3):
                if j !=k:
                    tmp.append(dp[i-1][k])
            dp[i][j] = max(tmp) + A[i][j]
print(max(dp[-1]))
### BUGGY CODE ###

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

def f(x):
    z=[0]*40
    i=1
    while x>0:
        z[-i]=x%2
        x=x//2
        i+=1
    return z

for i in range(n):
    a[i]=f(a[i])

y=[0]*40
for i in range(40):
    y[i]=sum(a[j][i] for j in range(n))%2
ans=[]
for i in range(n):
    p=0
    for j in range(40):
        if y[-j-1]!=a[i][-j-1]:
            p+=2**j
    ans.append(p)
for i in range(n):
    print(ans[i], end=" ")


### FIXED CODE ###

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

def f(x):
    z=[0]*40
    i=1
    while x>0:
        z[-i]=x%2
        x=x//2
        i+=1
    return z

for i in range(n):
    a[i]=f(a[i])

y=[0]*40
for i in range(40):
    y[i]=sum(a[j][i] for j in range(n))%2
ans=[]
for i in range(n):
    p=0
    for j in range(40):
        if y[-j-1]!=a[i][-j-1]:
            p+=2**j
    ans.append(p)
for i in range(n):
    print(ans[i], end=" ")
### BUGGY CODE ###

N,K=(int(i) for i in input().split())
A = list(int(i) for i in input().split())  
minNum=0
i=0
A2=[]
ans=0

A2.extend(A[i:i+K])
while i<N:    
    #print(A2)
    minNum=int(min(A2))
   # print(minNum)
    j=i
    #特定範囲の最小化
    while j<i+K:
        #途中でオーバーしたら逃げる
        if len(A2)<=j:
            break
        #print(A2[j])
        A2[j]=minNum
        j+=1
    if i==0:
        i=i+K
    else:
        i=i+K-1

    ans+=1
    A2.extend(A[i:i+K-1])

#print(A2)
print(ans)    



### FIXED CODE ###

N,K=(int(i) for i in input().split())
A = list(int(i) for i in input().split())  
minNum=0
i=0
A2=[]
ans=0

while i<N:    
   
    if i==0:
        i=i+K
    else:
        i=i+K-1

    ans+=1
    
print(ans)
### BUGGY CODE ###

import copy

N, W = list(map(int, input().split()))
w = [0 for i in range(N)]
v = [0 for i in range(N)]
for i in range(N):
    w[i], v[i] = list(map(int, input().split()))


# N, W = [3, 8]
# w = [0 for i in range(N)]
# v = [0 for i in range(N)]


# w[0], v[0] = [3, 30]
# w[1], v[1] = [4, 50]
# w[2], v[2] = [5, 60]

s = [0 for i in range(W+1)]


for i in range(N):
    #print(s)
    ns = copy.copy(s)
    for j in range(W+1):
        for k in range(j + w[i], W+1):
            ns[k] = max(s[k], s[j] + v[i])
    s = ns

print(max(s))





### FIXED CODE ###

import copy

N, W = list(map(int, input().split()))
w = [0 for i in range(N)]
v = [0 for i in range(N)]
for i in range(N):
    w[i], v[i] = list(map(int, input().split()))




s = [[0 for i in range(W+1)] for i in range(N)]


for i in range(W+1):
    if i < w[0]:
        s[0][i] = 0
    else :
        s[0][i] = v[0]

for i in range(1,N):
    for j in range(w[i]):
        s[i][j] = s[i-1][j]
    for j in range(w[i], W+1):
        s[i][j] = max(s[i-1][j], s[i-1][j-w[i]] + v[i])
#print(s)
print(s[-1][-1])
### BUGGY CODE ###

L,R = map(int,input().split())
answer = float('inf')
for i in range(L,R):
  for j in range(i+1,R+1):
    m = (i*j)%2019
    answer = min(answer,m)
print(answer)

### FIXED CODE ###

L,R = map(int,input().split())
if R-L>2019:
  R=L+2019
answer = float('inf')
for i in range(L,R):
  for j in range(i+1,R+1):
    m = (i*j)%2019
    answer = min(answer,m)
print(answer)
### BUGGY CODE ###

from heapq import heapify, heappop, heappush
from math import ceil

n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]
hp = xh
heapify(hp)

ans = 0

while hp:
    left = heappop(hp)
    cnt = ceil(left[1] / a)
    li = []
    while hp and hp[0][0] <= left[0] + 2 * d:
        nxt = heappop(hp)
        if nxt[1] - a * cnt > 0:
            li.append([nxt[0], nxt[1] - a * cnt])

    for e in li:
        heappush(hp, e)

    ans += cnt

print(ans)


### FIXED CODE ###

from heapq import heapify, heappush, heappop
from math import ceil

REAL = 0
UNREAL = 1

n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]

hp = []
for x, h in xh:
    heappush(hp, [x, REAL, h])

bomb_acm = 0
ans = 0
while hp:
    x, r, h = heappop(hp)
    if r == REAL:
        if h > bomb_acm:
            left = h - bomb_acm
            bomb_cnt = ceil(left / a)
            hp_dis = a * bomb_cnt
            bomb_acm += hp_dis
            heappush(hp, [x + 2 * d, UNREAL, hp_dis])
            ans += bomb_cnt

    else: # r == UNREAL
        bomb_acm -= h

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

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

n,k = LI()

# 互いに素なa,bについて、a*x+b*y=1の一つの解[x,y]を出力
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

# aの逆元(mod M)を求める（aとMは互いに素）
def mod_inv(a,M=mod):
    x = extgcd(a,M)[0]
    return (M+x%M)%M

def nCk2(n,k):
    x = [0]*(k+1)
    x[0] = 1
    for i in range(1,k+1):
        x[i] = x[i-1]*(n-k+i)*mod_inv(i) % mod
    return x[-1]

ans = 1
for i in range(1,k+1):
    for j in range(1,min(i+1,n-i+1)):
        ans += nCk2(i-1,j-1) * nCk2(n,j) * nCk2(n-j,i)
        ans %= mod
print(ans)

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# 0!~n!をmodしつつ求める
def fact_all(n,M=mod):
    f = [1]*(n+1)
    ans = 1
    for i in range(1,n+1):
        ans = (ans*i)%M
        f[i] = ans
    return f

# inv(0!)~inv(n!)をmodしつつ求める
def fact_inv_all(fact_all,M=mod):
    N = len(fact_all)
    finv = [0]*N
    finv[-1] = pow(fact_all[-1],M-2,M)
    for i in range(N-1)[::-1]:
        finv[i] = finv[i+1]*(i+1)%M
    return finv

# nCkをmodしつつ返す
def nCk(n,k,fact_list=[],inv_list=[],M=mod):
    # a!をmodしつつ求める
    def fact(a,M=mod):
        ans = 1
        for i in range(2,a+1):
            ans = (ans*i)%M
        return ans

    # 互いに素なa,bについて、a*x+b*y=1の一つの解[x,y]を出力
    def extgcd(a,b):
        r = [1,0,a]
        w = [0,1,b]
        while w[2] != 1:
            q = r[2]//w[2]
            r2 = w
            w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
            r = r2
            w = w2
        return [w[0],w[1]]

    # aの逆元(mod M)を求める（aとMは互いに素）
    def mod_inv(a,M=mod):
        x = extgcd(a,M)[0]
        return (M+x%M)%M
    
    if fact_list and inv_list:
        return (((fact_list[n]*inv_list[k])%M)*inv_list[n-k])%M
    else:
        x = fact(n,M)
        y1 = mod_inv(fact(k,M),M)
        y2 = mod_inv(fact(n-k,M),M)
        return ((x*y1)%M*y2)%M

n,k = LI()

fact_list = fact_all(n)
inv_list = fact_inv_all(fact_list)

ans = 1
for i in range(1,min(k+1,n)):
    ans += nCk(n,i,fact_list,inv_list) * nCk(n-1,i,fact_list,inv_list)
    ans %= mod
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
a=[int(i) for i in input().split()]
mask=0
for k in range(K):
  mask|=1<<k
a.sort(reverse=True)
dp=[0]*(N+1)
dp[0]=1
for i in range(N):
  dp[i+1]=(dp[i]|(dp[i]<<a[i]))&mask

def solve(x):
  if (dp[x]<<a[x])&(~mask):
    return True
  else:
    return False
  
for i in range(-1,N)[::-1]:
  if solve(i):
    break
    
print(N-i-1)

### FIXED CODE ###

from bisect import bisect_left
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort()
a=a[:bisect_left(a,K)]
d=[False]*(K)
d[0]=True
curr_max=0
ans=len(a)
for i,a in reversed(list(enumerate(a))):
  if curr_max+a>=K:
    ans=i
  c=curr_max
  for j in range(curr_max+1)[::-1]:
    if j+a<K and d[j]:
      d[j+a]=True
      c=max(c,j+a)
  curr_max=c
print(ans)
### BUGGY CODE ###

import heapq
N, M = map(int, input().split())
h = []
for i in input().split():
    heapq.heappush(h, int(i))

for i in range(M):
    b, c = map(int, input().split())
    for j in range(b):
        a = heapq.heappushpop(h, c)
        if a == c:
            break
print(sum(h))



### FIXED CODE ###

import heapq
N, M = map(int, input().split())
h = []
for i in input().split():
    heapq.heappush(h, int(i))
data = [list(map(int, input().split())) for _ in range(M)]
data = sorted(data, reverse=1, key=lambda x: x[1])
for b, c in data:
    for j in range(b):
        a = heapq.heappushpop(h, c)
        if a == c:
            print(sum(h))
            exit()
print(sum(h))
### BUGGY CODE ###


def resolve():
    INF = 1<<60
    H, N = map(int, input().split())
    A, B = [], []
    for i in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

    dp = [[INF]*(H+1) for _ in range(N+1)]
    for i in range(N):
        dp[i][0] = 0

    for i in range(N):
        for j in range(H+1):
            if j < A[i]:
                # 体力がマイナスなっても魔法は使用できる
                dp[i + 1][j] = min(dp[i][j], B[i])
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - A[i]] + B[i])

    print(dp[N][H])

if __name__ == "__main__":
    resolve()


### FIXED CODE ###


def resolve():
    INF = 1<<60
    H, N = map(int, input().split())
    A, B = [], []
    for i in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

    dp = [[INF]*(H+1) for _ in range(N+1)]
    dp[0][0] = 0

    for i in range(N):
        for j in range(H+1):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            dp[i+1][min( j + A[ i ], H)] = min(dp[i+1][min( j + A[ i ], H)], dp[i+1][j] + B[i])
    print(dp[N][H])


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

def main():
    N = int(input())
    a = list(map(int, input().split()))
    # 互いにできるだけ点数を高くしたい
    # 単に先頭と末尾を比較して大きい方を選択した場合には、選択した要素の次の要素のほうが大きい場合がある
    # dp[i][j]で左からi番目からj-1番目までだけ残っている場合にそこからとり得る最大値を考える
    # dp[0][0]

    dp = [[0 for i in range(N)] for j in range(N)]

    for i in range(N):
        dp[i][i] = a[i]

    for i in range(N-1, -1, -1):
        for j in range(i+1, N):
            right = a[i] - dp[i+1][j]
            left = a[j] - dp[i][j-1]
            if right > left:
                dp[i][j] = right
            else:
                dp[i][j] = left
    # print(dp)
    print(dp[0][N-1])


main()


### FIXED CODE ###

def main():
    N = int(input())
    a = list(map(int, input().split()))
    # 互いにできるだけ点数を高くしたい
    # 単に先頭と末尾を比較して大きい方を選択した場合には、選択した要素の次の要素のほうが大きい場合がある
    # dp[i][j]で左からi番目からj-1番目までだけ残っている場合にそこからとり得る最大値を考える
    # dp[0][0]

    dp = [[0 for i in range(N)] for j in range(N)]

    for i in range(N):
        dp[i][i] = a[i]

    for i in range(N-1, -1, -1):
        for j in range(i+1, N):
            right = a[i] - dp[i+1][j]
            left = a[j] - dp[i][j-1]
            if right > left:
                dp[i][j] = right
            else:
                dp[i][j] = left
    # print(dp)
    print(dp[0][N-1])


main()
### BUGGY CODE ###

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

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

ans = 0
seat = [[min(i, j, n-i-1, n-j-1) for j in range(n)] for i in range(n)]
reserved = [[True for j in range(n)] for i in range(n)]

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

for i in range(n**2):
    v = p[i]-1
    x, y = v//n, v % n
    reserved[x][y] = False
    ans += seat[x][y]
    q = [(x, y)]
    while q:
        x, y = q.pop()
        for dx, dy in vec:
            x1 = x+dx
            y1 = y+dy
            if 0 <= x1 < n and 0 <= y1 < n and seat[x1][y1] > seat[x][y] + reserved[x][y]:
                seat[x1][y1] = seat[x][y] + reserved[x][y]
                q.append((x1, y1))

print(ans)


### FIXED CODE ###

n = int(input())
p = [int(x) for x in input().split()]

ans = 0
seat = [[min(i, j, n-i-1, n-j-1) for j in range(n)] for i in range(n)]
reserved = [[True for j in range(n)] for i in range(n)]

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

for i in range(n**2):
    v = p[i]-1
    x, y = v//n, v % n
    reserved[x][y] = False
    ans += seat[x][y]
    q = [(x, y)]
    while q:
        x, y = q.pop()
        if 0 <= x+1 < n and 0 <= y < n and seat[x+1][y] > seat[x][y] + reserved[x][y]:
            seat[x+1][y] = seat[x][y] + reserved[x][y]
            q.append((x+1, y))
        if 0 <= x-1 < n and 0 <= y < n and seat[x-1][y] > seat[x][y] + reserved[x][y]:
            seat[x-1][y] = seat[x][y] + reserved[x][y]
            q.append((x-1, y))
        if 0 <= x < n and 0 <= y+1 < n and seat[x][y+1] > seat[x][y] + reserved[x][y]:
            seat[x][y+1] = seat[x][y] + reserved[x][y]
            q.append((x, y+1))
        if 0 <= x < n and 0 <= y-1 < n and seat[x][y-1] > seat[x][y] + reserved[x][y]:
            seat[x][y-1] = seat[x][y] + reserved[x][y]
            q.append((x, y-1))


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

#!/usr/bin/env python3
import sys
import numpy as np


input = sys.stdin.readline
mod = 998244353


def I():
    return int(input())


def MI():
    return map(int, input().split())


def main(N, steps):
    dp = np.zeros(N, np.int64)
    dp[0] = 1

    for i in range(N):
        steps = steps[steps < N]
        dp[steps] += dp[i]
        dp[steps] %= mod
        steps += 1

    return dp[N - 1]


N, K = MI()

steps = []
for _ in range(K):
    l, r = MI()
    steps += list(range(l, r + 1))

steps = np.array(steps)

print(main(N, steps))


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

# import numba
# from numba import njit, b1, i4, i8, f8

input = sys.stdin.readline
mod = 998244353


def I():
    return int(input())


def MI():
    return map(int, input().split())


# @njit((i8, i8[:]), cache=True)
def main(N, steps):
    dp = np.zeros(N + 1, np.int64)
    dpsum = np.zeros(N + 1, np.int64)
    dp[1] = 1
    dpsum[1] = 1
    for i in range(2, N + 1):
        for l, r in steps:
            li = i - r
            ri = i - l
            if ri < 0:
                continue
            li = max(li, 1)
            dp[i] += dpsum[ri] - dpsum[li - 1]
            dp[i] %= mod
        dpsum[i] = dpsum[i - 1] + dp[i]
        dpsum[i] %= mod

    return dp[N]


N, K = MI()

steps = []
for _ in range(K):
    l, r = MI()
    steps.append((l, r))


print(main(N, steps))
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
dp = [False]*(k+1)
for i in range(1,k+1):
    for j in range(n):
        if i-a[j]<0:
            break
        if dp[i-a[j]]==False:
            dp[i] = True
if dp[k]==True:
    print("First")
else:
    print("Second")


### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
dp = [False]*(k+1)
for i in range(1,k+1):
    for j in range(n):
        if i-a[j]<0:
            break
        if dp[i-a[j]]==False:
            dp[i] = True
            break
if dp[k]==True:
    print("First")
else:
    print("Second")
### BUGGY CODE ###

n = int(input())
prices = list(map(int,input().split()))
stock_num = 0
cash = 1000

for i in range(n-1):
    if prices[i+1] >= prices[i]:
        while cash >= prices[i]:
            cash -= prices[i]
            stock_num += 1
    else:
        while stock_num != 0:
            cash += prices[i]
            stock_num -=1

while stock_num != 0:
    cash += prices[n-1]
    stock_num -=1

print(cash)


### FIXED CODE ###

n = int(input())
prices = list(map(int,input().split()))
stock_num = 0
cash = 1000

for i in range(n-1):
    if prices[i+1] >= prices[i]:
        temp = cash // prices[i]
        cash -= prices[i]*temp
        stock_num += temp
    else:
        cash += stock_num*prices[i]
        stock_num = 0

cash += stock_num*prices[n-1]
stock_num = 0

print(cash)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

    INF = 10 ** 18

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

    dp = [INF] * (H + 1)
    dp[0] = 0

    for i in range(N):
        A, B = map(int, input().split())
        for j in range(H + 1):
            if j < A:
                dp[j] = min(dp[j], dp[0] + B)
            else:
                dp[j] = min(dp[j], dp[j - A] + B)
        
    print (dp[H])

    # for d in dp:
    #     print (d)

if __name__ == '__main__':
    main()

### FIXED CODE ###

INF = 10 ** 18


H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [[INF] * (H + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(H + 1):
        if j < AB[i][0]:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][0] + AB[i][1])
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - AB[i][0]] + AB[i][1])
    
print (dp[N][H])

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

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

# if min(A[0],A[-1])+k
for _ in range(k):
    # finish=True
    start=[0]*n
    end=[0]*n
    
    for i in range(n):
        start[max(0,i-A[i])]+=1
        end[min(n-1,i+A[i])]+=1
    if start[0]==n:
        break
    # update ans
    cnt=0
    for i in range(n):
        cnt+=start[i]
        A[i]=cnt
        cnt-=end[i]

print(*A)

### FIXED CODE ###

import sys
from itertools import accumulate
input=sys.stdin.buffer.readline

def main():
    n, k = map(int, input().split())
    A = [*map(int, input().split())]
    
    # for _ in range(min(k,int(math.log(n,2)))):
    
    for _ in "_"*k:
        b=[0]*(n)
        
        for i,v in enumerate(A):
            if i>v:
            # b[max(0,i-v)]+=1
                b[i-v]+=1
            else:
                b[0]+=1
            j=i-~v
            # if i+v+1<n:
            #     b[i+v+1]-=1
            if j<n:
                b[j]-=1
        
        # update ans
        # cnt=0
        # for i in range(1,n):
        #     b[i]+=b[i-1]
        A=[*accumulate(b)]
        
        if min(A)==n:
            break
    print(" ".join(map(str,A)))

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

# -*- coding: utf-8 -*-
"""
Created on Wed Aug  8 14:35:24 2018

@author: sugawara
"""

N = int(input())
A = [int(i) for i in input().split()]
#N = 6
#A = [-679, -2409, -3258, 3095, -3291, -4462]
# iからi+1への移動距離
delta_A = [abs(A[0])] + [abs(A[i] - A[i-1]) for i in range(1, N)]

#i番目を抜かしたときの
delta_A_1skip = [abs(A[1])] + [abs(A[i+1] - A[i-1]) for i in range(1, N-1)] + [abs(A[N-2])]

res = []
for i in range(N):
    # i番目を抜いた場合を考える
    tmp_delta_A = delta_A[:i] + [delta_A_1skip[i]] + delta_A[i+2:]
    if i != N-1:
        tmp_delta_A.append(abs(A[-1]))
    res.append(sum(tmp_delta_A))
#    break
    
for i in range(N):
    print(res[i])

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Aug  8 14:35:24 2018

@author: sugawara
"""


N = int(input())
A = [int(i) for i in input().split()]
#N = 6
#A = [-679, -2409, -3258, 3095, -3291, -4462]
#N = 3
#A = [3, 5, -1]

# iからi+1への移動距離
delta_A = [abs(A[0])] + [abs(A[i] - A[i-1]) for i in range(1, N)] + [abs(A[-1])]
sum_of_all = sum(delta_A)

A = [0] + A + [0]
res = []
for i in range(N):
    res.append(sum_of_all - abs(A[i+1] - A[i]) - abs(A[i+2] - A[i+1]) + abs(A[i+2] - A[i]))
    
    
for i in range(N):
    print(res[i])
### BUGGY CODE ###

import bisect

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

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

A.sort()

for i in range(M):
    B, C = list(map(int,input().split()))
    in_idx = min(B,bisect.bisect_right(A,C))
    A = [C]*in_idx + A[in_idx:]
    A.sort()

print(sum(A))

### FIXED CODE ###

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

A = [-1]
A += list(map(int,input().split()))
A.sort()

BC = [[1,-1]]

for i in range(M):
    BC.append(list(map(int,input().split())))

BC = sorted(BC, key=lambda x: x[1])


x = 0

for i in range(N):
    if A[-1] > BC[-1][1]:
        x += A.pop()
        
    else:
        x += BC[-1][1]
        BC[-1][0] -= 1
        if BC[-1][0] == 0:
            BC.pop()

print(x)
### BUGGY CODE ###

alp = {"a":2, "b":3,"c":5,"d":7,"e":11,"f":13,"g":17,"h":19,"i":23,"j":29,
       "k":31,"l":37,"m":41,"n":43,"o":47,"p":53,"q":59,"r":61,"s":67,"t":71,
       "u":73,"v":79,"w":83,"x":89,"y":97,"z":1.5}

n = int(input())

s = []

for i in range(n):
    tss= str(input()) # tss; temporary str s
    ts = 1
    for j in range(10):
      ts *= alp[tss[j]] # ts; temporary s
    s.append(ts)

a = 0 # a; pre ans

for i in range(n):
    for j in range(1, n - i):
        if s[i] == s[i + j]:
            a += 1

print(a)  


### FIXED CODE ###

n = int(input())
d = dict()

for _ in range(n):
    s = "".join(sorted([x for x in input()]))
    d[s] = d.get(s, 0) + 1

ans = 0

for v in d.values():
    if v >= 2:
        ans += (v * (v-1)) // 2

print(ans)