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

def resolve():
    numbers = int(input())
    number_list = list(map(int, input().split()))
    answer = 0
    for i in range(numbers - 1):
        num1 = number_list[i]
        num2 = sum(number_list[i+1:])
        answer += num1*num2
    print(answer%1000000007)
resolve()

### FIXED CODE ###

def resolve():
    numbers = int(input())
    number_list = list(map(int, input().split()))
    answer = 0
    num2 = sum(number_list)
    for num1 in number_list:
        num2 = num2 - num1
        answer += num1*num2
    print(answer%1000000007)
resolve()
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            if j - i == k - j:
                continue
            if S[i] == S[j] or S[i] == S[k] or S[j] == S[k]:
                continue
            ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
r, g, b = 0, 0, 0
for c in S:
    if c == "R":
        r += 1
    elif c == "G":
        g += 1
    else:
        b += 1
ans = r * g * b
sub = 0
for i in range(N):
    for j in range(i+1, N):
        if S[i] == S[j]:
            continue
        k = 2 * j - i
        if k >= N or S[k] == S[i] or S[k] == S[j]:
            continue
        sub += 1
print(ans - sub)
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    H, N = map(int, readline().split())
    Magic = list(list(map(int, readline().split())) for _ in range(N))

    dp = [INF]*(H+1)
    dp[0] = 0
    for h in range(H):
        for damage, cost in Magic:
            next_index = min(h + damage, H)
            dp[next_index] = min(dp[next_index],dp[h]+cost)
    print(dp[-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    H, N = map(int, readline().split())
    Magic = list(list(map(int, readline().split())) for _ in range(N))

    dp = [INF]*(H+1)
    dp[0] = 0
    for h in range(H):
        for damage, cost in Magic:
            next_index = min(h + damage, H)
            dp[next_index] = min(dp[next_index],dp[h]+cost)
    print(dp[-1])

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

def main():
    import sys,heapq
    from collections import defaultdict
    input = sys.stdin.readline

    n,q = map(int,input().split())
    #used[i]:0より大きいならi
    used = defaultdict(int)
    tank = []

    p = []
    for i in range(n):
        s,t,x = map(int,input().split())
        p.append((s-x,x))
        p.append((t-x,-x))
    p.sort()

    cnt = 0
    for i in range(q):
        d = int(input())
        while cnt<=len(p)-1 and p[cnt][0] <= d:
            w = p[cnt][1]
            if w>=0:
                used[w] += 1
                heapq.heappush(tank,w)
            else:
                used[-w] -= 1
            cnt += 1
        while True:
            if len(tank) == 0:
                print(-1)
                break
            kouho = tank[0]
            if used[kouho] > 0:
                print(kouho)
                break
            else:
                heapq.heappop(tank)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys,heapq
    from collections import defaultdict
    input = sys.stdin.readline

    n,q = map(int,input().split())
    #used[i]:0より大きいならi
    used = defaultdict(int)
    tank = []

    p = []
    for i in range(n):
        s,t,x = map(int,input().split())
        p.append((s-x,x))
        p.append((t-x,-x))
    p.sort()

    cnt = 0
    for i in range(q):
        d = int(input())
        while cnt<=len(p)-1 and p[cnt][0] <= d:
            w = p[cnt][1]
            if w>=0:
                used[w] += 1
                heapq.heappush(tank,w)
            else:
                used[-w] -= 1
            cnt += 1
        while True:
            if len(tank) == 0:
                print(-1)
                break
            kouho = tank[0]
            if used[kouho] > 0:
                print(kouho)
                break
            else:
                heapq.heappop(tank)
if __name__ == '__main__':
    main()
### BUGGY CODE ###


S = input()
Q = int(input())

# print(S, Q)

queries = []
for i in range(Q):
    query = input()
    queries.append(query)



for query in queries:
    if query == "1":
        # print("reverse", S)
        S = S[::-1]
    else:
        t, f, c = query.split()
        # print(t, f, c)
        if f =="1":
            # print("append c to head of", S)
            S = c + S
        else:
            # print("append c to tail of ", S)
            S = S + c

print(S)

### FIXED CODE ###

S = input()
Q = int(input())

queries = []
for i in range(Q):
    query = input()
    queries.append(query)

from collections import deque
slist = deque(list(S))
even = True
for query in queries:
    if query == "1":
        even = not even
    else:
        t, f, c = query.split()
        if f == '1':
            if even:
                slist.appendleft(c)
            else:
                slist.append(c)
        else:
            if even:
                slist.append(c)
            else:
                slist.appendleft(c)
if not even:
    slist.reverse()

print(''.join(slist))
### BUGGY CODE ###

import numpy as np
N,a,b = np.array(input().split()).astype(int)
mod = 10**9+7
import math
def power(x, n):
    ans = 1
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            ans = ans*x%mod
        x = x*x%mod
        n = n >> 1 #ビットシフト
    return ans
def fact(m, n):
    val = 1
    for i in range(m, n + 1):
        val = (val*i)%mod
    return val
def cmb1(N, r):
    A = fact(N-r+1, N)
    B = math.factorial(r)
    return A, B, (A*power(B, mod-2))%mod
  
def cmb2(a, b, A, B):
    A = fact(N-a+1, N-b)*A
    B = fact(b+1, a)*B
    return (A*power(B, mod-2))%mod
if(a>N//2):
    a = N-a
if(b>N//2):
    b = N-b
tmp = max(a,b)
b = min(a,b)
a = tmp
A, B, K1 = cmb1(N, b)
K2 = cmb2(a, b, A, B)
print((power(2, N)-1-K1-K2)%mod)

### FIXED CODE ###

import numpy as np
N,a,b = np.array(input().split()).astype(int)
mod = 10**9+7
def power(x, n):
    ans = 1
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            ans = ans*x%mod
        x = (x*x)%mod
        n = n >> 1 #ビットシフト
    return ans
def fact(m, n):
    val = 1
    for i in range(m, n+1):
        val = val*i % mod
    return val
    
def cmb1(N, r):
    A = fact(N-r+1, N)%mod
    B = fact(1, r)%mod
    return A, B, (A*power(B, mod-2))%mod
def cmb2(a, b, A, B):
    A = fact(N-a+1, N-b)*A%mod
    B = fact(b+1, a)*B%mod
    return (A*power(B, mod-2))%mod
if(a>N//2):
    a = N-a
if(b>N//2):
    b = N-b
tmp = max(a,b)
b = min(a,b)
a = tmp
A, B, K1 = cmb1(N, b)
K2 = cmb2(a, b, A, B)
print((power(2, N)-1-K1-K2)%mod)
### BUGGY CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split())) + [0]*(k+1)
dp = [0] + [float("inf")] * (n+k+1)

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

print(dp[n-1])

### FIXED CODE ###

import numpy as np

n,k = list(map(int, input().split()))
h = np.array(list(map(int, input().split())))

dp = np.array([0] * n)

for i in range(1,n):
    s = max(i-k,0)
    dp[i] = min(dp[s : i] + abs(h[i] - h[s:i]))

print(dp[n-1])
### BUGGY CODE ###

from fractions import gcd
from sys import stdin

def main():
    mod = 10**9 + 7
    input = stdin.readline

    N = int(input())
    A = input().split()
    num = 1
    for n in A:
        num = (num*int(n))//gcd(num,int(n))

    t = 0
    for n in A:
        t = (t + num//int(n)) % mod
    print(t)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from fractions import gcd

def main():
    mod = 10**9 + 7

    N = int(input())
    A = input().split()
    AP = set(A)
    num = 1
    for n in AP:
        num = (num*int(n))//gcd(num,int(n))

    t = 0
    for n in A:
        t = (t + num//int(n))
    print(t%mod)


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

DEBUG = False


def get_pos(index):
    """初期位置indexのロボットのクエリ後の配置を返す
    is_whick_sideの返り値として返す"""
    if DEBUG: print()
    iws = -1 if index == -1 else 1 if index == N else 0
    if iws != 0:
        if DEBUG: print(iws)
        return iws
    for t, d in e:
        if DEBUG: print(index, s[index], t, d, end='')
        if t == s[index]:
            if d == 'R':
                index += 1
            else:
                index -= 1
        if DEBUG: print('->', index, s[index] if 0 <= index < N else '==Removed')
        iws = -1 if index == -1 else 1 if index == N else 0
        if iws != 0:
            if DEBUG: print(iws)
            return iws
    if DEBUG: print(0)
    return 0


N, Q = map(int, input().split())
s = input()

e = [input().split() for _ in range(Q)]
# t: 文字 <- siと比較
# d: 'L', 'R'

# right
left = -1
right = N
while right - left > 1:
    mid = (left + right) // 2
    if get_pos(mid) == 1:
        # 右消滅
        right = mid
    else:
        left = mid
    if DEBUG: print('lr', left, right)
ar = right
if DEBUG: print('right', ar)
# 右消滅開始位置

# left
left = -1
right = N
while right - left > 1:
    mid = (left + right) // 2
    if get_pos(mid) == -1:
        left = mid
    else:
        right = mid
    if DEBUG: print('lr', left, right)
al = left
if DEBUG: print('left', al)
# 左消滅開始位置
# (al, ar) = 残存区間

print((ar - 1) - (al + 1) + 1)


### FIXED CODE ###

"""https://atcoder.jp/contests/exawizards2019/submissions/4769434
左右どちらから消滅するか確認が必要だと気づかされた"""


def get_pos(index):
    """初期位置indexのロボットのクエリ後の配置を返す
    is_whick_sideの返り値として返す"""
    iws = -1 if index == -1 else 1 if index == N else 0
    if iws != 0:
        return iws
    for t, d in e:
        if t == s[index]:
            if d == 'R':
                index += 1
            else:
                index -= 1
        iws = -1 if index == -1 else 1 if index == N else 0
        if iws != 0:
            return iws
    return 0


N, Q = map(int, input().split())
s = input()

e = [input().split() for _ in range(Q)]
# t: 文字 <- siと比較
# d: 'L', 'R'

# right
left = -1
right = N
while right - left > 1:
    mid = (left + right) // 2
    if get_pos(mid) == 1:
        # 右消滅
        right = mid
    else:
        left = mid
ar = right
# 右消滅開始位置

# left
left = -1
right = N
while right - left > 1:
    mid = (left + right) // 2
    if get_pos(mid) == -1:
        left = mid
    else:
        right = mid
al = left
# 左消滅開始位置
# (al, ar) = 残存区間

print((ar - 1) - (al + 1) + 1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
l = [[] for _ in range(n+1)]
nn = []
for i in range(n-1):
    a,b = map(int,input().split())
    l[a].append(b)
    l[b].append(a)
    nn.append(b)

m = max(map(len,l)) 

co = [ set(range(1,m+1)) for _ in range(n+1)]

col = [0 for i in range(n+1)]
col[1] = 1

for i in range(1,n+1):
    for la in l[i]:
        if col[la] ==0:
            col[la] = co[i].pop()
            co[la].discard(col[la])
print(m)
for i in range(n-1):
    print(col[nn[i]])


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
l=[[]]
nn = []
for _ in range(n+1):
    l.append([])

for i in range(n-1):
    a,b = map(int,input().split())
    l[a].append(b)
    l[b].append(a)
    nn.append(b)

ml = list(map(len,l)) 
m = max(ml)
co = []
for i in range(n+1):
    co.append( set(range(1,ml[i]+1) ))

col = [0]*(n+1)
col[1] = 1

for i in range(1,n+1):
    for la in l[i]:
        if col[la] ==0:
            col[la] = co[i].pop()
            co[la].discard(col[la])
print(m)
for i in range(n-1):
    print(col[nn[i]])
### BUGGY CODE ###

def sol(k, S):
    maxi = 0
    for x in range(k+1):
        ttl = 0
        for s in S:
            ttl += (x ^ s)
        maxi = max(maxi, ttl)
    return maxi


test = False
if test:
    n, k = 3, 7
    S =list( map(int, "1 6 3".split()))
    print(sol(k, S))

    n, k = 4, 9
    S =list( map(int, "7 4 0 3".split()))
    print(sol(k, S))

    n, k = 1, 0
    S =list( map(int, "1000000000000".split()))
    print(sol(k, S))


else:
    n, k = map(int, input().split())
    S =list( map(int, input().split()))
    print(sol(k, S))


### FIXED CODE ###

#-*- coding: utf-8 -*-
"""
https://atcoder.jp/contests/abc117/tasks/abc117_a
"""

def sol_naive(k, S):
    maxi = 0
    for x in range(k+1):
        ttl = 0
        for s in S:
            ttl += (x ^ s)
        maxi = max(maxi, ttl)
    return maxi


def keta(x):
    if x <= 0:
        return 0
    else:
        return 1 + keta(int(x/2))

def bin(x):
    return "{0:08b}".format(x)

def rec(k, S, b_keta, ans): # which digit
    #print("rec(%s, %s, %s, %s)" % (k, S, b_keta, ans))
    if b_keta == 0:
        #print("miso")
        return ans
    else:
        #print("soup")
        ones = 0
        for s in S:
            #print("checking %s and %s" % (bin(s), bin(1 << (b_keta-1))))
            if (1 << (b_keta-1) & s) > 0:
                #print("it's 1")
                ones += 1
        if ones < len(S) - ones: # should be set 1 in this digit
            if ans + (1 << (b_keta-1)) <= k:
                ans += (1 << (b_keta-1))
            #print("ans updated %s" % ans)
            return rec(k, S, b_keta-1, ans)
        else:
            return rec(k, S, b_keta-1, ans)


def sol(k, S):
    maxi = max(S)
    b_keta = keta(k)
    #print("find maxi(%s) and it's digit is %s and k is (%s)" % (maxi, b_keta, k))
    x = rec(k, S, b_keta, 0)
    ans = 0
    for s in S:
        ans += (x ^ s)
    return ans

test = False
#test = True
if test:
    n, k = 3, 7
    S =list( map(int, "1 6 3".split()))
    print(sol(k, S))

    n, k = 4, 9
    S =list( map(int, "7 4 0 3".split()))
    print(sol(k, S))
    #
    n, k = 1, 0
    S =list( map(int, "1000000000000".split()))
    print(sol(k, S))


else:
    n, k = map(int, input().split())
    S =list( map(int, input().split()))
    print(sol(k, S))
### BUGGY CODE ###

a,b,c,d=map(int,input().split())
r1=a
r2=c
while r1!=0 and r2!=0:
  r2-=b
  r1-=d
if r2==0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a,b,c,d=map(int,input().split())
r1=a
r2=c
while r1>0 and r2>0:
  r2-=b
  r1-=d
if r2<=0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

N,K,Q = map(int,input().split())
A = [int(input())for i in range(Q)]
for i in range(1,N+1):
  x=A.count(i)
  if K-Q+x>=1:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

from collections import Counter
N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
count = Counter(A)
f_p = [K-Q]*N
for k,v in count.items():
  f_p[k-1] += v
  
for ans in f_p:
  if ans >= 1:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

# -*- coding utf-8 -*-
n=int(input())
x=1

for i in range(1,n+1,1):
    x=x*i

print(x%(10**9+7))


### FIXED CODE ###

# -*- coding utf-8 -*-
n=int(input())
ans=1

for i in range(1,n+1):
    ans=(ans*i)%(10**9+7)

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

import sys
input = sys.stdin.readline

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

for _ in range(m):
    l, r, d = [int(x) for x in input().split()]
    l -= 1
    r -= 1
    g[l].append([r, d])
    g[r].append([l, -d])

visited = [0] * n

for i in range(n):
    if visited[i] != 0:
        continue
    d = [0] * n
    d[i] = 0
    stack = [i]
    while stack:
        u = stack.pop()
        for v, d_ in g[u]:
            visited[v] = 1
            if d[v] == 0:
                d[v] = d[u] + d_
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
        if g[u] and v != i:
            stack.append(v)
print("Yes")


### FIXED CODE ###

n, m = map(int, input().split())
ed = [[] for _ in range(n)]  # グラフ
v = [None] * n
for _ in range(m):
  l, r, d = map(int, input().split())
  ed[l-1].append((r-1, d))  # l -> r
  ed[r-1].append((l-1, -d))  # r -> l

visited = [False] * n  # 訪問フラグ（非連結の可能性の為）

def dfs(start):
  s = [start]
  v[start] = 0
  while s:
    label = s.pop()
    if visited[label] == False:
      visited[label] = True
      for to, dist in ed[label]:
        if v[to] is None:
          v[to] = v[label] + dist
          s.append(to)
        else:
          if v[to] != v[label] + dist:
            return False
  return True

is_exist = True
for i in range(n):
  if v[i] is None:
    if not dfs(i):
      print('No')
      is_exist = False
      break
if is_exist:
  print("Yes")
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import networkx as nx

N, M, S = map(int, readline().split())

edges = []
for _ in range(M):
    u, v, a, b = map(int, readline().split())
    for coin in range(a, 2500):
        edges.append(((u, coin), (v, coin - a), b))
        edges.append(((v, coin), (u, coin - a), b))

for u in range(1, N + 1):
    c, d = map(int, readline().split())
    for coin in range(2500):
        edges.append(((u, coin), (u, min(coin + c, 2499)), d))

if S >= 2500:
    S = 2499


G = nx.DiGraph()
G.add_weighted_edges_from(edges)
path_lengths = nx.single_source_dijkstra_path_length(G, (1, S))

INF = 10 ** 18
answer = [INF] * (N + 1)
for key, L in path_lengths.items():
    u, c = key
    if answer[u] > L:
        answer[u] = L

print(*answer[2:], sep='\n')


### FIXED CODE ###

import sys
from heapq import *
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8, i8, i8[:, :], i8[:]), cache=True)
def main(N, S, G, CD):
    ind = np.searchsorted(G[:, 0], np.arange(N + 1), 'right')
    U = 2600
    C, D = CD[::2], CD[1::2]
    C = np.minimum(C, U)
    S = np.minimum(S, U)
    INF = 10**18
    dist = np.full((N + 1, U + 1), INF, np.int64)
    dist[1, S] = 0
    q = [(0, 1, S)]
    while q:
        d, v, coin = heappop(q)
        if dist[v, coin] < d:
            continue
        for i in range(ind[v - 1], ind[v]):
            w, a, b = G[i, 1:]
            if coin < a:
                continue
            if dist[w, coin - a] <= d + b:
                continue
            dist[w, coin - a] = d + b
            heappush(q, (d + b, w, coin - a))
        c = min(U, coin + C[v - 1])
        if dist[v, c] <= d + D[v - 1]:
            continue
        dist[v, c] = d + D[v - 1]
        heappush(q, (d + D[v - 1], v, c))
    return dist

N, M, S = map(int, readline().split())
nums = np.array(read().split(), np.int64)
UVAB = nums[:4 * M]
CD = nums[4 * M:]

U, V, A, B = UVAB.reshape(-1, 4).T

G = np.empty((M + M, 4), np.int64)
G[:, 0] = np.concatenate((U, V))
G[:, 1] = np.concatenate((V, U))
G[:, 2] = np.concatenate((A, A))
G[:, 3] = np.concatenate((B, B))
G = G[G[:, 0].argsort()]

ans = main(N, S, G, CD)[2:].min(axis=1)
print('\n'.join(map(str, ans.tolist())))
### BUGGY CODE ###

S=str(input())
if len(S)<=4:
  if int(S)%2019==0:
    print(1)
  else:
    print(0)
else:
  N=len(S)
  t=0
  for i in range(N-3):
    for j in range(i+4,N+1):
      if int(S[i:j])%2019==0:
        t+=1
  print(t)


### FIXED CODE ###

S=input()
N=len(S)
Slis=[]
for i in range(N):
  Slis+=[int(S[i])]
T=[0 for i in range(N+1)]#T[i]はi桁より右側の数字


ten=1

for i in range(N):
  T[N-i-1]=(T[N-i]+ten*Slis[N-i-1])%2019
  ten=(ten*10)%2019

MOD=[0 for i in range(2019)]
for i in range(N+1):
  tmp=T[i]%2019
  MOD[tmp]+=1


  
ans=0

for i in range(2019):
  tmp=MOD[i]
  ans+=tmp*(tmp-1)//2
print(ans)
### BUGGY CODE ###

from operator import mul
from functools import reduce
from bisect import bisect_left


def solve(a):
    a.sort()
    max_cmb = cmb(a[1], a[0])
    ans = [a[1], a[0]]
    for ai in a[n-1:1:-1]:
        divided_ai = ai//2
        ak = a[bisect_left(a, divided_ai)]
        q = cmb(ai, ak)
        if a[1] <= ai//2:
            aj = a[bisect_left(a, divided_ai)-1]
            p = cmb(ai, aj)
            if q < p and max_cmb < p:
                ans = [ai, aj]
                max_cmb = p
            elif max_cmb < q:
                ans = [ai, ak]
                max_cmb = q
            else:
                return str(ans[0]) + ' '+str(ans[1])

        else:
            if max_cmb < q:
                ans = [ai, ak]
                max_cmb = q
            else:
                return str(ans[0]) + ' '+str(ans[1])

    return str(ans[0]) + ' '+str(ans[1])


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


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    print(solve(a))


### FIXED CODE ###

from bisect import bisect_left
from sys import stdin



def solve(a):
    a.sort()
    mid = a[n-1]/2
    ai = a[bisect_left(a, mid)-1]
    aj = a[bisect_left(a, mid)]
    am = ai if abs(mid-ai) <= abs(mid-aj) else aj

    print(a[n-1], am)


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, stdin.readline().split()))
    solve(a)
### BUGGY CODE ###

import math
import operator as op
from functools import reduce
from fractions import Fraction as frac

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom
"""
int(input())
map(int,input().split())
list(map(int,input().split()))
"""
# t=int(input())
t=1
for term in range(t):
    nk=list(map(int,input().split()))
    h=list(map(int,input().split()))
    n=nk[0]
    k=nk[1]
    dp=[10**9]*n
    dp[0]=0
    dp[1]=abs(h[1]-h[0])
    for i in range(2,n):
        dp[i]=min(dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-k),i))
    print(dp[n-1])

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline().strip()
 
def main():
    nk=list(map(int,input().split()))
    h=list(map(int,input().split()))
    n=nk[0]
    k=nk[1]
    dp=[10**9]*n
    dp[0]=0
    dp[1]=abs(h[1]-h[0])
    for i in range(2,n):
        dp[i]=min(dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-k),i))
        # for j in range(max(0,i-k),i):
        #     dp[i]=min(dp[j]+abs(h[i]-h[j]),dp[i])
 
    print (dp[-1])
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

B=sorted(set(A))
sa = []
gokei = 0
for i in range(len(B)):
    x = A.count(B[i])
    if x == 1:
        gokei += 0
        sa.append(0)
    elif x ==2:
        gokei += 1
        sa.append(1)
    else:
        z = math.factorial(x)//(math.factorial(x-2)*math.factorial(2))
        gokei += z
        sa.append(z-z*(x-2)//x)

ans = [0]*(N+1)
for i in range(N):
    z = A[i]
    if ans[z] == 0:
        e = gokei - sa[B.index(z)]
        ans.append(e)
        print(e)
    else:
        print(ans[z])

### FIXED CODE ###

import collections

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

gokei = 0
counter = collections.Counter(A)
for i in counter.values():
    gokei += i * (i - 1) // 2

ans = [0]*(N+1)
for i in range(N):
    z = A[i]
    d = counter[z]
    if ans[z] == 0:
        e = gokei - (d * (d - 1) // 2 - (d-1) * (d - 2) // 2)
        ans.append(e)
        print(e)
    else:
        print(ans[z])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N, Q = list(map(int, input().split()))
nodes = {i:[] for i in range(N)}
for i in range(N-1):
  r, e = list(map(int, input().split()))
  r, e = r - 1, e - 1
  nodes[r].append(e)
  nodes[e].append(r)
#print(nodes)

result = [0] * N
for i in range(Q):
  r, s = list(map(int, input().split()))
  result[r-1] += s

def dfs(r, prev=-1):
  for i in nodes[r]:
    if i == prev:
      continue
    result[i] += result[r]
    dfs(i, r)

dfs(0)
print(" ".join(map(str, result)))

### FIXED CODE ###

#人の（ほぼ同じなのにうまくいかないので）
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N, Q = map(int, input().split())
lines = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    lines[a-1].append(b-1)
    lines[b-1].append(a-1)
ans = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x

def dfs(v, parent):
    for u in lines[v]:
        if u != parent:
            ans[u] += ans[v]
            dfs(u, v)

dfs(0, -1)
print (*ans)