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

MOD = 1000000007

n = int(input())
str_ary = input().split()
ary = [int(c) for c in str_ary]
# ary = []
# queue = [0 for i in range(n)]
# for i int range(n):
#   num = int(str_ary[i])
#   ary.append(num)
#   for j int range(i):
#     pre_queue = []
#     queue.append(pre_queue)

sum = 0
for diff in range(n - 1):
  for i in range(n - diff - 1):
    # print(i, i + diff + 1)
    sum += ary[i] * ary[i + diff + 1] % MOD
# for i in range(n):
#   sum = 0
#   for j in range(n - i - 1):
#     # print(i, j + i + 1)
#     sum += ary[j + i + 1]
#   result += ary[i] * sum

print(sum % MOD)

### FIXED CODE ###

MOD = 1000000007

n = int(input())
str_ary = input().split()
ary = [int(c) for c in str_ary]
# ary = []
# queue = [0 for i in range(n)]
# for i int range(n):
#   num = int(str_ary[i])
#   ary.append(num)
#   for j int range(i):
#     pre_queue = []
#     queue.append(pre_queue)

result = 0
sum = sum(ary[i] for i in range(n))
# for diff in range(1, n):
#   for i in range(n - diff):
#     # print(diff, i, i + diff)
#     sum += ary[i] * ary[i + diff] % MOD
for i in range(n):
  sum -= ary[i]
  result += ary[i] * sum

print(result % MOD)
### BUGGY CODE ###

import math

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

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

AB_divs = cf(A, B)

def is_prime(n):
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

primes = []

for v in AB_divs:
    if is_prime(v):
        primes.append(v)

primes.insert(0, 1)
print(len(primes))


### FIXED CODE ###

import math

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

A_divs = make_divisors(A)
B_divs = make_divisors(B)

A_divs_len = len(B_divs)
B_divs_len = len(B_divs)
AB_divs = []

if A_divs_len >= B_divs_len:
    for v in B_divs:
        if v in A_divs:
            AB_divs.append(v)
        else:
            continue
else:
    for w in A_divs:
        if w in B_divs:
            AB_divs.append(w)

def is_prime(n):
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

primes = []

for v in AB_divs:
    if is_prime(v):
        primes.append(v)

primes.insert(0, 1)
print(len(primes))
### BUGGY CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * n
dp[0] = 0
dp[1] = abs(h[0] - h[1])

for i in range(2, n):
    dp[i] = min(abs(h[i] - h[j]) + dp[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():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [0] * n
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])

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


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

n=int(input())

count = 0

for c in range(n):
    if c==0:
        continue
    for a in range(n):
        if a==0:
            continue
        for b in range(n):
            if b==0:
                continue
            if (a*b)+c == n:
                count += 1
else:
    print(count)

### FIXED CODE ###

N = int(input())
ans = 0
for a in range(1, N):
    ans += (N-1)//a
print(ans)
### BUGGY CODE ###

from operator import itemgetter

def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) + list(map(int,input().split())) for _ in range(M)]
    dp = [float("inf")]*(2**N)
    S = [sum([2**(c - 1) for c in abc[2:]]) for abc in ABC]
    dp[0] = 0
    for i in range(M):
        for bit in range(2**N):
            result = int(bit | S[i])
            dp[result] = min(dp[result],dp[bit] + ABC[i][0])        
    print(dp[2**N - 1] if dp[2**N - 1] < float("inf") else -1)
    return

if __name__ == "__main__":
    main()

### FIXED CODE ###

from operator import itemgetter

def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) + list(map(int,input().split())) for _ in range(M)]
    dp = [float("inf")]*(2**N)
    S = [sum([2**(c - 1) for c in abc[2:]]) for abc in ABC]
    dp[0] = 0
    for i in range(M):
        for bit in range(2**N):
            result = int(bit | S[i])
            dp[result] = min(dp[result],dp[bit] + ABC[i][0])        
    print(dp[2**N - 1] if dp[2**N - 1] < float("inf") else -1)
    return

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

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

def dijkstra(s,n,cost,l):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        dist_v = d[v]
        for j in range(n):
            weight = cost[v][j]
            alt = dist_v + weight
            r = (dist_v - 1) // l
            if (r != (alt - 1) // l) and dist_v != 0:
                alt = (r + 1) * l + weight         
            d[j] = min(d[j],alt)
    return d
 
n,m,l = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(m)]
q = int(input())
st = [list(map(int, input().split())) for i in range(q)]
path = [[float("inf") for i in range(n)] for i in range(n)]
ans_list = []
for i in abc:
  a,b,cost = i[0]-1, i[1]-1, i[2]
  if cost <= l:
    path[a][b] = cost
    path[b][a] = cost
for s in range(n):
  ans_list.append(dijkstra(s,n,path,l))
for i in st:
  s, t = i[0] - 1, i[1] - 1
  ans = ans_list[s][t]
  if ans == float("inf"):
    ans = -1
  else:
    ans = (ans - 1) // l
  print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

def dijkstra(s,n,cost,l):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        dist_v = d[v]
        for j, weight in enumerate(cost[v]):
            alt = dist_v + weight
            r = (dist_v - 1) // l
            if r != ((alt - 1) // l) and dist_v != 0:
                alt = (r + 1) * l + weight         
            d[j] = min(d[j],alt)
    return d

n,m,l = map(int, input().split())
path = [[float("inf") for i in range(n)] for i in range(n)]
ans_list = []
for i in range(m):
  a,b,cost = map(int, input().split())
  a -= 1
  b -= 1
  if cost <= l:
    path[a][b] = cost
    path[b][a] = cost
for s in range(n):
  ans_list.append(dijkstra(s,n,path,l))
q = int(input())

for i in range(q):
  s,t = map(int, input().split())
  ans = ans_list[s-1][t-1]
  if ans == float("inf"):
    ans = -1
  else:
    ans = (ans - 1) // l
  print(ans)
### BUGGY CODE ###

R, G, B, n = map(int, input().split())
ans = 0
for r in range(n // R + 1):
    for g in range((n - r) // G + 1):
        if (n - r * R - g * G) % B == 0:
            b = (n - r * R - g * G) / B
            if b >= 0:
                ans += 1
print(ans)

### FIXED CODE ###

R, G, B, n = map(int, input().split())
ans = 0
for r in range(n // R + 1):
    for g in range((n - r) // G + 1):
        if (n - r * R - g * G) % B == 0:
            b = (n - r * R - g * G) / B
            if b >= 0:
                ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
arr = []
for i in range(n):
    num = int(input())
    if num in arr:
        arr.remove(num)
    else:
        arr.append(num)
print(len(arr))

### FIXED CODE ###

n = int(input())
arr = set()
for i in range(n):
    num = int(input())
    if num in arr:
        arr.remove(num)
    else:
        arr.add(num)
print(len(arr))
### BUGGY CODE ###

import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()
tugi = [0]+a
town  =1
route = [0]*n
route[0] = town

for i in range(n):
    town = tugi[town]
    if town in route:
        i = route.index(town)
        notcycle = route[:i]
        cycle = route[i:]
        break
    route[i+1] = town

for i in range(n):
    if cycle[i] == 0:
        cycle = cycle[:i]
        break

if len(notcycle) >k:
    print(notcycle[k])
else:
    k -= len(notcycle)
    print(cycle[k%len(cycle)])

### FIXED CODE ###

import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()
tugi = [0]+a
town  =1
route = [0]*n
route[0] = town
used = [False]*n
used[0] = True
for i in range(n):
    town = tugi[town]
    if used[town-1]:
        i = route.index(town)
        notcycle = route[:i]
        cycle = route[i:]
        break
    used[town-1] = True
    route[i+1] = town

for i in range(n):
    if cycle[i] == 0:
        cycle = cycle[:i]
        break

if len(notcycle) >k:
    print(notcycle[k])
else:
    k -= len(notcycle)
    print(cycle[k%len(cycle)])
### BUGGY CODE ###

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

from collections import deque
import copy
QUE=deque()

for i in range(H):
    for j in range(W):

        if MAP[i][j]=="#":
            QUE.append([i,j,0])

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

while QUE:
    NQUE=deque()
    while QUE:
        x,y,z=QUE.pop()
        ANS[x][y]=z

        for nx,ny in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:
            if nx<0 or ny<0 or nx>=H or ny>=W:
                continue

            if ANS[nx][ny]!=-1:
                continue

            NQUE.append([nx,ny,z+1])

    QUE=NQUE

            
print(max([max(ANS[i]) for i in range(H)]))

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

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

from collections import deque
QUE=deque()

for i in range(H):
    for j in range(W):

        if MAP[i][j]=="#":
            QUE.append([i,j,0])
            ANS[i][j]=0

while QUE:
    NQUE=deque()
    while QUE:
        x,y,z=QUE.pop()

        for nx,ny in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:
            if nx<0 or ny<0 or nx>=H or ny>=W:
                continue

            if ANS[nx][ny]!=-1:
                continue

            NQUE.append([nx,ny,z+1])
            ANS[nx][ny]=z+1

    QUE=NQUE

            
print(max([max(ANS[i]) for i in range(H)]))
### BUGGY CODE ###

# 動的計画法
#D - Knapsack 1
#https://atcoder.jp/contests/dp/tasks/dp_d
#インデックスと重さを対応させていく
N, W = list(map(int,input().split()))
item = [list(map(int,input().split())) for i in range(N)]
dp = [-1]*(W+1)
dp[0] = 0
for i in range(N):
    w = item[i][0]
    v = item[i][1]
    #print(w,v)
    for j in range(W-w,-1,-1):
        if dp[j] != -1:
            if dp[j] + v > dp[j+w]:
                dp[j+w] = dp[j] + v
        #print(dp)
print(max(dp))

### FIXED CODE ###

#動的計画法
#D - Knapsack 1
#インデックスの順番でなく重さを基準に動的計画していく
N, W = list(map(int,input().split()))
item = [list(map(int,input().split())) for i in range(N)]
dp = [-1]*(W+1)
dp[0] = 0
for i in range(N):
    w = item[i][0]
    v = item[i][1]
    #print(w,v)
    for j in range(W-w,-1,-1):
        if dp[j] != -1:
            if dp[j] + v > dp[j+w]:
                dp[j+w] = dp[j] + v
        #print(dp)
print(max(dp))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 0
for i in range(n-1):
    if i+a[i]+1 < n:
        for j in range(i+a[i]+1,n):
            if j-i == a[i]+a[j]:
                ans+=1
print(ans)



### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
l = {}
r = {}
for i in range(n):
    p = i+a[i]
    q = i-a[i]
    if p < n:
        if p in l:
            l[p] = l[p]+1
        else:
            l[p] = 1
    if q > 0:
        if q in r:
            r[q] = r[q]+1
        else:
            r[q] = 1
ans = 0
for i in l:
    if i in r:
        ans+= l[i]*r[i]
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if(discrete) else 10**-8
    if((not left)^f(r)): return r if(left) else r+1
    elif(left^f(l)): return l-1 if(left) else l
    while(r-l>eps):
        h=(l+r)//2 if(discrete) else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if(not discrete) else l if(left) else r

def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()

    def check(i): # i のカードを除いて、k-a[i]<=s<k が作れるか
        dp=1
        for j in range(n):
            if(i==j): continue
            dp|=(dp<<A[j])

        for j in range(max(0,k-A[i]),k):
            if((dp>>j)&1):
                return True
        return False

    print(bisection(0,n-1,check,left=False))
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if(discrete) else 10**-8
    if((not left)^f(r)): return r if(left) else r+1
    elif(left^f(l)): return l-1 if(left) else l
    while(r-l>eps):
        h=(l+r)//2 if(discrete) else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if(not discrete) else l if(left) else r

def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A=[min(a,k+1) for a in A]
    A.sort()
    mask=(1<<k)-1

    def check(i): # i のカードを除いて、k-a[i]<=s<k が作れるか
        if(k-A[i]<0): return True
        dp=1
        for j in range(n):
            if(i==j): continue
            dp|=(dp<<A[j])
            dp&=mask

        dp>>=(k-A[i])
        return dp>0

    print(bisection(0,n-1,check,left=False))
resolve()
### BUGGY CODE ###

import itertools

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

triangle = itertools.combinations(l, 3)

cnt = 0

for i in triangle:
  if max(i)*2 < sum(i):
    cnt += 1

print(cnt)

### FIXED CODE ###

import bisect

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

l.sort()
cnt = 0


for i in range(n-2):
  for j in range(i+1, n-1):
    sum = l[i] + l[j]
    index = bisect.bisect_left(l, sum)
    cnt += index - j - 1

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

N,a,b=map(int,input().split())
sum=0
blue=0
red=0
while sum<N:
    for n in range(a):
        if sum==N:
            break
        blue+=1
        sum+=1
    for m in range(b):
        if sum==N:
            break
        red+=1
        sum+=1
print(blue)

### FIXED CODE ###

N,A,B=map(int,input().split())
ans=(N//(A+B))*A
if N%(A+B)>A:
    ans+=A
else:
    ans+=N%(A+B)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import itertools
 
 
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    c = itertools.combinations_with_replacement(range(1, N + 1), 2)
    cnt = 0
    for i in c:
        x = i[0]
        y = i[1]
        if y - A[y - 1] == x + A[x - 1]:
            cnt += 1
    print(cnt)
    return
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
# import itertools
import collections


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    # # TLE
    # c = itertools.combinations_with_replacement(range(1, N + 1), 2)
    # cnt = 0
    # for i in c:
    #     x = i[0]
    #     y = i[1]
    #     if x + A[x - 1] == y - A[y - 1]:
    #         cnt += 1
    # print(cnt)

    L = []  # 左辺
    R = []  # 右辺
    for i in range(N):
        x = y = i + 1
        L.append(x + A[i])
        R.append(y - A[i])
    cl = collections.Counter(L)
    cr = collections.Counter(R)
    ans = 0
    for i in range(N):
        if i in cl and i in cr:
            ans += cl[i] * cr[i]
    print(ans)
    return

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

import queue
def main():
    h,w=map(int,input().split())
    maze=[]
    r_append=maze.append
    for i in range(h):
        #r_append=maze.append
        row=input()
        r_append(row)
    #print(maze)
    root=[[-1 for i in range(h*w)] for i in range(h*w)]
    ina=[i for i in range(h*w)]
    for i in range(h):
        for j in range(w):
        # print(maze[i][j])
            now=w*i+j
            hidari=w*i+j-1
            migi=w*i+j+1
            ue=w*(i-1)+j
            sita=w*(i+1)+j
            if maze[i][j]==".":
                if j>0:
                    if maze[i][j-1]!="#":
                        root[now][hidari]=0
                if i+1<h:
                    if maze[i+1][j]!="#":
                        root[now][sita]=0
                if j+1<w:
                    if maze[i][j+1]!="#":
                        root[now][migi]=0
                if 0<i:
                    if maze[i-1][j]!="#":
                        root[now][ue]=0
            else:
                ina[now]=-1
                if j>0:
                    root[now][hidari]=-1
                if i+1<h:
                    root[now][sita]=-1
                if j+1<w:
                    root[now][migi]=-1
                if 0<i:
                    root[now][ue]=-1
    #print(root)
    max=0
    hw=h*w
    for start in ina:
        dist=[0]*(hw)
        now=start
        dist[start]=0
        visted=[0]*(hw)
        toVis=queue.Queue()
        visted[now]=1
        for i in range(hw):
            if root[now][i]!=-1:
                toVis.put(i)
                dist[i]=dist[now]+1
        while toVis.empty()!=True:
            now=toVis.get()
            visted[now]=1
            le=dist[now]
            for i in range(hw):
                if root[now][i]!=-1 and visted[i]!=1:
                    toVis.put(i)
                    dist[i]=le+1
        farest=dist[now]
        if max<farest:
            max=farest
    print(max)
            
if __name__=="__main__":
    main()


    

### FIXED CODE ###

h,w=map(int,input().split())
n=h*w
inf=10**6
field=[]
for i in range(h):
    field.append(input())
dist=[[inf]*n for i in range(n)]
for i in range(h):
    for j in range(w):
        if field[i][j]=="#":continue
        if j+1<w and field[i][j+1]!="#":
            dist[i*w+j][i*w+j+1]=1
            dist[i*w+j+1][i*w+j]=1
        if i+1<h and field[i+1][j]!="#":
            dist[i*w+j][(i+1)*w+j]=1
            dist[(i+1)*w+j][i*w+j]=1
for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k])
ans=0
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        if dist[i][j]==inf:
            continue
        ans=max(ans,dist[i][j])
print(ans)
### BUGGY CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    dic = defaultdict(int)
    a.sort()
    ans = 0
    for i in range(n):
        x = a[i]
        div=[]
        for check in range(1,int(x**0.5)+1):
            if(x%check==0):
                div.append(check)
                div.append(x//check)
        flag = 1
        for e in div:
            if dic[e]:
                flag = 0
                break
        if i < n-1 and a[i] == a[i+1]:
            flag = 0
        if flag:
            ans += 1
        dic[a[i]] = 1
    print(ans)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
 
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    N = max(a)+1
    tab = [1 for _ in range(N)]
    for i in range(n):
        x = a[i]
        if i < n-1 and a[i] == a[i+1]:
            tab[a[i]] = 0
        if tab[x]:
            ans += 1
        for i in range(N):
            if x*i >= N:
                break
            tab[x*i] = 0        
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

query=[""]*Q
for i in range(Q):
    query[i]=input()

#print(query)

for i in query:
    a=i.split(" ")
    if(len(a)==1):
        S=S[::-1]
    else:
        if(a[1]=="1"):
            S=a[2]+S
        else:
            S+=a[2]
print(S)


### FIXED CODE ###

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

flag=0
forward=""
back=""
for i in range(Q):
    #query[i]=input()
    b=input()

    if(len(b)==1):
        #S=S[::-1]
        flag+=1
    else:
        a=b.split(" ")
        if(flag==0):
            if(a[1]=="1"):
                #S=a[2]+S
                forward=a[2]+forward
            else:
                #S+=a[2]
                back=back+a[2]
        else:
            if(a[1]=="1"):
                #S=a[2]+S
                back=back+a[2]
            else:
                #S+=a[2]
                forward=a[2]+forward
                
    flag=flag%2

S=forward+S+back
if(flag==1):
    S=S[::-1]
print(S)
### BUGGY CODE ###

INF = 1 << 32


def main(n, k, heights):
    for i in range(k):
        heights.extend([INF for i in range(k)])
    costs = [INF for i in range(n + k)]
    costs[0] = 0
    for i in range(n):
        for j in range(1, k + 1):
            costs[i + j] = min(costs[i + j], abs(heights[i] - heights[i + j]) + costs[i])
    return costs[n - 1]


if __name__ == '__main__':
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    print(main(N, K, H))


### FIXED CODE ###

import numpy as np


def main(n, k, heights):
    heights = np.array(heights, dtype=int)
    costs = np.zeros(n, dtype=int)
    for i in range(1, n):
        start = max(0, i - k)
        costs[i] = np.min(costs[start:i] + np.abs(heights[i] - heights[start:i]))
    return costs[-1]


if __name__ == '__main__':
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    print(main(N, K, H))
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    from collections import Counter

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

    A_Counter = Counter(A)
    for i in range(Q):
        B, C = map(int, input().split())
        A_Counter[C] += A_Counter[B]
        A_Counter[B] = 0

        print(sum(A_Counter.elements()))


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    from collections import Counter

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

    ans = [None] * Q
    Asum = sum(A)
    A_Counter = Counter(A)
    for q in range(Q):
        B, C = map(int, input().split())
        Asum = Asum + (C-B)*A_Counter[B]
        A_Counter[C] += A_Counter[B]
        A_Counter[B] = 0

        ans[q] = Asum

    print('\n'.join(map(str, ans)))


if __name__ == "__main__":
    main()