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

n=int(input())
x=list(map(int, input().split()))
mod = 10**9+7
last=x[-1]
X=[]
for i in x[:-1]:
  X.append(last-i)
l=1
left=[1]
for i in range(1, n-1):
  l=l*i%mod
  left.append(l)
r=1
right=[1]
for i in range(n-1, 1, -1):
  r*=i%mod
  right.append(r)
right.reverse()
flst=[]
for i,j in zip(left,right):
  flst.append((i*j)%mod)
s=0
for i,j in zip(X,flst):
  s+=i*j%mod
print(s%mod)

### FIXED CODE ###

# https://atcoder.jp/contests/dwacon6th-prelims/submissions/9426910


def solve():
    MOD = 10**9 + 7

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

    ds = []
    for i in range(N-1):
        d = xs[i+1] - xs[i]
        ds.append(d)

    nums = [1, 1]
    num = 1
    for i in range(2, N-1):
        num *= i
        num %= MOD
        nums.append(num)

    ms = [N-1]
    m = N-1
    for i in reversed(range(2, N-1)):
        m *= i
        m %= MOD
        ms.append(m)
    ms.reverse()
    ms.append(1)

    ks = []
    k = 0
    for num, m in zip(nums, ms):
        k += num*m % MOD
        k %= MOD
        ks.append(k)

    ans = 0
    for d, k in zip(ds, ks):
        ans += d*k % MOD
        ans %= MOD

    print(ans)

solve()
### BUGGY CODE ###

#!/usr/bin/env python3
n, *a = map(int, open(0).read().split())
b = [0] * 60
ans = 0
for i in range(n):
    for j in range(60):
        ans += (i - b[j] if a[i] >> j & 1 else b[j]) << j
    ans %= 10**9 + 7
    for j in range(60):
        b[j] += a[i] >> j & 1
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
n, *a = map(int, open(0).read().split())
b = [0] * 60
ans = 0
for i in range(n):
    for j in range(60):
        ans += (i - b[j] if a[i] >> j & 1 else b[j]) << j
    ans %= 10**9 + 7
    for j in range(60):
        b[j] += a[i] >> j & 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import bisect

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

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
ans=0
for i in range(n):
    if x[i][1]>=1:
        w=x[i][1]
        ans+=w
        q=bisect.bisect_right(y,x[i][0]+2*d,i,n)
        for j in range(q-i):
            if x[i+j][1]<=0:
                continue
            else:
                x[i+j][1]-=w
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
import collections
from collections import deque
n,d,a= map(int, input().split())
x= [list(map(int, input().split())) for i in range(n)]

x.sort()
y=[]
for i in range(n):
    y.append(x[i][0])
    x[i][1]=-(-x[i][1]//a)

# どのモンスターまで倒したか管理しながら進める。
# 累積ダメージを管理
qq=deque([])
ans=0
atk=0
for i in range(n):
    w=x[i][1]
    # iがダメージの有効期限を超過している場合
    while len(qq)>0 and i > qq[0][0]:
        atk-=qq[0][1]
        qq.popleft()

    if w-atk>0:
        ans+=w-atk
        q=bisect.bisect_right(y,x[i][0]+2*d)-1
        # 有効期限　ダメージ
        qq.append([q,w-atk])
        atk += w - atk
print(ans)
### BUGGY CODE ###

from collections import Counter
from math import sqrt

MOD = 10**9+7
p_list = {}  # 最大公約数を素因数分解したもの

def prime_decomposition(n):
    i = 2
    a = []
    while i <= int(sqrt(n))+1:
        while n % i == 0:
            n //= i
            a.append(i)
        i += 1
    if n > 1:
        a.append(n)
    return a


def main():
    N = int(input())
    a = [int(i) for i in input().split()]

    for i in a:
        l = Counter(prime_decomposition(i))
        for k, v in l.items():
            if p_list.get(k):
                p_list[k] = max(p_list[k], v)
            else:
                p_list[k] = v

    # ここからMODを法として考える
    lcm = 1
    for k, v in p_list.items():
        lcm *= pow(k, v, MOD)
        lcm %= MOD

    ans = 0
    for i in a:
        # ans += lcm // i
        ans += lcm * pow(i, MOD - 2, MOD)
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from functools import reduce
from fractions import gcd

MOD = 10**9+7

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def main():
    N = int(input())
    a = [int(i) for i in input().split()]

    lcm = reduce(lcm_base, a, 1)
    
    ans = 0
    for i in a:
        ans += lcm // i

    print(ans % MOD)


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

n = int(input())
c = list(input())

end = []
for i in range(n+1):
    end.append("R"*i + "W"*(n-i))
#print(end)

newc = "".join(c)
ans = 0
j,k = -1,n
if newc in end:
    print(ans)
    exit()
while newc not in end:
    for i in range(j+1,n):
        if c[i] == "W":
            j = i
            c[i] = "R"
            break
    for i in reversed(range(k)):
        if c[i] == "R":
            k = i
            c[i] = "W"
            break
    newc = "".join(c)
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
c = list(input())

x = c.count("R")

ans = 0
for i in range(x):
    if c[i] == "W":
        ans += 1

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

A, B, N = map(int, input().split())
# S = input()
# X1_list = [int(input()) for i in range(N)]
# X2_list = [list(map(int,input().split())) for i in range(N)]


ans = 0
before_ans = 0
for i in range(1, N + 1):
    a = int(A * i / B)
    b = A * int(i / B)
    ans = max(ans, a - b)
    #print(i, ans)
    if before_ans > ans:
        break
    if ans == min(A - 1, B - 1):
        break
    before_ans = a - b
print(ans)

### FIXED CODE ###

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


# S = input()
# X1_list = [int(input()) for i in range(N)]
# X2_list = [list(map(int,input().split())) for i in range(N)]
def solve(i):
    a = int(A * i / B)
    b = A * int(i / B)
    return a - b


print(solve(min(N, B - 1)))
### BUGGY CODE ###

# coding:utf-8

S = input()
Q = int(input())
queries = [input().rstrip('\n') for _ in range(Q)]

for query in queries:
    q = query.split(' ')
    if len(q) == 1:
        S = S[::-1]
    else:
        if q[1] == '1':
            S = q[2] + S
        else:
            S = S + q[2]
print(S)

### FIXED CODE ###

# coding:utf-8
from collections import deque

S = deque(input())
Q = int(input())
queries = [input().rstrip('\n') for _ in range(Q)]
reverse = False

for query in queries:
    q = query.split(' ')
    if q[0] == '1':
        reverse = not reverse
    else:
        if q[1] == '1':
            S.appendleft(q[2]) if not reverse else S.append(q[2])
        else:
            S.append(q[2]) if not reverse else S.appendleft(q[2])

if reverse:
    S.reverse()
print("".join(S))
### BUGGY CODE ###

#! /usr/bin/env python3

import sys
from collections import deque, Counter
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


c = list(Counter(prime_factorize(N)).values())

ans = 0
used = {}

for i in range(len(c)):
    acc = 0
    cnt = 1
    while True:
        if c[i] >= acc + cnt:
            c[i] -= acc+cnt
            acc = acc+cnt
            ans += 1
        else:
            break
c = sorted(c)[::-1]

hoge = 1
for hoge in range(1, 1000):
    for _ in range(100000):
        for i in range(len(c)-1):
            if min(c[i:i+hoge+1]) >= 1:
                for k in range(hoge+1):
                    c[i+k]-=1
                ans += 1
        c = sorted(c)[::-1]

print(ans)


### FIXED CODE ###

#! /usr/bin/env python3

import sys
from collections import deque, Counter
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


c = list(Counter(prime_factorize(N)).values())

ans = 0
used = {}

for i in range(len(c)):
    cnt = 1
    while True:
        if c[i] >= cnt:
            c[i] -= cnt
            ans += 1
            cnt += 1
        else:
            break

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

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

cnt = 0
ind = 1
while A != []:
  A = list(map(lambda x: x - 1, A))
  if(0 in A):
    zero = A.count(0)
    if(zero > ind):
      cnt += abs(zero - ind)
    elif(zero < ind):
      cnt += zero
    for _ in range(zero):
      A.remove(0)
  ind += 1
print(cnt)

### FIXED CODE ###

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

d = {}
for i in range(N):
  if(a[i] not in d):
    d[a[i]] = 1
  else:
    d[a[i]] += 1
cnt = 0
for k, v in d.items():
  if(k > v):
    cnt += v
  elif(k < v):
    cnt += v - k
print(cnt)
### BUGGY CODE ###

def sol():
    n,m=map(int,input().split())
    t={}
    w={}
    p,q=set(),set()
    for i in range(m):
        l,r,d=[int(i) for i in input().split()]
        t[(l,r)]=d
        if l in w:
            w[l].add((r,d))
        else:
            w[l]={(r,d)}
        p.add(l)
        q.add(r)
    s=p-q
    chk=set()
    if len(s)==0:
        print(["No","Yes"][m==0])
        exit()
    for i in s:
        chk.add((i,0))
        while len(chk):
            x=chk.pop()
            if x[0] in w:
                for j in w[x[0]]:
                    if (i,j[0]) in t and t[(i,j[0])]!=x[1]+j[1]:
                    #if (x[0],j[0]) in t and t[(i,j[0])]!=
                        print("No")
                        exit()
                    elif (i,j[0]) not in t:
                        t[(i,j[0])]=x[1]+j[1]
                        chk.add((j[0],x[1]+j[1]))
                    else:
                        chk.add((j[0],x[1]+j[1]))
    print("Yes")

if __name__=="__main__":
    sol()

### FIXED CODE ###

def sol():
    n,m=map(int,input().split())
    t,w={},{}
    p,q=set(),set()
    for i in range(m):
        l,r,d=[int(i) for i in input().split()]
        if l in w: w[l].add((r,d))
        else: w[l]={(r,d)}
        p.add(l)
        q.add(r)
    s=p-q
    chk=set()
    if len(s)==0:
        print(["No","Yes"][m==0])
        exit()
    for i in s:
        chk.add((i,0))
        while len(chk):
            x=chk.pop()
            if x[0] in w:
                for j in w[x[0]]:
                    if (i,j[0]) in t and t[(i,j[0])]!=t[(i,x[0])]+j[1]:
                        print("No")
                        exit()
                    elif (i,j[0]) not in t:
                        #t[(i,j[0])]=t[(i,x[0])]+j[1]
                        t[(i,j[0])]=x[1]+j[1]
                        chk.add((j[0],x[1]+j[1]))
    print("Yes")

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

n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
for _ in range(m):
  b,c = map(int,input().split())
  for i in range(b):
    if a[i] < c:
      a[i] = c
    else:
      break
  a.sort()
      
print(sum(a))
  

### FIXED CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = [tuple(map(int,input().split())) for _ in range(m)]

bc.sort(key = lambda x: x[1],reverse = True)
i = 0
j = 0
ad = []
while i < n and j < m:
    ad.extend([bc[j][1]]*bc[j][0])
    i += bc[j][0]
    j += 1
    
if len(ad) < n:
    ad.extend([0]*(n-len(ad)))

a.sort(reverse = True)

i = 0
j = 0
k = 0
ans = 0
while k < n :
    if a[i] > ad[j]:
        ans += a[i]
        i += 1
        k += 1
    else:
        ans += ad[j]
        j += 1
        k += 1
  
print(ans)
### BUGGY CODE ###

import itertools

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

# まずループを見つけてみる

loopstart = -1
loopend = -1
path = []
nextcity = 0
for i in range(N):
    currentcity = nextcity
    path.append(nextcity)
    nextcity = A[nextcity]-1
    if nextcity in path:
        loopstart = nextcity
        loopend = currentcity
        path.append(nextcity)
        break
#print(path)

# ループまでの距離
toloop = path.index(loopstart)

# ループ内の距離
looplength = path.index(loopend) - toloop + 1

#print(toloop)
#print(looplength)
if K < toloop + looplength + 1:
    print(path[K] + 1)
else:
    fromloopstart = (K - toloop) % looplength
    print(path[toloop + fromloopstart] + 1)

### FIXED CODE ###

import itertools

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

# まずループを見つけてみる

loopstart = -1
loopend = -1
path = []
nextcity = 0
FLAGS = [False for _ in range(N)]
for i in range(N):
    currentcity = nextcity
    path.append(nextcity)
    FLAGS[nextcity] = True
    nextcity = A[nextcity]-1
    if FLAGS[nextcity]:
        loopstart = nextcity
        loopend = currentcity
        path.append(nextcity)
        break
#print(path)

# ループまでの距離
toloop = path.index(loopstart)

# ループ内の距離
looplength = path.index(loopend) - toloop + 1

#print(toloop)
#print(looplength)
if K < toloop + looplength + 1:
    print(path[K] + 1)
else:
    fromloopstart = (K - toloop) % looplength
    print(path[toloop + fromloopstart] + 1)
### BUGGY CODE ###

s = input()
ans = 0
for i in range(len(s)):
    if "BW" in s:
        s_index = s.index("BW")
        s = list(s)
        s[s_index], s[s_index+1] = s[s_index+1], s[s_index]
        s = "".join(s)
        ans += 1
print(ans)


### FIXED CODE ###

s = input()
b_idx = list(reversed([i for i, x in enumerate(s) if x == "B"]))
ans = 0
for i in range(len(b_idx)):
    ans += (len(s)-(i+1)) - b_idx[i]
print(ans)
### BUGGY CODE ###

from copy import deepcopy
n,m = (int(i) for i in input().split())
p = [int(i) for i in input().split()]
x = [[int(i) for i in input().split()] for i in range(m)]
c,d,e = [[] for i in range(n+1)],[True for i in range(n+1)],[]
d[0],ans = False,0
for i,j in x:
	c[i].append(j)
	c[j].append(i)
while sum(d)!=0:
	for i in range(n+1):
		if d[i]: break
	num2 = set([i])
	while True:
		num3 = deepcopy(num2)
		for i2 in list(num2):
			for j in c[i2]:
				if d[j]:
					num3.add(j)
					d[j] = False
		if num2==num3: break
		else: num2 = num3
	for i in num2: d[i]=False
	e.append(list(num2))
for i in e:
	for j in i:
		if p[j-1] in i: ans+=1
print(ans)

### FIXED CODE ###

n,m = (int(i) for i in input().split())
par,rank = [i for i in range(n+1)],[0 for i in range(n+1)]
def root(x):
	if par[x]!=x: par[x] = root(par[x])
	return par[x]
def unite(x,y):
	x2,y2 = root(x),root(y)
	if x2!=y2:
		if rank[x2]<rank[y2]: par[x2] = y2
		else: par[y2] = x2
		if rank[x2]==rank[y2]: rank[x2]+=1
p = [int(i) for i in input().split()]
x = [[int(i) for i in input().split()] for i in range(m)]
for i,j in x: unite(i,j)
ans = -1
for i,j in enumerate([0]+p):
	if root(i)==root(j): ans += 1
print(ans)
### BUGGY CODE ###

s = input()
ss = s
for i in range(len(s)):
    if "10" or "01" in s:
        s = s.replace("10", "")
        s = s.replace("01", "")
print(len(ss)-len(s))

### FIXED CODE ###

s = input()
c1, c2 = 0, 0
for i in s:
    if i == "0":
        c1 += 1
    else:
        c2 += 1
print(min(c1, c2)*2)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
p = 1
maxp = 10 ** 18
for i in range(n):
  p *= a[i]
if p > maxp:
  print('-1')
else:
  print(p)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
p = 1
maxp = 10 ** 18
overFlag = False
if 0 in a:
  p = 0
else:
  for i in range(n):
    p *= a[i]
    if p > maxp:
      overFlag = True
      break
if overFlag == True:
    print('-1')
else:
  print(p)
### BUGGY CODE ###

N,H = map(int,input().split())
ans = 0
A = []
B = []
for i in range(N) :
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
B = sorted(B,reverse = True)
flag = 0
for i in range(N) :
    if H <= 0 :
        break
    if max(A) < B[i] :
        H -= B[i]
        ans += 1
    else :
        break
if H <= 0 :
    print(ans)
else :
    if H % max(A) == 0 :
        ans += H // max(A)
    else :
        ans += H // max(A) + 1
    print(ans)
    
   

### FIXED CODE ###

N,HP = map(int,input().split())
L = list(list(map(int,input().split())) for i in range(N))

L = sorted(L, key=lambda x: x[0], reverse=True)
max_a = L[0][0]
L = sorted(L, key=lambda x: x[1], reverse=True)

ans = 0

for i in range(N) :
    if L[i][1] < max_a :
        break
    HP -= L[i][1]
    ans += 1
    if HP <= 0 :
        break

if HP >= 0 :
    if HP % max_a == 0 :
        ans += HP//max_a
    else :
        ans += HP//max_a + 1

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

p=int(input())
A=list(map(int,input().split()))
cmb=[0]*p
cmb[0]=1
for i in range(1,p):
  cmb[i]=cmb[i-1]*(p-i)*pow(i,p-2,p)%p
ans=[0]*p
for i in range(p):
  if A[i]==1:
    b=1
    ans[0]=ans[0]+1
    for j in range(p):
      ans[p-j-1]=(ans[p-j-1]-cmb[j]*b)%p
      b=b*(-i)%p
for i in range(p-1):
  print(ans[i],end=" ")
print(ans[p-1])



### FIXED CODE ###

p=int(input())
A=list(map(int,input().split()))
cmb=[0]*p
cmb[0]=1
for i in range(1,p):
  cmb[i]=cmb[i-1]*(p-i)*pow(i,p-2,p)%p
ans=[0]*p
for i in range(p):
  if A[i]==1:
    b=1
    ans[0]=ans[0]+1
    for j in range(p):
      ans[p-j-1]=(ans[p-j-1]-cmb[j]*b)%p
      b=b*(-i)%p
for i in range(p-1):
  print(ans[i],end=" ")
print(ans[p-1])
### BUGGY CODE ###

S=input()
T=input()


def search():
    pos=0
    now=S
    for t in T:
        if t in S:
            if not t in now:
                now+=S
            ind=now.index(t)+1
            now=now[ind:]

            pos+=ind
        else:
            return -1
    return pos

print(search())


### FIXED CODE ###

import collections
import bisect
S = input()
T = input()
N = len(S)

d = collections.defaultdict(list)
for i, s in enumerate(S):
    d[s].append(i + 1)

ans = 0
end = 0
isOK = True
i = 0

for t in T:
    if len(d[t]) == 0:
        isOK = False
        break
    dic = d[t]
    idx = bisect.bisect_right(dic, i)
    if len(dic) == idx:
        i = dic[0]
        end += 1
    else:
        i = dic[idx]

if isOK:
    ans = N * end + i
else:
    ans = -1

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

N = int(input())
L = [int(i) for i in input().split()]
L.sort()

result = 0

for aIndex,a in enumerate(L):
    for bIndex,b in enumerate(L[aIndex+1:]):
        for c in L[aIndex+bIndex+2:]:
            if a<b+c and b<a+c and c<a+b:
                result+=1
            else:
                break

print(result)

### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int,input().split()))
L.sort()
 
result = 0

for aIndex,a in enumerate(L[:N-2]):
    for bIndex,b in enumerate(L[aIndex+1:N-1]):
        bIndex = aIndex + bIndex + 1
        ab = a+b
        n = bisect_left(L,ab) - bIndex - 1
        result += n
print(result)
### BUGGY CODE ###

n = int(input())
result = 0

for i in range(1, n):
    result += i
print(result)

### FIXED CODE ###

n = int(input())
print(int((n-1)*(n)//2))
### BUGGY CODE ###

from collections import defaultdict
MAX_N = 10 ** 3 + 10
MAX_M = 2 * (10 ** 3) + 1
INF = -(10 ** 100)

def bfs(graph, N, M):
    que = []
    que.append([0, 0])
    visited = defaultdict(list)
    result = INF
    while (len(que) > 0):
        now = que[0]
        que.pop(0)

        pos = now[0]
        cost = now[1]

        if (pos in visited):
            visited_cost = visited[pos][0]
            visited_cnt = visited[pos][1]
            if (visited_cost >= cost):
                continue
            if (visited_cnt >= MAX_N):
                continue
            visited[pos] = [cost, visited_cnt + 1]
        else:
            visited[pos] = [cost, 0]

        if (pos == N - 1):
            result = max(result, cost)

        for val in graph[pos]:
            nxt = val[0]
            nxt_cost = val[1]
            if (nxt not in visited):
                que.append([nxt, nxt_cost + cost])
            elif(nxt_cost + cost > visited[nxt][0]):
                que.append([nxt, nxt_cost + cost])
    if (visited[N - 1][1] >= MAX_N):
        return (0, False)
    return (result, True)


if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = defaultdict(list)
    for x in range(M):
        a,b,c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    res,ok = bfs(graph, N, M)
    if (not ok):
        print ('inf')
    else:
        print (res)


### FIXED CODE ###


MAX_N = 10 ** 3 + 10
MAX_M = 2 * (10 ** 3) + 1
INF = 10 ** 13

def bfs(graph, N, M):
    que = []
    que.append([0, 0])
    visited = [-INF for x in range(MAX_N)]
    update_cnt = [0 for x in range(MAX_N)]
    result = -INF
    while (len(que) > 0):
        now = que[0]
        que.pop(0)

        pos = now[0]
        cost = now[1]
        if (visited[pos] > cost):
            continue
        for val in graph[pos]:
            nxt = val[0]
            nxt_cost = val[1]

            if (cost + nxt_cost > visited[nxt] and update_cnt[nxt] < MAX_M):
                visited[nxt] = cost + nxt_cost
                update_cnt[nxt] += 1
                que.append([nxt, nxt_cost + cost])

    if (update_cnt[N - 1] >= MAX_N):
        return (0, False)
    return (visited[N - 1], True)


if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = [[] for x in range(MAX_N)]
    for x in range(M):
        a,b,c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    res,ok = bfs(graph, N, M)
    if (not ok):
        print ('inf')
    else:
        print (res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(lambda x:int(x)-1, input().split()))
query = []
for i in range(q):
    l, r = map(int, input().split())
    query.append((i, l-1, r-1))

class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.bit = [0]*n
    
    def add(self, i, w):
        x = i+1
        while x<=self.n:
            self.bit[x-1] += w
            x += x & -x
    
    def sum_(self, i):
        ret = 0
        x = i+1
        while x>0:
            ret += self.bit[x-1]
            x -= x & -x
        return ret

bit = BinaryIndexedTree(n+1)
query.sort(key=lambda x:x[2])
last = [None]*n
ans = [None]*q
nr = -1
for idx, l, r in query:
    for cr in range(nr+1, r+1):
        if last[c[cr]] is not None:
            bit.add(last[c[cr]]+1, -1)
        last[c[cr]] = cr
        bit.add(cr+1, 1)
    nr = r
    ans[idx] = bit.sum_(r+1) - bit.sum_(l)
for i in ans:
    print(i)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(lambda x:int(x)-1, input().split()))
query = []
for i in range(q):
    l, r = map(int, input().split())
    query.append((i, l-1, r-1))

class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.bit = [0]*n
    
    def add(self, i, w):
        x = i+1
        while x<=self.n:
            self.bit[x-1] += w
            x += x & -x
    
    def sum(self, i):
        ret = 0
        x = i+1
        while x>0:
            ret += self.bit[x-1]
            x -= x & -x
        return ret

bit = BinaryIndexedTree(n+1)
query.sort(key=lambda x:x[2])
last = [None]*n
ans = [None]*q
nr = -1
for idx, l, r in query:
    for cr in range(nr+1, r+1):
        if last[c[cr]] is not None:
            bit.add(last[c[cr]]+1, -1)
        last[c[cr]] = cr
        bit.add(cr+1, 1)
    nr = r
    ans[idx] = bit.sum(r+1) - bit.sum(l)
for i in ans:
    print(i)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    l = list(map(int,input().split()))
    dp = [0]+ [100000000000]*(n-1)

    for i in range(1,n):
        
        for j in range(1,m+1):
            if i-j >= 0:
                dp[i] = min(dp[i],dp[i-j]+abs(l[i]-l[i-j]))
        
    print(dp[n-1])

if __name__ == "__main__":
    main()    

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    l = list(map(int,input().split()))
    dp = [0]+ [100000000000]*(n-1)

    for i in range(1,n):
        
        for j in range(1,m+1):
            if i-j >= 0:
                dp[i] = min(dp[i],dp[i-j]+abs(l[i]-l[i-j]))
        
    print(dp[n-1])

if __name__ == "__main__":
    main()