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

from collections import deque
import sys
imput = sys.stdin.readline


diff = ((0, 1), (0, -1), (1, 0), (-1, 0))
n = int(input())
p = list(map(int, input().split()))

cost = [0] * (n * n)
for i in range(n):
    for j in range(n):
        cost[i * n + j] = min(i, j, n - i - 1, n - j - 1)

occ = [True] * (n * n)
ans = 0
for start in p:
    start -= 1
    q = deque([start])
    ans += cost[start]
    occ[start] = False
    while q:
        ij = q.popleft()
        i, j = divmod(ij, n)
        for di, dj in diff:
            nxt_ij = (i + di) * n + (j + dj)
            if not(0 <= i + di < n and 0 <= j + dj < n):
                continue
            if not occ[ij] and cost[nxt_ij] > cost[ij]:
                    cost[nxt_ij] = cost[ij]
                    q.append(nxt_ij)
            elif cost[nxt_ij] > cost[ij] + 1:
                    cost[nxt_ij] = cost[ij] + 1
                    q.append(nxt_ij)

print(ans)

### FIXED CODE ###

from collections import deque
import sys
imput = sys.stdin.readline


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

cost = [0] * (n * n)
for i in range(n):
    for j in range(n):
        cost[i * n + j] = min(i, j, n - i - 1, n - j - 1)

occ = [True] * (n * n)
ans = 0
for start in p:
    start -= 1
    q = deque([start])
    ans += cost[start]
    occ[start] = False
    while q:
        ij = q.popleft()
        i, j = divmod(ij, n)

        nxt_ij = (i + 1) * n + j
        if not(0 <= i + 1 < n and 0 <= j < n):
             pass
        elif not occ[ij] and cost[nxt_ij] > cost[ij]:
            cost[nxt_ij] = cost[ij]
            q.append(nxt_ij)
        elif cost[nxt_ij] > cost[ij] + 1:
            cost[nxt_ij] = cost[ij] + 1
            q.append(nxt_ij)
              
        nxt_ij = (i - 1) * n + j
        if not(0 <= i - 1 < n and 0 <= j < n):
            pass
        elif not occ[ij] and cost[nxt_ij] > cost[ij]:
            cost[nxt_ij] = cost[ij]
            q.append(nxt_ij)
        elif cost[nxt_ij] > cost[ij] + 1:
            cost[nxt_ij] = cost[ij] + 1
            q.append(nxt_ij)

        nxt_ij = i * n + (j + 1)
        if not(0 <= i + 0 < n and 0 <= j + 1 < n):
            pass
        elif not occ[ij] and cost[nxt_ij] > cost[ij]:
            cost[nxt_ij] = cost[ij]
            q.append(nxt_ij)
        elif cost[nxt_ij] > cost[ij] + 1:
            cost[nxt_ij] = cost[ij] + 1
            q.append(nxt_ij)

        nxt_ij = i * n + (j - 1)
        if not(0 <= i < n and 0 <= j - 1 < n):
            pass
        elif not occ[ij] and cost[nxt_ij] > cost[ij]:
            cost[nxt_ij] = cost[ij]
            q.append(nxt_ij)
        elif cost[nxt_ij] > cost[ij] + 1:
            cost[nxt_ij] = cost[ij] + 1
            q.append(nxt_ij)
print(ans)
### BUGGY CODE ###

# ナイーブに総当たり
s = input()

cnt = 0

while True:
    i = s.find("ABC")
    if i == -1:
        break
    else:
        cnt += 1
        s = s[:i] + "BCA" + s[i+3:]
        continue

print(cnt)

### FIXED CODE ###

s = input()
s = s.replace("BC", "D")

cnt = 0
num_a = 0
for i in range(len(s)):
    if s[i] in ["B", "C"]:
        num_a = 0
    elif s[i] == "A":
        num_a += 1
    elif s[i] == "D":
        cnt += num_a

print(cnt)
### BUGGY CODE ###

import numpy as np
H,W,D = map(int,input().split())
a = [input().split() for l in range(H)]
Q = int(input())
b = [input().split() for l in range(Q)]
a = np.array(a)
b = np.array(b)
a = np.int64(a)
b = np.int64(b)
ans = []
for i in range(Q):
  syo = b[i,0]
  go = b[i,1]
  syouhi = 0
  while syo != go:
    c = np.where(a == syo)
    syo += D
    d = np.where(a == syo)
    syouhi += abs(c[0][0] - d[0][0]) + abs(c[1][0] - d[1][0])
  ans.append(syouhi)
for i in range(Q):
  print(ans[i])

### FIXED CODE ###

import numpy as np
H,W,D = map(int,input().split())
a = [input().split() for l in range(H)]
basyo = [[0,0] for i in range(H*W)]
for i in range(W):
  for j in range(H):
    basyo[int(a[j][i])-1] = [j,i]
Q = int(input())
b = [input().split() for l in range(Q)]
ans = []
memo = [0] * (H*W+1)
for i in range(D):
  while i < H*W:
    i += D
    if i >= H*W:
      break
    memo[i] = memo[i-D]  + abs(basyo[i][0] - basyo[i-D][0]) + abs(basyo[i-D][1] - basyo[i][1])
b = np.array(b)
b = np.int64(b)
for i in range(Q):
  syo = b[i,0]
  go = b[i,1]
  print(memo[go-1] - memo[syo-1])
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
s=set(a)
ans=0
for i in s:
    if a.count(i)%2==1:
        ans+=1
print(ans)


### FIXED CODE ###

import collections
n=int(input())
a=[int(input()) for i in range(n)]
s=set(a)
cnt=collections.Counter(a)
ans=0
for i in s:
    if cnt[i]%2==1:
        ans+=1
print(ans)
### BUGGY CODE ###

x, y, a, b, c = map(int, input().split())
arrayP = list(map(int, input().split()))
arrayQ = list(map(int, input().split()))
arrayR = list(map(int, input().split()))
arrayP.sort(reverse=True)
arrayQ.sort(reverse=True)
arrayR.sort(reverse=True)
arrayAns = []
for i in range(x):
    arrayAns.append(int(arrayP[i]))
for i in range(y):
    arrayAns.append(int(arrayQ[i]))
arrayAns.sort()
for i in range(len(arrayR)):
    if arrayAns[0] <= int(arrayR[i]):
        arrayAns[0] = int(arrayR[i])
        arrayAns.sort()
print(sum(arrayAns))


### FIXED CODE ###

x, y, a, b, c = map(int, input().split())
arrayP = list(map(int, input().split()))
arrayQ = list(map(int, input().split()))
arrayR = list(map(int, input().split()))
arrayP.sort(reverse=True)
arrayQ.sort(reverse=True)
arrayR.sort(reverse=True)
arrayAns = []
for i in range(x):
    arrayAns.append(int(arrayP[i]))
for i in range(y):
    arrayAns.append(int(arrayQ[i]))
arrayAns.sort()
for i in range(min(len(arrayR), len(arrayAns))):
    if arrayAns[i] <= int(arrayR[i]):
        arrayAns[i] = int(arrayR[i])
    else:
        break
print(sum(arrayAns))
### BUGGY CODE ###

import heapq


def main():
    N, M = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    heapq.heapify(A)
    for _ in range(M):
        B, C = list(map(int, input().split(' ')))
        for _ in range(B):
            heapq.heappushpop(A, C)
    print(sum(A))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N, M = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    updates = list()
    for _ in range(M):
        B, C = list(map(int, input().split(' ')))
        updates.append((B, C))
    updates.sort(key=lambda x: x[1], reverse=True)
    for B, C in updates:
        A.extend([C] * B)
        if len(A) > 2 * N:
            break
    A.sort(reverse=True)
    print(sum(A[:N]))


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

import itertools

N = int(input())
lst = [int(input()) for i in range(N)]
ans = 0
for i in range(1,N+1):
  c = itertools.combinations(lst, i)
  for j in c:
    num = sum(j)
    if (num > ans and num % 10 != 0):
      ans = num
print(ans)

### FIXED CODE ###

import itertools

N = int(input())
lst = [int(input()) for i in range(N)]
sum_lst = sum(lst)
ans = 0
if (sum_lst % 10 != 0):
  ans = sum_lst
else:
  for i in lst:
    if ((sum_lst - i) % 10 != 0):
      ans = max(ans,sum_lst - i)
print(ans)
### BUGGY CODE ###

import copy
h,w = map(int,input().split())
a = []
for i in range(h+2):
  a.append([2] * (w+2))
d = 0
for i in range(h):
  b = input()
  c = 0
  for k in b:
    if k == '.':
      a[i+1][c+1] = 0
      d += 1
    else:
      a[i+1][c+1] = 1
    c += 1
count = 0
while d != 0:
  count += 1
  d = 0
  b = copy.deepcopy(a)
  for i in range(h):
    for k in range(w):
      if a[i+1][k+1] == 0:
        if b[i][k+1] == 1 or b[i+2][k+1] == 1 or b[i+1][k] == 1 or b[i+1][k+2] == 1:
          a[i+1][k+1] = 1
        else:
          d += 1
print(count)


### FIXED CODE ###

h,w = map(int,input().split())
a1 = [[5000] * (w+2) for i in range(h+2)]
a2 = [['.'] * (w+2) for i in range(h+2)]
for i in range(h):
  a2[i+1][1:-1] = list(input())
for i in range(h):
  for j in range(w):
    if a2[i+1][j+1] == '#':
      a1[i+1][j+1] = 0
for i in range(w):
  for j in range(h):
    a1[j+1][i+1] = min(a1[j][i+1]+1,a1[j+1][i+1])
for i in range(w):
  for j in range(h):
    a1[h-j][i+1] = min(a1[h-j+1][i+1]+1,a1[h-j][i+1])
for i in range(h):
  for j in range(w):
    a1[i+1][j+1] = min(a1[i+1][j]+1,a1[i+1][j+1])
for i in range(h):
  for j in range(w):
    a1[i+1][w-j] = min(a1[i+1][w-j+1]+1,a1[i+1][w-j])
m = 0
for i in range(h):
  for j in range(w):
    m = max(m,a1[i+1][j+1])
print(m)
### BUGGY CODE ###

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

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


### FIXED CODE ###

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

count = 1
mini = P[0]
for i in range(1, N):
    if mini >= P[i]:
        count += 1
        mini = P[i]

print(count)
### BUGGY CODE ###

n, k = map(int, input().split())
if(n % k == 0):
  print(0)
else:
  while(True):
    if(abs(n - k) < n):
      n = abs(n - k)
    else:
      print(n)
      break

### FIXED CODE ###

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

print(min(n % k, k - n % k))
### BUGGY CODE ###

n, m, k = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

# print(n, m, k)
# print(a)
# print(b)

ans = set()
ans.add(0)
time_sum_a = 0
for i_n in range(0, n+1):
    if time_sum_a > k:
        break

    if i_n != 0:
        time_sum_a += a[i_n-1]
    time_sum_b = 0
    for i_m in range(0, m+1):
        if time_sum_a + time_sum_b > k:
            break
        if i_m != 0:
            time_sum_b += b[i_m-1]

        time_sum = time_sum_a + time_sum_b
        # print(i_n, a[:i_n], i_m, b[:i_m], time_sum, k)
        if time_sum <= k:
            # print(i_n, a[:i_n], i_m, sum(b[:i_m]), k)
            ans.add(i_n + i_m)

# print(ans)

print(list(ans)[-1])


### FIXED CODE ###

n, m, k = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

a = [0]
b = [0]
for i in range(len(A)):
    a.append(a[i] + A[i])

for i in range(len(B)):
    b.append(b[i] + B[i])


# print(a)
# print(b)

j_n = m
ans = 0

for i_n in range(len(a)):
    if a[i_n] > k:
        break

    while b[j_n] > k - a[i_n]:
        j_n -= 1

    ans = max(ans, i_n + j_n)

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

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

dp = [[0]*(W+1) for j in range(N+1)] # DPテーブルの作成

for i in range(N):
    for j in range(W+1):
        if j < w[i]: # 選ばない時
            dp[i+1][j] = dp[i][j]
        else: # 選ぶ時
            dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i])

print(dp[N][W])

### FIXED CODE ###

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

dp = [[0]*(W+1) for j in range(N+1)] # DPテーブルの作成

for i in range(N):
    for j in range(W+1):
        if j < w[i]: # 選ばない時
            dp[i+1][j] = dp[i][j]
        else: # 選ぶ時
            dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i])

print(dp[N][W])
### BUGGY CODE ###

from collections import deque

n=int(input())
command=[0 for i in range(n)]
k=[0 for i in range(n)]
k_queue= deque([])

for i in range(n):
    s=input()
    if s=="deleteFirst" or s=="deleteLast":
        command[i],k[i]=s,0
    else:
        command[i],k[i]=s.split()
    
    if command[i]=="insert":
        k_queue.appendleft(k[i])
    elif command[i]=="deleteFirst":
        k_queue.popleft()
    elif command[i]=="deleteLast":
        k_queue.pop()
    else:
        try: k_queue.remove(k[i])
        except ValueError: y=0
print( " ".join(map(str, k_queue)))









### FIXED CODE ###

from collections import deque
 
n=int(input())
command=[0 for i in range(n)]
k=[0 for i in range(n)]
k_queue= deque([])
 
for i in range(n):
    s=input()
    if s=="deleteFirst" or s=="deleteLast":
        command[i],k[i]=s,0
    else:
        command[i],k[i]=s.split()
     
for i in range(n):
    if command[i]=="insert":
        k_queue.appendleft(k[i])
    elif command[i]=="deleteFirst":
        k_queue.popleft()
    elif command[i]=="deleteLast":
        k_queue.pop()
    else:
        try: k_queue.remove(k[i])
        except ValueError: y=0
print( " ".join(map(str, k_queue)))
### BUGGY CODE ###

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

for i in range(M):
  index = A.index(max(A))
  A[index] = A[index]//2

print(sum(A))


### FIXED CODE ###

import sys
from heapq import heappush, heappop
input = sys.stdin.readline
N,M = map(int, input().split())
A = []
for a in input().split():
  heappush(A,-int(a))

for _ in range(M):
  tmp = heappop(A)
  heappush(A, -(-tmp//2))

print(-sum(A))
### BUGGY CODE ###

N=input()
List=list(N)
M=len(List)
ans=0
Mods=[0]*(M+1)
Sum=""
for i in range(M):
  Sum=List[M-i-1]+Sum
  Mods[M-i-1]=int(Sum)%2019
Mods.sort()

import collections
C=collections.Counter(Mods)
for j in range((Mods[M])):
  k=C[j]
  ans+=k*(k-1)/2
print(int(ans))

### FIXED CODE ###

S = input()[::-1]

#aのMOD求めるンゴ
MOD=2019
ls_rem_a=[]
d=1
for i in range(len(S)):
  ls_rem_a.append(int(S[i])*d%MOD)
  d = d*10%MOD

#次に累積和求めるンゴ
ls_rem_s=[0]
sum=0
for i in range(len(S)):
  sum+=ls_rem_a[i]
  sum%=MOD
  ls_rem_s.append(sum)

#最後にMODが同じやつの個数を調べるンゴ
from collections import Counter
C_rem = Counter(ls_rem_s)
ans=0
for i in C_rem.keys():
  n=C_rem[i]
  ans+=n*(n-1)//2
print(ans)
### BUGGY CODE ###

from sys import stdin
from sys import setrecursionlimit
import numpy as np

setrecursionlimit(10 ** 7)

n,k = map(int,stdin.readline().rstrip().split())
a = list(map(int,stdin.readline().rstrip().split()))
a = np.array(a,dtype=np.int64)
lamp= np.zeros(n,dtype=np.int64)

for i,j in enumerate(a):
    lamp[max(0,i-j):min(n+1,i+j+1)] += 1

if k == 1:
    print(*lamp)
    exit()

for _ in range(min(k-1,17)):
    b = np.zeros(n,dtype=np.int64)
    for i,j in enumerate(lamp):
        b[max(0,i-j):min(n+1,i+j+1)] += 1
    b[b>n] = n
    lamp = b.copy()

lamp[lamp>n] = n

print(*lamp)

### FIXED CODE ###

from itertools import accumulate
from copy import deepcopy

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0]*(n+1)

if k > 41:
    k = 41

for _ in range(k):
    b = [0]*(n+1)
    for i,j in enumerate(a):
        b[max(0,i-j)] += 1
        b[min(n,i+j+1)] -= 1
    a = list(accumulate(b))
    for i in range(n+1):
        if a[i] >= n:
            a[i] = n

print(*a[:-1])
### BUGGY CODE ###

import copy

N = int(input())
A = [int(input()) for _ in range(N)]

for i in range(N):
    tmp = A[i]
    A[i] = -1
    print(sorted(A,reverse=True)[0])
    A[i] = tmp

### FIXED CODE ###

import copy

N = int(input())
A = [int(input()) for _ in range(N)]

res = sorted(A,reverse=True)
for i in range(N):
    if A[i] == res[0]:
        print(res[1])
    else:
        print(res[0])
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
ans = 1
for r in range(N):
  ans *= A[r]
if ans > 1e18:
    ans = -1
print(ans)

### FIXED CODE ###

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

ans = 1
if 0 in A:
  print(0)
  exit()
  
for r in A:
  ans *= r
  if ans > 1e18:
      print(-1)
      exit()
      
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split(' '))
     
inf = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split(' '))
    inf[a-1].append(b-1)
    inf[b-1].append(a-1)
point = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, input().split(' '))
    point[p-1] += x
def add(num):
    for k in inf[num]:
        if k != num:
            point[k] += point[num]
            add(k)  
add(0)
print(*point)

### FIXED CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    from collections import deque
    sys.setrecursionlimit(10**7)

    visit = [True for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = deque()
    next_visit.append(0)
    visit[0] = False
    counter = 1
    while counter < n:
        t = next_visit.pop()
        for s in dic[t]:
            if visit[s]:
                point[s] += point[t]
                visit[s] = False
                counter += 1
                next_visit.append(s)
    print(*point)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

if B > N:
    result = int(A * N / B) - A * int(N / B)
    
else:
    tmp = 0
    result = 0
    for i in range(B - 1, N, B):
        tmp = int(A * i / B) - A * int(i / B)
        if result < tmp:
            result = tmp

print(result)

### FIXED CODE ###

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


if B > N:
    result = int(A * N / B) - A * int(N / B)
    
else:
    result = int(A * (B - 1) / B) - A * int((B - 1) / B)
    
print(result)
### BUGGY CODE ###

n,*l = map(int, open(0).read().split())

for i in range(n):
    min = 1001
    min_j = -1
    for j in range(i, n):
        if l[j] < min:
            min = l[j]
            min_j = j
    l[i], l[min_j] = l[min_j], l[i]
    
ans = 0
for i in range(n):
    for j in range(i+1, n):
        big = l[i]+l[j]
    
        ch_max = n
        ch_min = j+1
        
        while ch_min < ch_max:
            ch_i = (ch_min + ch_max) // 2
            if l[ch_i] < big:
                ch_min = ch_i + 1
            else:
                ch_max = ch_i
                
        big_i = ch_max
        
        ans += big_i - (j + 1)
                
print(ans)

### FIXED CODE ###

n = int(input())
l = sorted(map(int, input().split()))
 
ans = 0
for i in range(n):
    for j in range(i+1, n):
        big = l[i]+l[j]
    
        ch_max = n
        ch_min = j+1
        
        while ch_min < ch_max:
            ch_i = (ch_min + ch_max) // 2
            if l[ch_i] < big:
                ch_min = ch_i + 1
            else:
                ch_max = ch_i
                
        big_i = ch_max
        
        ans += big_i - (j + 1)
                
print(ans)
### BUGGY CODE ###

n=int(input())
s=input()
ans=0
for i in range(10):
  flag1=False
  for a in range(n-2):
    if s[a]==str(i):
      flag1=True
      break
  if flag1:
    for j in range(10):
      flag2=False
      for b in range(a+1,n-1):
        if s[b]==str(j):
          flag2=True
          break
      if flag2:
        for k in range(10):
          for c in range(b+1,n):
            if s[c]==str(k):
              flag3=True
              ans+=1
              break
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
ans=0
alist=[0]*10
for i in range(n):
  alist[int(s[i])]=i
for i in range(10):
  flag1=False
  for a in range(n-2):
    if s[a]==str(i):
      flag1=True
      break
  if flag1:
    for j in range(10):
      flag2=False
      for b in range(a+1,n-1):
        if s[b]==str(j):
          flag2=True
          break
      if flag2:
        for k in range(10):
          if b<alist[k]:
            ans+=1
print(ans)
### BUGGY CODE ###

def main():
    l, r = map(int, input().split())

    res = 2018
    for i in range(l, r):
        for j in range(l+1, r+1):
            mod = (i*j)%2019
            if mod < res:
                res = mod
            if res == 0:
                break
    print(res)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    l, r = map(int, input().split())

    res = 2018
    for i in range(l, r):
        for j in range(l+1, r+1):
            mod = (i*j)%2019
            if mod < res:
                res = mod
            if res == 0:
                break
        else:
            continue
        break
        
    print(res)


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

N = int(input())

s = [i for i in range(N)]
print(sum(s))

### FIXED CODE ###

N = int(input())

print(N*(N-1)//2)
### BUGGY CODE ###

from collections import deque, defaultdict
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        p, q, c = map(int, input().split())
        adj[p].append((q, c))
        adj[q].append((p, c))

    deq = deque()
    cost = [10 ** 7] * (N+1)
    seen = [defaultdict(int) for _ in range(N+1)]
    prev = defaultdict(list)
    deq.append(1)
    cost[1] = 0
    flag = [1] * (N+1)
    while deq:
        v = deq.pop()
        flag[v] = 1
        for uc in adj[v]:
            u, c = uc
            # print(v, u, c)
            # print(deq, prev, cost)
            # print(seen[4])
            if c in prev[v] and seen[u][c] == 0:
                if cost[u] == cost[v]:
                    prev[u].append(c)
                    if flag[u]:
                        deq.append(u)
                        flag[u] = 0
                elif cost[u] > cost[v]:
                    cost[u] = cost[v]
                    deq.append(u)
                    flag[u] = 0
                    prev[u] = [c]
                seen[v][c] = 1
            else:
                if cost[u] > cost[v] + 1:
                    cost[u] = cost[v] + 1
                    deq.appendleft(u)
                    flag[u] = 0
                    prev[u] = [c]
                elif cost[u] == cost[v] + 1:
                    prev[u].append(c)

    print(cost[N]) if cost[N] < 10 ** 7 else print(-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    c2v = {}
    v = N+1
    for _ in range(M):
        p, q, c = map(int, input().split())
        P = p*(10**7) + c
        Q = q*(10**7) + c
        if P not in c2v:
            c2v[P] = v
            adj[p].append((v, 1))
            adj.append([(p, 1)])
            v += 1
        if Q not in c2v:
            c2v[Q] = v
            adj[q].append((v, 1))
            adj.append([(q, 1)])
            v += 1
        adj[c2v[P]].append((c2v[Q], 0))
        adj[c2v[Q]].append((c2v[P], 0))

    que = deque()
    que.append(1)
    seen = [-1] * len(adj)
    seen[1] = 0
    while que:
        v = que.popleft()
        for u, cost in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + cost
                if cost:
                    que.append(u)
                else:
                    que.appendleft(u)
    print(seen[N] // 2)


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

N = 1
seg = []

def get(a, b, k, l, r):
    if r <= a or b <= l:
        return 0
    elif a <= l and r <= b:
        return seg[k]
    
    return get(a, b, k * 2 + 1, l, (l + r) // 2) + get(a, b, k * 2 + 2, (l + r) // 2, r)

def update(k, x):
    k += N - 1
    seg[k] += x

    while k > 0:
        k = (k - 1) // 2
        seg[k] = seg[k * 2 + 1] + seg[k * 2 + 2]
    
    return

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

a = [int(input()) for _ in range(n)]

v = [0]

for i in range(n):
    v.append(v[i] + a[i])

for i in range(n + 1):
    v[i] -= i * k

st = sorted(list(set(v)))
mp = {t:i for i, t in enumerate(st)}

while N < len(mp):
    N <<= 1

for i in range(N * 2 - 1):
    seg.append(0)

ans = 0

for i in range(n + 1):
    ans += get(0, mp[v[i]] + 1, 0, 0, N)
    update(mp[v[i]], 1)

print(ans)

### FIXED CODE ###

bit = [0 for _ in range(252525)]

def get(r):
    r += 1

    res = 0
    while r > 0:
        res += bit[r]
        r -= r & -r
    
    return res

def update(k, x):
    k += 1

    while k < 252525:
        bit[k] += x
        k += k & -k
    
    return

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

a = [int(input()) for _ in range(n)]

v = [0]

for i in range(n):
    v.append(v[i] + a[i])

for i in range(n + 1):
    v[i] -= i * k

st = sorted(list(set(v)))
mp = {t:i for i, t in enumerate(st)}

ans = 0

for i in range(n + 1):
    ans += get(mp[v[i]])
    update(mp[v[i]], 1)

print(ans)