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

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
n = int(input())
s = str(n)

INF = float('inf')
dp = [[INF,INF] for _ in range(len(s)+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(len(s)):
    dp[i+1][0] = min(dp[i][0]+int(s[i]), dp[i][1]+10-int(s[i]), dp[i][1]+int(s[i])+1)
    dp[i+1][1] = min(dp[i][0]+int(s[i])+1,dp[i][1]+10-int(s[i])-1)

print(dp[-1][0])


### FIXED CODE ###

s = input()
l = len(s)

INF = float('inf')
dp = [[INF]*2 for _ in range(l+1)]
dp[0][0]=0
dp[0][1]=1
for i in range(l):
    num = int(s[i])
    dp0 = dp[i][0]
    dp1 = dp[i][1]
    dp[i+1][0] = min(dp0+num, dp1+min(10-num,num+1))
    dp[i+1][1] = min(dp0+num+1,dp1+10-num-1)

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

from collections import defaultdict
from collections import deque
n = int(input())
tree = defaultdict(list)
for i in range(n-1):
    a, b, c = map(int, input().split())
    tree[a].append([b, c])
    tree[b].append([a, c])

def distance(x, y):
    seen = set()
    d = 0
    stack = deque([[tree[x], d]])
    flag = True
    while flag:
        connect, d = stack.popleft()
        for i in connect:
            if i[0] not in seen:
                seen.add(i[0])
                d += i[1]
                if i[0] == y:
                    flag = False
                    break
                stack.append([tree[i[0]], d])
                d -= i[1]
    return d

q, k = map(int, input().split())
dis_l = {}
for i in range(n):
    dis_l[i+1] = distance(i + 1, k)
for i in range(q):
    x, y = map(int, input().split())
    print(dis_l[x] + dis_l[y])

### FIXED CODE ###

from collections import defaultdict
from collections import deque
n = int(input())
tree = defaultdict(list)
for i in range(n-1):
    a, b, c = map(int, input().split())
    tree[a].append([b, c])
    tree[b].append([a, c])

def distance(k):
    seen = set()
    dis_l = {}
    d = 0
    stack = deque([[tree[k], d]])
    flag = True
    while stack:
        connect, d = stack.popleft()
        for i in connect:
            if i[0] not in seen:
                seen.add(i[0])
                d += i[1]
                dis_l[i[0]] = d
                stack.append([tree[i[0]], d])
                d -= i[1]
    return dis_l

q, k = map(int, input().split())
dis_l = distance(k)
for i in range(q):
    x, y = map(int, input().split())
    print(dis_l[x] + dis_l[y])
### BUGGY CODE ###

N, K = map(int, input().split(" "))
A = list(map(int, input().split(" ")))
A = [0] + A
for i in range(1, N + 1):
    A[i] += A[i - 1]
    A[i - 1] -= i - 1
A[N] -= N

rem_count = {i: 0 for i in range(K)}
rem_count[0] = 1
ans = 0
for i in range(1, N + 1):
    if i - K >= 0:
        rem_count[A[i - K] % K] -= 1
    ans += rem_count[A[i] % K]
    rem_count[A[i] % K] += 1

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().strip().split(" "))
A = list(map(int, input().strip().split(" ")))
A = [0] + A
for i in range(1, N + 1):
    A[i] += A[i - 1]
    A[i - 1] -= i - 1
A[N] -= N

rem_count = {}
rem_count[0] = 1
ans = 0
for i in range(1, N + 1):
    if i - K >= 0:
        rem_count[A[i - K] % K] -= 1
    if A[i] % K in rem_count:
        ans += rem_count[A[i] % K]
        rem_count[A[i] % K] += 1
    else:
        rem_count[A[i] % K] = 1

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

k = int(raw_input())
a = map(int,raw_input().split(" "))

if a[-1] != 2:
  print "-1"
  exit(0)

r = [2,3]
ainv = a[::-1]

for now in ainv[1:]:
  lower = (r[0]/now)*now
  if lower < r[0]:
    lower += now
  q = [lower,lower + now - 1]

  upper = lower + now - 1
  while (upper / now) * now <= r[1]:
    upper += 1
  upper -= 1

  if q[0] > r[1]:
    print "-1"
    exit(0)
  q = [lower,upper]
  #print r,q
  r = q

print "%d %d" % (r[0],r[1])


### FIXED CODE ###

k = int(raw_input())
a = map(int,raw_input().split(" "))

if a[-1] != 2:
  print "-1"
  exit(0)

r = [2,3]
ainv = a[::-1]

for now in ainv[1:]:
  lower = (r[0]/now)*now
  if lower < r[0]:
    lower += now
  upper = (r[1]/now)*now

  q = [lower,upper]

  if q[0] > r[1]:
    print "-1"
    exit(0)
  #print r,q
  q[1] = q[1] + now - 1
  r = q

print "%d %d" % (r[0],r[1])
### BUGGY CODE ###

n = int(input())
l_li = list(map(int,input().split()))
l_li.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if l_li[k] >= l_li[i]+l_li[j]:
                break
            if l_li[i] < l_li[j]+l_li[k] and l_li[j] < l_li[i]+l_li[k] and l_li[k] < l_li[i]+l_li[j]:
                ans += 1
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l_li = list(map(int,input().split()))
l_li.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        ind = bisect.bisect_left(l_li,l_li[i]+l_li[j])
        num = ind-1 - j
        if num > 0:
            ans += num
print(ans)
### BUGGY CODE ###

N=int(input())
A=[int(x) for x in input().split()]
A_s=set(A)
Com=0
for k in A_s:
    x=A.count(k)
    Com+=int(x*(x-1)/2)
    
for i in range(N):
    y=A.count(A[i])
    print(Com-y+1)

### FIXED CODE ###

from collections import Counter

N=int(input())
A=[int(x) for x in input().split()]
Com=0

A_C=Counter(A)

for name,x in A_C.items():
    Com+=int(x*(x-1)/2)
    
for i in range(N):
    y=A_C[A[i]]
    print(Com-y+1)
### BUGGY CODE ###

h,w=map(int,input().split())
s=set()
q=[]
for i in range(h):
    tmp=input()
    for j in range(w):
        if tmp[j]=="#":
            q.append((i,j))
            s.add((i,j))

ans=0
ll=[[0,1],[0,-1],[1,0],[-1,0]]
while q:
    l=[]
    for i,j in q:
        for x,y in ll:
            if i+x>=0 and i+x<h and j+y>=0 and j+y<w:
                if (i+x,j+y) not in s:
                    s.add((i+x,j+y))
                    l.append((i+x,j+y))
    q=l
    ans+=1

print(ans-1)





### FIXED CODE ###

h,w=map(int,input().split())
s=set()
a=[]
from collections import deque
q=deque([])
for i in range(h):
    tmp=list(input())
    a.append(tmp)
    for j in range(w):
        if tmp[j]=="#":
            q.append((i,j,0))

ans=0
ll=[[0,1],[0,-1],[1,0],[-1,0]]
while q:
    x,y,v=q.popleft()
    ans=max(ans,v)
    for i,j in ll:
        if 0<=x+i<h and 0<=y+j<w and a[i+x][j+y]==".":
            a[i+x][j+y]="#"
            q.append((i+x,j+y,v+1))

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

import io


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)



K = int(input())
ans = 0
for a in range(1,K+1):
   for b in range(1,K+1):
       for c in range(1,K+1):
           ans += gcd(c, gcd(a, b))

print(ans)

### FIXED CODE ###

import io


def gcd(a, b):
    while b > 0 :
        a, b = b, a%b

    return a


K = int(input())
ans = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            ans += gcd(c, gcd(a, b))

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

n = int(input())
mat = [list(map(int, input().split())) for _ in range(n)]
ans = 0
d = [[1] * n for _ in range(n)]
for i in range(n):
    for j, c2 in enumerate(row[i] for row in mat):
        for k, (c1, c3) in enumerate(zip(mat[j], mat[i])):
            if c1 > c2+c3:
                print(-1)
                exit(0)
            elif i != j and i != k and c1 == c2 + c3:
                d[j][k] = 0
for i in range(n):
    for j in range(n):
        if d[i][j]:
            ans += mat[i][j]
print(ans // 2)

### FIXED CODE ###

n = int(input())
mat = [list(map(int, input().split())) for _ in range(n)]
ans = 0
d = [[1] * n for _ in range(n)]
for i in range(n):
    for j, c2 in enumerate(row[i] for row in mat):
        for k, (c1, c3) in enumerate(zip(mat[j], mat[i])):
            if c1 > c2+c3:
                print(-1)
                exit(0)
            elif i != j and i != k and c1 == c2 + c3:
                d[j][k] = 0
for i in range(n):
    for j in range(n):
        if d[i][j]:
            ans += mat[i][j]
print(ans // 2)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
 
s = []
cnt = 0
n = 1
f = False
while cnt <= N:
  s.append(n)
  cnt += 1
  n = A[n - 1]
  if n == 2:
    f = True
    break
  elif s.count(n) != 0:
    break
print(cnt if f else -1)

### FIXED CODE ###

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

cnt = 0
n = 1
f = False
while cnt <= N:
  cnt += 1
  n = A[n - 1]
  if n == 2:
    f = True
    break
print(cnt if f else -1)
### BUGGY CODE ###

import math
def com(x, y):
    return math.factorial(x) // (math.factorial(x - y) * math.factorial(y))

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

P = a[n-1]//2
S = 0
T = 0

for i in range(n):
    if a[i] > P:
        S = a[i-1]
        T = a[i]
        break

if com(a[n-1],S) >= com(a[n-1],T):
    print(a[n-1],S)
else:
    print(a[n-1],T)

### FIXED CODE ###

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

P = a[n-1]/2
S = 0
T = 0

for i in range(n):
    if a[i] > P:
        S = a[i-1]
        T = a[i]
        break


if abs(S-P) <= abs(T-P):
    print(a[n-1],S)
else:
    print(a[n-1],T)
### BUGGY CODE ###

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

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

res = [0]
tmp = 0

for i in range(n):
    tmp = a[tmp] - 1
    if tmp in res:
        start = tmp
        break
    else:
        res = res + [tmp]

lenret = len(res)
stridx = res.index(start)

cycle = lenret - stridx

if stridx >= k:
    print(res[k]+1)
    exit()
else:
    k = k - stridx

    tmp = k % cycle

    print(res[stridx+tmp]+1)


### FIXED CODE ###

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

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

res = [0]
tmp = 0

tf = [-1 for i in range(n)]
tf[0] = 0

for i in range(n):
    tmp = a[tmp] - 1
    if tf[tmp] != -1:
        start = tmp
        break
    else:
        res.append(tmp)
        tf[tmp] = i+1

lenret = i+1
stridx = tf[start]

cycle = lenret - stridx

if stridx >= k:
    print(res[k]+1)
    exit()
else:
    k = k - stridx

    tmp = k % cycle

    print(res[stridx+tmp]+1)
### BUGGY CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import combinations, permutations

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


N = int(input())
xy1 = []
xy2 = []
for i in range(N):
	x, y = list(map(int, input().split()))
	xy1.append([x, i])
	xy2.append([y, i])
xy1.sort()
xy2.sort()

edge_list = [[] for _ in range(N)]

for i in range(N - 1):
	edge_list[xy1[i][1]].append([xy1[i + 1][0] - xy1[i][0], xy1[i + 1][1]])
	edge_list[xy1[i + 1][1]].append([xy1[i + 1][0] - xy1[i][0], xy1[i][1]])
	edge_list[xy2[i][1]].append([xy2[i + 1][0] - xy2[i][0], xy2[i + 1][1]])
	edge_list[xy2[i + 1][1]].append([xy2[i + 1][0] - xy2[i][0], xy2[i][1]])

judge = [0]*N
G = []
heapq.heapify(G)
for edge in edge_list[0]:
	heapq.heappush(G, edge)

judge[0] = 1
total = 0
num = 0
while num < N - 1:
	edge = heapq.heappop(G)
	if judge[edge[1]] == 0:
		judge[edge[1]] = 1
		total += edge[0]
		num += 1
		for add in edge_list[edge[1]]:
			if judge[add[1]] == 0:
				heapq.heappush(G, add)

print(total)

### FIXED CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import combinations, permutations

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


N = int(input())
xy1 = []
xy2 = []
for i in range(N):
	x, y = list(map(int, input().split()))
	xy1.append((x, i))
	xy2.append((y, i))
xy1.sort()
xy2.sort()

edge_list = [[] for _ in range(N)]

for i in range(N - 1):
	edge_list[xy1[i][1]].append((xy1[i + 1][0] - xy1[i][0], xy1[i + 1][1]))
	edge_list[xy1[i + 1][1]].append((xy1[i + 1][0] - xy1[i][0], xy1[i][1]))
	edge_list[xy2[i][1]].append((xy2[i + 1][0] - xy2[i][0], xy2[i + 1][1]))
	edge_list[xy2[i + 1][1]].append((xy2[i + 1][0] - xy2[i][0], xy2[i][1]))

judge = [0]*N
G = []
heapq.heapify(G)
for edge in edge_list[0]:
	heapq.heappush(G, edge)

judge[0] = 1
total = 0
num = 0
while num < N - 1:
	edge = heapq.heappop(G)
	if judge[edge[1]] == 0:
		judge[edge[1]] = 1
		total += edge[0]
		num += 1
		for add in edge_list[edge[1]]:
			if judge[add[1]] == 0:
				heapq.heappush(G, add)

print(total)
### BUGGY CODE ###

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

def gcd(m, n) :
    while n :
        m, n = n, m % n
    return m

ret = 0
x = gcd(A, B)
if x % 2 == 0 :
    ret += 1
    while x % 2 == 0 :
        x //= 2
        
i = 3
while x != 1 :
    flg = False
    while x % i == 0 :
        x //= i
        flg = True
        
    if flg :
        ret += 1
    i += 2
        
print(ret + 1)


### FIXED CODE ###

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

def gcd(m, n) :
    while n :
        m, n = n, m % n
    return m

ret = 0
x = gcd(A, B)
if x % 2 == 0 :
    ret += 1
    while x % 2 == 0 :
        x //= 2
        
i = 3
while i * i <= x :
    if x % i == 0 :
        ret += 1
        x //= i
        
    while x % i == 0 :
        x //= i
        
    i += 2

if x != 1 :
    ret += 1
print(ret + 1)
### BUGGY CODE ###

def classify(a,b,c,T):
    if T[a][1]!=T[b][1] and T[b][1]!=T[c][1] and T[c][1]!=T[a][1]:
        return 1
    else:
        return 0
X,Y,Z,K = map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
XY=[]
for a in A:
    for b in B:
        XY.append(a+b)
XY.sort(reverse=True)
XY_prime=XY[:K]
XYZ=[]
for xy in XY_prime:
    for c in C:
        XYZ.append(xy+c)
XYZ.sort(reverse=True)
for xyz in XYZ[:K]:
    print(xyz)


### FIXED CODE ###

X,Y,Z,K = map(int,input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)
xy=[]
for a in A:
    for b in B:
        xy.append(a+b)
xy=sorted(xy,reverse=True)
xy=xy[:K]
xyz=[]
for c in C:
    for x in xy:
        xyz.append(x+c)
xyz=sorted(xyz,reverse=True)
for i in range(K):
    print(xyz[i])
### BUGGY CODE ###

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

a=[]
b=[]
cnt=0
sum=0

for i in range(0,n):
    ta,tb = map(int,input().split())
    a.append(ta)
    b.append(tb)


while m>0:
    mindex = a.index(min(a))
    for i in range(0,b[mindex]):
        sum+=a[mindex]
        m-=1
        if m<=0:
            break
    del b[mindex]
    del a[mindex]

print(sum)

### FIXED CODE ###

n,m = map(int,input().split())
data = []
sum=0


for i in range(0,n):
    a,b = map(int,input().split())
    data.append((a,b))

data.sort()

while m>0:
    num = m if m<data[0][1] else data[0][1]
    sum+=data[0][0]*num
    m-=num
    del data[0]

print(sum)
### BUGGY CODE ###

from heapq import heappush, heappop
import sys
from __pypy__ import builders
readline = sys.stdin.readline
N, Q = map(int, readline().split())
U = [0]*N
qs = []
for i in range(N):
    s, t, x = map(int, input().split())
    qs.append((s-x, x, i, 1))
    qs.append((t-x, x, i, 0))
qs.sort()

b = builders.StringBuilder(Q)
que = []
j = 0
for i in range(Q):
    d = int(input())
    while j < 2*N and qs[j][0] <= d:
        _, x, i, m = qs[j]
        if m:
            heappush(que, (x, i))
        else:
            U[i] = 1
        j += 1
    while que and U[que[0][1]]:
        heappop(que)
    if que:
        b.append("%d\n" % que[0][0])
    else:
        b.append("-1\n")
sys.stdout.write(b.build())

### FIXED CODE ###

from heapq import heappush, heappop
import sys
from __pypy__ import builders
readline = sys.stdin.readline
N, Q = map(int, readline().split())
qs = [0]*N
for i in range(N):
    s, t, x = map(int, readline().split())
    qs[i] = (s-x, t-x, x)
qs.sort()

b = builders.StringBuilder(Q)
que = []
D = [int(readline()) for i in range(Q)]
j = 0
for d in D:
    while j < N and qs[j][0] <= d:
        s, t, x = qs[j]
        heappush(que, (x, t))
        j += 1
    while que and que[0][1] <= d:
        heappop(que)
    if que:
        b.append("%d\n" % que[0][0])
    else:
        b.append("-1\n")
sys.stdout.write(b.build())
### BUGGY CODE ###

L, R = [int(x) for x in input().split()]


res = []
for i in range(L, R + 1):
    for j in range(i + 1, R + 1):
        res.append((i * j) % 2019)
print(min(res))

### FIXED CODE ###

L, R = [int(x) for x in input().split()]


res = 2018
for i in range(L, R + 1):
    for j in range(i + 1, R + 1):

        tmp = (i * j) % 2019
        if tmp == 0:
            print(0)
            exit()
        if tmp < res:
            res = tmp

print(res)
### BUGGY CODE ###

t = input()
keep = True
keeped_ones = 0
n0 = 0
ones = [] # (number of zeros before 1, is_odd)
for i, x in enumerate(t):
    if x == '0':
        n0 += 1
        keep = True
    elif x == '1':
        if keep:
            ones.append((n0, (i+1)%2))
            keep = False
        else:
            keeped_ones += 1
            ones = ones[:-1]
            keep = True

ans = keeped_ones * n0
for n0_before, is_odd in ones:
    ans += (n0_before + is_odd)//2 + (n0 - n0_before)
ans += (keeped_ones + (len(ones)+1)//2) * (keeped_ones + len(ones)//2 + 1)
print(ans)

### FIXED CODE ###

t = input()
before_is_zero = True
keeped_ones = 0
n0 = 0
ones = [0] * int(1e5+1) # (number of zeros before 1, is_odd)
ones_index = 0
for i, x in enumerate(t):
    if x == '0':
        n0 += 1
        before_is_zero = True
    elif x == '1':
        if before_is_zero:
            ones[ones_index] = (n0, (i+1)%2)
            ones_index += 1
            before_is_zero = False
        else:
            keeped_ones += 1
            ones_index -= 1
            before_is_zero = True

if before_is_zero:
    if len(ones) > 0:
        ones = ones[:-1]

ans = keeped_ones * n0
for i in range(ones_index):
    n0_before, is_odd = ones[i]
    ans += (n0_before + is_odd)//2 + (n0 - n0_before)
ans += (keeped_ones + (ones_index+1)//2) * (keeped_ones + ones_index//2 + 1)
print(ans)
### BUGGY CODE ###

def main():
    S = input()
    con = 10**9 + 7

    ns = list(range(10))
    c = []
    iii = 1
    for i in range(len(S)):
        s = S[len(S) - i - 1]
        if s != "?":
            c.append([(int(s) * iii) % 13])
            iii = (iii * 10) % 13
            continue
        c.append([(j * iii) % 13 for j in ns])
        iii = (iii * 10) % 13

    _tdp = {i: 0 for i in range(13)}
    it = iter(c)
    pdp = {i: 1 for i in next(it)}
    d = 0
    for v in it:
        tdp = _tdp.copy()
        for r in v:
            for _r, _v in pdp.items():
                tdp[(_r + r) % 13] += _v
        if d == 0:
            for i in range(13):
                tdp[i] %= con
        d = (d + 1) % 50
        pdp = tdp

    ans = pdp.get(5, 0)
    print(ans % con)

if __name__ == "__main__":
    main()

### FIXED CODE ###

S = input()
con = 10**9 + 7

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

def get_mod(S):
    c = {}
    iii = 1
    for i in range(len(S)):
        if S[len(S) - i - 1] != "?":
            iii *= 10
            iii %= 13
            continue
        c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
        iii *= 10
        iii %= 13
    return c
c = get_mod(S)

def get_tdp(pdp):
    tdp = {i: 0 for i in range(13)}
    for r in v.keys():
        for _r, _v in pdp.items():
            tdp[(_r + r) % 13] += _v
    for i in range(13):
        tdp[i] %= con
    return tdp

pdp = {i: 0 for i in range(13)}
pdp[SS] += 1
for k, v in c.items():
    pdp = get_tdp(pdp)

ans = pdp[5]
print(ans)
### BUGGY CODE ###

import sys
import math
import time
import numpy
sys.setrecursionlimit(int(1e6))
#dprint = print
def dprint(*args):
    pass

N, Q = list(map(int, input().split()))
c = list(map(int, input().split()))
dprint('c=', c)

while(Q > 0):
    l, r = list(map(int, input().split()))
    h = {}
    for i in range(l-1, r):
        key = c[i]
        h[key] = 1
    dprint('l, r=', l, r)
    dprint('h=', h)
    print(len(h))
    Q = Q - 1



### FIXED CODE ###


import sys
import math
import time
sys.setrecursionlimit(int(1e6))
if False:
    dprint = print
else:
    def dprint(*args):
        pass

class BIT:
    def __init__(self, n=0):
        self.n = n
        self.d = [0] * (n+1)
    
    def add(self, i, x=1):
        i = int(i+1) # index begin 1
        while i <= self.n:
            self.d[i] += x
            i += i&-i # add LSB
    
    def sum(self, i=None):
        x = 0
        i = int( i+1 if not (i is None) else self.n )
        while i > 0:
            x += self.d[i]
            i -= i&-i # sub LSB
        return x

n, q = list(map(int, input().split()))
c = list(map(int, input().split()))
dprint("n, q =", n, q)
dprint("c =", c)

# check colors pair index (s,t)
st = [0] * (n+1)
col_last = [0] * (n+1)
for i in range(n):
    t = i + 1
    col = c[i]
    s = col_last[col]
    if s > 0:
        st[s] = t
    col_last[col] = t
dprint("st =", st)

# input querys (l,r)
lr = [None] * n
qs = list()
sorted_qs = list()
for i in range(q):
    l, r = list(map(int, input().split()))
    qs.append((i,l,r)) 
sorted_qs = sorted(qs, key=lambda q: q[1], reverse=True)
dprint("qs =", qs)
dprint("sorted_qs =", sorted_qs)

i_qs = 0
x = n
d = BIT(n+1)
qs_ans = [0] * len(qs)
for i_qs in range(len(sorted_qs)):
    i, l, r = sorted_qs[i_qs]
    dprint("i, l, r", i, l, r)
    while (x >= l):
        if st[x] > 0:
            d.add(st[x])
            dprint("add x(s), t =", x, st[x])
        x -= 1
    qs_ans[i] = (r-l+1)-d.sum(r)

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

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


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
m=[0]*n
for i in l:
    m[i-1]+=1
for j in range(n):
    print(m[j])
### BUGGY CODE ###

def dijkstra_back(s,t,n,w,cost):
    #sからtへの最短経路の経路復元
    prev = [s] * n #最短経路の直前の頂点
    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
        
        for i in range(n):
            if d[i] > d[v] + cost[v][i]: 
                d[i] = d[v] + cost[v][i]
                prev[i] = v
        
    path = [t]
    while prev[t] != s:
        path.append(prev[t])
        prev[t] = prev[prev[t]]
    path.append(s)
    path = path[::-1]
    return path

################################
n,w = map(int,input().split()) #n:頂点数　w:辺の数

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(w):
    x,y = map(int,input().split())
    x-=1
    y-=1
    cost[x][y] = 1
    cost[y][x] = 1
sp = [0 for _ in range(n-1)]

for i in range(1,n):
    sp[i-1] = dijkstra_back(0,i,n,w,cost)

sp.sort()
#print(*sp)
sg = [-1 for _ in range(n)]
for l in sp:
    for j in range(len(l)):
        x = l[j]
        if j != 0:
            #print(l,x)
            if sg[x] == -1:
                sg[x] = l[j-1]
            elif sg[x] !=  l[j-1]:
                print('No')
                exit()

print('Yes')
for i in range(1,n):
    print(sg[i]+1)



### FIXED CODE ###

from collections import deque



n,m = map(int,input().split())
ab = [[] for _ in range(m)]
kr = [[] for _ in range(n)]
dist = [-1 for _ in range(n)]
dist[0] = 0
ans = [-1 for _ in range(n)]
qn = deque([1])
for i in range(m):
    a,b = map(int,input().split())
    a,b = min(a,b),max(a,b)
    ab[i] = [a,b]
    kr[a-1].append(b)
    kr[b-1].append(a)

dis = 1
while len(qn) > 0:
    v = qn.popleft()
    d = dist[v-1]
    for w in kr[v-1]:
        if dist[w-1] > -1:
            continue
        dist[w-1] = d + 1
        qn.append(w)
        ans[w-1] = v


#print(dist)

#ab.sort()
#print(ab)
#print(kr)

print('Yes')
for i in range(1,n):
    print(ans[i])
### BUGGY CODE ###

N,K = [int(x) for x in input().split()]
H = [int(x) for x in input().split()]

INF = 10**20
dp = [INF] * N
dp[0] = 0

for i in range(0, N - 1):
    for k in range(0, min(i + 1, K)):
        if dp[i + 1] > dp[i - k] + abs(H[i + 1] - H[i - k]):
            dp[i + 1] = dp[i - k] + abs(H[i + 1] - H[i - k])

print(dp[N-1])

### FIXED CODE ###

N,K = [int(x) for x in input().split()]
H = [int(x) for x in input().split()]

INF = 10**9
dp = [INF] * N
dp[0] = 0

for i in range(0, N - 1):
    for k in range(0, min(i + 1, K)):
        if dp[i + 1] > dp[i - k] + abs(H[i + 1] - H[i - k]):
            dp[i + 1] = dp[i - k] + abs(H[i + 1] - H[i - k])


print(dp[N - 1])