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

import numpy as np

n = int(input())
l = list(map(int, input().split()))
count = 0
for i in range(n - 2):
    for j in range(i + 1 , n - 1):
        l_np = np.array(l[j + 1:n])
        count += np.count_nonzero((l_np > abs(l[i] - l[j])) & (l_np < l[i] + l[j]))
print(count)

'''
print("")
print("i=" +str(i)+ ", j=" + str(j))
print("l[i]=" + str(l[i]) + ", l[j]" + str(l[j]))
print("差 = " + str(abs(l[i] - l[j])) + ", 和 = " + str(l[i] + l[j]))
print("計算対象 = " + str(l_np))
print("個数 = " + str(np.count_nonzero((l_np > abs(l[i] - l[j])) & (l_np < l[i] + l[j]))))
'''





### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int,input().split()))
l.sort()

count = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        k = bisect.bisect_left(l, l[i] + l[j])
        count += k - j - 1
print(count)
### BUGGY CODE ###

s = input()
K = int(input())
sub = set()
length = len(s)
for i in range(length):
    for j in range(i + 1, length + 1):
        sub.add(s[i:j])
ans = list(sub)
ans.sort()
print(ans[K - 1])

### FIXED CODE ###

s = input()
K = int(input())
sub = set()
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        if j - i > 5:
            break
        sub.add(s[i:j])
sub = list(sub)
sub.sort()
print(sub[K-1])
### BUGGY CODE ###

import math
r,g,b,n = [int(u) for u in input().split(" ")]
i = 0
for ir in range(math.floor(n/r)+1):
  if ir*r>n:
    break
  for ig in range(math.floor(n/g)+1):
    if ig*g>n:
      break
    y = n- (ir*r+ig*g)
    if y<0:
      break
    if y>=0 and y%b==0:
      #print(ir,ig,y/b)
      i+=1
print(i)

### FIXED CODE ###

import math
r,g,b,n = [int(u) for u in input().split(" ")]
i = 0
for ir in range(math.floor(n/r)+1):
  if ir*r==n:
    i+=1
    break
  elif ir*r>n:
    break
  for ig in range(math.floor(n/g)+1):
    y = n - (ir*r+ig*g)
    if y<0:
      break
    if y%b==0:
      #print(ir,ig,y/b)
      i+=1
      continue
print(i)
### BUGGY CODE ###

import sys

(n) = map(int, sys.stdin.readline().strip().split())
list_input = list(map(int, input().split()))

anti_ans = 0
list_a = list_input.copy()
for i in list_input:
    for iloop in range(len(list_a)-1):
        if i % list_a[iloop+1] == 0:
            anti_ans += 1
            break
    a = list_a.pop(0)
    list_a.append(a)
print(len(list_input) - anti_ans)


### FIXED CODE ###

import sys

n = int(input())
list_input = list(map(int, sys.stdin.readline().split()))

list_input.sort()

# 倍数判断用のリストを作成
list_div = [0]*(max(list_input))

for i in list_input:
    # print(i)
    a = list_div[i-1]
    # list_div[i-1::i] = [1]*(len(list_div[i-1::i]))
    list_div[i-1::i] = map(lambda x: x+1, list_div[i-1::i])
    if a == 1:
        pass
    else:
        # list_div[i-1] = 0
        pass

ans = 0
for i in list_input:
    if list_div[i-1] == 1:
        ans += 1

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

from itertools import combinations

def solve(N, K, XYs):
    ans = 10 ** 19 + 1
    Ys = [y for x, y in XYs]
    Xs = [x for x, y in XYs]
    for y1, y2 in combinations(Ys, r=2):
        for x1, x2 in combinations(Xs, r=2):
            y1, y2 = min(y1, y2), max(y1, y2)
            x1, x2 = min(x1, x2), max(x1, x2)
            if len([(x, y) for x, y in XYs if x1 <= x <= x2 and y1 <= y <= y2]) >= K:
                ans = min(ans, abs(y2 - y1) * abs(x2 - x1))
    return ans


if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    XYs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, K, XYs))


### FIXED CODE ###


def solve(N, K, XYs):
    ans = 10 ** 19 + 1

    XYs.sort(key=lambda x: x[0])
    for i in range(N):
        for j in range(i+K-1, N):
            narrowedXY = XYs[i:j+1]
            narrowedXY.sort(key=lambda x: x[1])
            for y1 in range(len(narrowedXY)):
                for y2 in range(y1+K, len(narrowedXY)+1):
                    min_x = XYs[i][0]
                    max_x = XYs[j][0]
                    ys = [xy[1] for xy in narrowedXY[y1:y2]]
                    max_y = max(ys)
                    min_y = min(ys)
                    ans = min(ans, abs(max_x - min_x) * abs(max_y - min_y))

    return ans

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    XYs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, K, XYs))
### BUGGY CODE ###

N = int(input())
cnt = N+1-2
for i in range(1,N//2):
    if N%i == 0:
        if cnt > i+N//i-2:
            cnt = i+N//i-2
    if cnt == N**(0.5) * 2 -2:
        break
print(cnt)

### FIXED CODE ###

N = int(input())
cnt = N+1-2
for i in range(1,int(N**0.5)+1):
    if N%i == 0:
        if cnt > i+N//i-2:
            cnt = i+N//i-2
    if cnt == N**(0.5) * 2 -2:
        break
print(cnt)
### BUGGY CODE ###

from math import factorial

s = input()
array = [0]*(len(s)+1)
mod = 2019

for i in range(len(s)):
    array[i] = int(s[i:len(s)]) % mod
    
array[len(s)] = 0

array.sort()

cnt = 0
w = 1

for i in range(0, len(array)-1):
    if array[i] == array[i+1]:
        w += 1
    else:
        if w > 2:
            cnt += factorial(w) / (factorial(2)*factorial(w - 2))
            w = 1
        elif w == 2:
            cnt += 1
            w = 1
            
if w != 1:
    cnt += factorial(w) / (factorial(2)*factorial(w - 2))
    
print(int(cnt))

### FIXED CODE ###

s = input()
mod = 2019
array = [0]*(len(s)+1)

for i in range(len(s)):
    array[i+1] = (array[i] + pow(10,i,mod)*int(s[len(s)-(i+1)])) % mod
    

    
array.sort()

cnt = 0
w = 1

for i in range(0, len(array)-1):
    if array[i] == array[i+1]:
        w += 1
    else:
        if w >= 2:
            cnt += w*(w-1)/2
            w = 1
            
if w != 1:
    cnt += w*(w-1)/2
    
print(int(cnt))
### BUGGY CODE ###

n=int(input())
l = list(map(int,input().split()))	
l.sort()
ans=0
if l[0]+l[1]>l[n-1]:
    print((n*(n-1)*(n-2))//6)
    exit()
else:
    for i in range(n-2):
        for j in range(n-i-2):
            j+=i+1
            for k in range(n-j-1):
                k+=j+1
                if l[i]+l[j]>l[k]:
                    ans+=1
                else:
                    break
print(ans)


### FIXED CODE ###

def main():
    n = int(input())
    l = list(map(int,input().split()))
    l.sort()
    l.append(10**7)
    ans=0

    for i in range(n-2):
        for j in range(i+1,n-1):
            ok=j
            ng=n
            while ng-ok>1:
                mid = (ok + ng)//2
                if l[mid] < l[i] + l[j]:
                    ok=mid
                else:
                    ng=mid  
            ans+=ok-j
            
    print(ans)

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

import math

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

max_value = 0

for i in range(1, N+1):
    tmp =  math.floor(A*i/B) - A* math.floor(i/B)
    if tmp >= max_value:
        max_value = tmp

    
print(max_value)

### FIXED CODE ###

import math

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

max_value = 0
n = min(N, B-1)

max_value =  math.floor(A*n/B) - A* math.floor(n/B)


    
print(max_value)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
D = {}
for i in range(M):
  B, C = map(int, input().split())
  if C in D:
    D[C] += B
  else:
    D[C] = B
sorted(D, reverse=True)
S = 0
for i in range(N):
  if D != {}:
    M = max(j for j in D)
  else:
    M = 0
  if A[i] <= M:
    S += M
    D[M] -= 1
    if D[M] == 0:
      del D[M]
  else:
    S += A[i]
print(S)

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
D = []
for i in range(M):
  B, C = map(int, input().split())
  D.append([C, B])
D.sort(reverse=True)
E = []
j = 0
for i in range(N):
  if j < M:
    if D[j][1] == 0:
      j += 1
    if j == M:
      E.append(0)
    else:
      E.append(D[j][0])
      D[j][1] -= 1
  else:
    E.append(0)
S = 0
for i in range(N):
  S += max(A[i], E[i])
print(S)
### BUGGY CODE ###

A,B,C,K = map(int, input().split())
MAX = 10**18
for i in range(K):
    temp_a = A
    temp_b = B
    temp_c = C
    A = temp_b + temp_c
    B = temp_a + temp_c
    C = temp_a + temp_b
if abs(A-B) > MAX:
    print("Unfair")
else:
    print(A-B)

### FIXED CODE ###

A,B,C,K = map(int, input().split())
MAX = 10**18
if abs(A-B) > MAX:
    print("Unfair")
elif K%2:
    print(B-A)
else:
    print(A-B)
### BUGGY CODE ###

from collections import deque

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

Map = [[-1] * W for i in range(H)]

d = deque([])
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      Map[i][j] = 0
      d.append([i, j])

ans = 0
while d:
  x, y = d.popleft()
  dist = Map[x][y]
  for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
    u, v = x + dx, y + dy
    if 0<=u<H and 0<=v<W and Map[u][v]==-1:
      Map[u][v] = dist + 1
      ans = max(ans, dist + 1)
      d.append([u, v])

print(ans)

### FIXED CODE ###

from collections import deque

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

Map = [[-1] * W for i in range(H)]

d = deque([])
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      Map[i][j] = 0
      d.append([i, j])

ans = 0
while d:
  x, y = d.popleft()
  dist = Map[x][y]
  for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
    u, v = x + dx, y + dy
    if 0<=u<H and 0<=v<W and Map[u][v]==-1:
      Map[u][v] = dist + 1
      ans = max(ans, dist + 1)
      d.append([u, v])

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

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

CSUM = [0 for _ in range(N)]
CSUM[0] = A[0]
for i in range(1,N):
  CSUM[i] = CSUM[i-1] + A[i]
#print(CSUM)
def csum(i,j):
  if i == 0:
    return CSUM[j]
  else:
    return CSUM[j]-CSUM[i-1]

dp = [[0 for _ in range(N)] for _ in range(N)]

for k in range(1,N):
  for i in range(N-k):
    j = i+k
    tmp = 10**10
    for l in range(i,j):
      tmp = min(tmp,dp[i][l]+dp[l+1][j])
    dp[i][j] = tmp + csum(i,j)

print(dp[0][N-1])
#print(dp)


### FIXED CODE ###

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

CSUM = [0 for _ in range(N)]
CSUM[0] = A[0]
for i in range(1,N):
  CSUM[i] = CSUM[i-1] + A[i]
#print(CSUM)
def csum(i,j):
  if i == 0:
    return CSUM[j]
  else:
    return CSUM[j]-CSUM[i-1]

dp = [[0 for _ in range(N)] for _ in range(N)]

for k in range(1,N):
  for i in range(N-k):
    j = i+k
    tmp = 10**18
    for l in range(i,j):
      tmp = min(tmp,dp[i][l]+dp[l+1][j] + csum(i,j))
    dp[i][j] = tmp

print(dp[0][N-1])
#print(dp)
### BUGGY CODE ###

#D
import numpy as np
import math
def power(x, y, mod):
    if y == 0:
        t = 1
    elif y == 1:
        t = x % mod
    elif y % 2 == 0:
        t = (power(x, int(y/2), mod) ** 2) % mod
    else:
        t = (x * (power(x, int(y/2), mod) ** 2)) % mod
    return t
    
    
def frac_mod(n, mod, f=1):
    for i in range(1, n + 1):
        f = (f * i) % mod
    return f

def ifrac_mod(n, mod, f_inv=1):
    for i in range(n, 1, -1):
        f_inv = (f_inv * power(i, mod-2, mod)) % mod
    return f_inv

def cmb_mod(n, r, mod):
    n_frac = frac_mod(n, mod)
    n_r_ifrac = ifrac_mod(n-r, mod)
    r_ifrac = ifrac_mod(r, mod)
    
    return int((n_frac * n_r_ifrac * r_ifrac) % mod)
mod = 10**9+7
x,y = map(int, input().split())
a = np.array([[1,2], [2,1]])
b = np.array([x,y])
res = np.linalg.solve(a,b)
is_ok = True
if not (res[0].is_integer() and res[1].is_integer()):
    is_ok = False
    ans = 0
x_res = int(res[0])
y_res = int(res[1])
if is_ok:
    ans = cmb_mod(x_res+y_res, x_res, mod)
print(ans)

### FIXED CODE ###

## D
import numpy as np
import math

def cmb(n, k, mod):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n-i)) % mod
 
    denominator = 1
    for i in range(1, k+1):
        denominator = (denominator * i) % mod
 
    return (numerator * pow(denominator, mod-2, mod)) % mod
    
    return int((n_frac * n_r_ifrac * r_ifrac) % mod)

mod = 10**9+7
x,y = map(int, input().split()) 
is_ok = True
b = (2 * x - y) / 3
a = x - 2 * b
if not (a.is_integer() and b.is_integer()):
    ans = 0
    is_ok = False
    
a = int(a)
b = int(b)
if a < 0 or b < 0:
    ans = 0
    is_ok = False
if is_ok:    
    ans = cmb(a+b, a, mod)
print(ans)
### BUGGY CODE ###

from fractions import Fraction
def solve(p, q, a, n):
    def _solve(f, n, m, s):
        if f < 0 or m > a or n < 0:
            return 0
        if f == 0:
            return 1
        return sum((_solve(f-Fraction(1, i), n-1, m*i, i) for i in range(s, a//m+1)), 0)
    return _solve(Fraction(p, q), n, 1, 1)
        
if __name__ == "__main__":
    while True:
        p, q, a, n = [int(i) for i in input().split()]
        if p == 0:
            break
        print(solve(p, q, a, n))

### FIXED CODE ###

from functools import lru_cache

@lru_cache(maxsize=1<<10)
def solve(p, q, a, n):
    def _solve(num, dem, d, m, s):
        if num == 0:
            return 1
        if d == 0:
            return 0
        if num * a // m < dem:
            return 0
        return sum((_solve(num*i-dem, dem*i, d-1, m*i, i)
                    for i in range(s, min(dem*n//num, a//m)+1)), 0)
    return _solve(p, q, n, 1, 1)

if __name__ == "__main__":
    ans = []
    while True:
        p, q, a, n = [int(i) for i in input().split()]
        if p == 0:
            break
        ans.append(solve(p, q, a, n))
    print(*ans, sep="\n")
### BUGGY CODE ###

n,m=map(int,input().split())
l,r=map(int,input().split())
lis=list(range(l,r+1))
ans=lis
for i in range(m-1):
    l,r=map(int,input().split())
    lis_=list(range(l,r+1))
    ans=list(set(lis)&set(lis_))
print(len(ans))

### FIXED CODE ###

#不十分だった
n, m = map(int, input().split())
l_max, r_min = 0, 10**5 + 1
for i in range(m):
    l, r = map(int, input().split())
    l_max = max(l_max, l)
    r_min = min(r_min, r)

print(max(r_min - l_max + 1, 0))
### BUGGY CODE ###

arr = input().split()
n = int(arr[0])
m = int(arr[1])

a = [0] * m
b = [0] * m

mat = [[0] * n for i in range(n)]

for i in range(m):
    tmp = input().split()
    a[i] = int(tmp[0])
    b[i] = int(tmp[1])
    mat[a[i]-1][b[i]-1] = 1
    #mat[b[i]-1][a[i]-1] = 1

path = []
for i in range(n):
    if mat[0][i] == 1:
        path.append(i)

flag = False
for i in range(len(path)):
        if mat[path[i]][n-1] == 1: 
            flag = True
            break

if flag == True:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
    

### FIXED CODE ###

arr = input().split()
n = int(arr[0])
m = int(arr[1])

x = []
y = []

for i in range(m):
    a,b = map(int, input().split())
    if a == 1:
        x.append(b)
    if b == n:
        y.append(a)

if len(set(x+y)) < len(x) + len(y):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

N, K = map(int, input().split())
h = [int(input()) for _ in range(N)]
h.sort()

ans = float('inf')
for i in range(N-K+1):
    ans = min(ans,h[i:i+K][-1]-h[i:i+K][0])
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for _ in range(N)]
h.sort()

ans = float('inf')
for i in range(N-K+1):
    ans = min(ans,h[i+K-1]-h[i])
print(ans)
### BUGGY CODE ###

import sys

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

ans=0

for i in range(N*(N-1)//2):
    stamina=[1]*N
    for g in range(N):
        if A[g]!=[] and stamina[g]==1 and stamina[A[g][0]-1]==1:
            if g+1 == A[A[g][0]-1][0]:
                _pop = A[g].pop(0)
                A[_pop-1].pop(0)
                stamina[g]=0
                stamina[_pop-1]=0
    ans+=1
    if A==[[] for n in range(N)]:
        print(ans)
        sys.exit()

print(-1)

### FIXED CODE ###

import sys
from collections import deque

N = int(input())
A = [deque([int(i) for i in input().split()]) for i in range(N)]

ans=0
empty = [deque() for i in range(N)]
pre_fight = set([i for i in range(N)])
record = set()

while True:
    for g in pre_fight:
        if A[g]!=deque():
            if g+1 == A[A[g][0]-1][0]:
                record.add(g)
                record.add(A[g][0]-1)
    if record==set():
        break
    else:
        for i in record:
            A[i].popleft()
    ans+=1
    pre_fight = record
    record = set()
    if A==empty:
        print(ans)
        sys.exit()

print(-1)
### BUGGY CODE ###

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

total_a = sum(a_list)
#約数の列挙
candidates = set()
for i in [a for a in range(1, total_a) if a * a <= total_a]:
    if total_a % i == 0:
        candidates.add(i)
        candidates.add(total_a // i)

ans = 1
for x in candidates:
    remainders = sorted(map(lambda a: a % x, a_list))
    total_r = sum(remainders)
    border = total_r // x
    need = sum(remainders[:(N - border)])
    if need <= K:
        ans = max(ans, x)
print(ans)


### FIXED CODE ###

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

total_a = sum(a_list)
#約数の列挙
candidates = set()
for i in range(1, total_a):
    if i * i > total_a:
        break
    if total_a % i == 0:
        candidates.add(i)
        candidates.add(total_a // i)

ans = 1
for x in candidates:
    remainders = sorted(map(lambda a: a % x, a_list))
    total_r = sum(remainders)
    border = total_r // x
    need = sum(remainders[:(N - border)])
    if need <= K:
        ans = max(ans, x)
print(ans)
### BUGGY CODE ###

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N = int(input())

V = [[0]*N for _ in range(N)]

for i in range(N-1):
    u,v,w = list(map(int, input().split()))
    V[u-1][v-1] = w

D = dijkstra(csr_matrix(V), directed=False, indices=0)
#print(D)

for d in D:
    if d % 2 == 0: #even
        print(0)
    else:
        print(1)


### FIXED CODE ###

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

import sys
#import numpy
#from collections import deque
sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

childsof = [[] for _ in range(N+1)]

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

distances = [-1]*(N+1)
distances[1] = 0

def dfs(i):
    childs = childsof[i]

    for c in childs:
        j = c[0]
        if distances[j] == -1:
            distances[j] = distances[i] + c[1]
            dfs(j)

dfs(1)

for d in distances[1:]:
    if d % 2 == 0: #even
        print(0)
    else:
        print(1)
### BUGGY CODE ###

N = int(input())
S = list(input())
S.append("a")
n = list(map(str,range(0,10)))
ans = 0
for i in n:
    for j in n:
        for k in n:
            num = i+j+k
            now = 0

            for l in range(N+1):
                if now == 3:
                    ans += 1
                    break
                if num[now] == S[l]:
                    now += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
S.append("a")
n = list(map(str,range(0,10)))
ans = 0
for i in n:
    for j in n:
        for k in n:
            num = i+j+k
            now = 0

            for l in range(N+1):
                if now == 3:
                    ans += 1
                    break
                if num[now] == S[l]:
                    now += 1
print(ans)
### BUGGY CODE ###

from collections import deque
N = int(input())
node = [[]for i in range(N)]
side = []
ans = [0]*(N-1)
watch = [0]*N
watch[0] = 1
for i in range(N-1):
    a,b = map(int,input().split())
    side.append([a-1,b-1])
    node[a-1].append(i)
    node[b-1].append(i)

K = max(len(i) for i in node)
print(K)

queue = deque([0])

while queue:
    q = queue.popleft()
    use = [0]*(K+1)
    for i in node[q]:
        use[ans[i]] = 1
    p = 1
    for i in node[q]:
        if ans[i] == 0:
            while use[p]:
                p += 1
            ans[i] = p
            use[p] = 1
            s = side[i]
            next = s[(s.index(q)+1)%2]
            if watch[next] == 0:
                queue.append(next)
                watch[next] = 1

for i in ans:
    print(i)

### FIXED CODE ###

from collections import deque
N = int(input())
node = [[]for i in range(N)]
side = []
count = [0]*N
ans = [0]*(N-1)
closed = [0]*N
for i in range(N-1):
    a,b = map(int,input().split())
    side.append([a-1, b-1])
    node[a-1].append(i)
    node[b-1].append(i)
    count[a-1] += 1
    count[b-1] += 1

K = max(count)
print(K)

queue = deque([[0,K+1]])


while queue:
    q,m = queue.popleft()
    p = 1
    for i in node[q]:
        if p == m:
            p += 1
        if ans[i] == 0:
            ans[i] = p
            s = side[i]
            next = s[(s.index(q)+1)%2]
            if closed[next] == 0:
                queue.append([next,p])
                closed[next] = 1
            p += 1

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

from collections import deque
def readinput():
    n=int(input())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    edges=[]
    for _ in range(n-1):
        a,b=map(int,input().split())
        edges.append((a,b))
        nList[a].append(b)
        nList[b].append(a)
    return n,nList,edges

def bfs(s,nList):
    #print(nList)
    WHITE=0
    GRAY=1
    BLACK=2
    status=[WHITE]*(n+1)
    parent=[0]*(n+1)
    color=[]
    maxcolor=0
    for i in range(n+1):
        color.append([0]*(n+1))
    Q=deque([])
    Q.append(s)
    while(len(Q)>0):
        u=Q.popleft()
        usedcolor=set()
        usedcolor.add(color[u][parent[u]])
        for t in nList[u]:
            if status[t]==WHITE:
                status[t]=GRAY
                parent[t]=u
                for col in range(1,n):
                    if col in usedcolor:
                        continue
                    color[u][t]=col
                    color[t][u]=col
                    usedcolor.add(col)
                    maxcolor=max(maxcolor,col)
                    break
                Q.append(t)
        status[u]=BLACK
        #print(u,usedcolor)
    return color, maxcolor


def main(n,nList,edges):
    color, maxcolor=bfs(1,nList)
    print(maxcolor)
    for a,b in edges:
        print(color[a][b])

if __name__=='__main__':
    n,nList,edges=readinput()
    main(n,nList,edges)


### FIXED CODE ###

from collections import deque
def readinput():
    n=int(input())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    edges=[]
    for _ in range(n-1):
        a,b=map(int,input().split())
        edges.append((a,b))
        nList[a].append(b)
        #nList[b].append(a)
    return n,nList,edges

def bfs(s,nList):
    #print(nList)
    WHITE=0
    GRAY=1
    BLACK=2
    status=[WHITE]*(n+1)
    parent=[0]*(n+1)
    color=[0]*(n+1)
    maxcolor=0
    Q=deque([])
    Q.append(s)
    while(len(Q)>0):
        u=Q.popleft()
        usedcolor=color[u]
        col=1
        for t in nList[u]:
            if status[t]==WHITE:
                status[t]=GRAY
                parent[t]=u
                if col==usedcolor:
                    col+=1
                color[t]=col
                Q.append(t)
                col+=1
        maxcolor=max(maxcolor,col-1)
        status[u]=BLACK
        #print(u,usedcolor)
    return color, maxcolor


def main(n,nList,edges):
    color, maxcolor=bfs(1,nList)
    print(maxcolor)
    for a,b in edges:
        print(color[b])

if __name__=='__main__':
    n,nList,edges=readinput()
    main(n,nList,edges)
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(n) for n in input().split()]
dp = [0]*n

dp[1] = abs(h[1]-h[0])
for i in range(2, n):
  dp[i] = min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1,min(i+1,k+1))])
  #for j in range(1,min(i+1,k+1)):
   # if j == 1:
    #  dp[i] = dp[i-1]+abs(h[i]-h[i-1])
    #print([i,j], dp[i-j]+abs(h[i]-h[i-j]), dp[i])
    #dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]))
#print(h)
print(dp[-1])

### FIXED CODE ###

def main():
  n, k = map(int, input().split())
  h = [int(n) for n in input().split()]
  dp = [0]*n
  for i in range(1, n):
    dp[i] = min([dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-k),i)])  
  print(dp[-1])

if __name__ == "__main__":
  main()