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

N = int(input())
S = []
chars = 'abcdefghijklmnopqrstuvwxyz'

for i in range(N):
    s = input()
    S.append(int(''.join([str(s.count(a)) for a in chars])))

count = 0
for i in range(N-1):
    for j in range(i+1, N):
        count += 1 if S[i]==S[j] else 0

print(count)

### FIXED CODE ###

N = int(input())
S = []

for i in range(N):
    s = input()
    S.append(''.join(sorted(s)))

S.sort()
count = 0
sw = 0
series = []
for i in range(1, len(S)):
    if S[i-1]==S[i]:
        sw = 1
        count += 1
    else:
        if sw==1:
            count += 1
            series.append(count)
            count = 0
            sw = 0
if sw==1:
    count += 1
series.append(count)

count = int(sum([c * (c-1)/2 for c in series]))

print(count)
### BUGGY CODE ###

import math

x = int(input())
m = 100
count = 1

while True:
    depo = math.floor(m*1.01)
    if depo >= x:
        print(count)
        break
    count += 1

### FIXED CODE ###

import math

x = int(input())
depo = 100
count = 1

while True:
    depo = math.floor(depo*1.01)
    if depo >= x:
        print(count)
        break
    count += 1
### BUGGY CODE ###

from itertools import accumulate
n,k = list(map(int,input().split()))
p = list(map(int,input().split()))

P = [(list(accumulate([x for x in range(i+1)]))[-1])/i for i in p]
ans = max([sum(P[i:i+k]) for i in range(n-k+1)])

print(ans)


### FIXED CODE ###

from itertools import accumulate
n,k = list(map(int,input().split()))
p = list(map(int,input().split()))

P = list(accumulate([(i+1)/2 for i in p]))
P = [0] + P
ans = max([P[i+k]-P[i] for i in range(n-k+1)])
print(ans)
### BUGGY CODE ###

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

import sys

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

mx = 0
d = {}
r = []

for a in A:
    if not a in d:
        d[a] = 0
    d[a] += 1
    if d[a] > mx:
        r = [a]
        mx = d[a]
    elif d[a] == mx:
        if not a in r:
            r.append(a)

r.sort()
for i in r:
    print(i)


### FIXED CODE ###

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

import sys

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

mx = 0
d = {}
r = []

for a in A:
    if not a in d:
        d[a] = 0
    d[a] += 1
    if d[a] > mx:
        r = [a]
        mx = d[a]
    elif d[a] == mx:
        r.append(a)

r.sort()
for i in r:
    print(i)
### BUGGY CODE ###

from collections import deque
import copy
H, W = map(int,input().split())

A = [[False for _ in range(W)] for _ in range(H)]

Q = deque()
for y in range(H):
    S = input()
    for x, s in enumerate(S):
        if s == "#":
            Q.append((y, x))
            A[y][x] = True

ans = 0
while True:
    ans += 1
    NQ = deque()
    while Q:
        y, x = Q.pop()
        if x > 0 and A[y][x-1] == False:
            A[y][x-1] = True
            NQ.append((y,x-1))
        if x < W-1 and A[y][x+1] == False:
            A[y][x+1] = True
            NQ.append((y,x+1))
        if y > 0 and A[y-1][x] == False:
            A[y-1][x] = True
            NQ.append((y-1, x))
        if y < H-1 and A[y+1][x] == False:
            A[y+1][x] = True
            NQ.append((y+1,x))
    if NQ:
        Q = copy.copy(NQ)
    else:
        break

print(ans-1)

### FIXED CODE ###

def main():
    H, W = map(int,input().split())

    A = [[False for _ in range(W)] for _ in range(H)]

    Q = []
    for y in range(H):
        S = input()
        for x, s in enumerate(S):
            if s == "#":
                Q.append((y, x))
                A[y][x] = True

    ans = 0
    while Q:
        ans += 1
        NQ = []
        for y, x in Q:
            if x > 0 and A[y][x-1] == False:
                A[y][x-1] = True
                NQ.append((y,x-1))
            if x < W-1 and A[y][x+1] == False:
                A[y][x+1] = True
                NQ.append((y,x+1))
            if y > 0 and A[y-1][x] == False:
                A[y-1][x] = True
                NQ.append((y-1, x))
            if y < H-1 and A[y+1][x] == False:
                A[y+1][x] = True
                NQ.append((y+1,x))
        if NQ:
            Q = NQ
        else:
            break

    print(ans-1)

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

n = int(input())
a = [int(input()) for i in range(n)]

for i in range(n):
  b = a[0:i]
  c = a[i+1:]
  if len(b) > 0:
    b = max(b)
  else:
    b = 0
  if len(c) > 0:
    c = max(c)
  else:
    c = 0

  if b > c:
    print(b)
  else:
    print(c)
  """
  # 遅すぎる
  b = a.copy()
  del b[i]
  print(max(b))
  # 遅すぎる2
  b = a[0:i]
  c = a[i+1:]
  b += c
  print(max(b))
  """

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

# ほとんどは全体のmax?
m1 = max(a)

# max値が多い場合用に2nd max
m2 = sorted(a)[n-2]

for i in range(n):
  if a[i] == m1:
    print(m2)
  else:
    print(m1)
### BUGGY CODE ###

import sys

lines = sys.stdin.readlines()

X = lines[0].split(' ')
N = int(X[0])
M = int(X[1])

H = []
Y = []

for i in range(N):
    H.append(int(lines[1].split(' ')[i]))

for j in range(M):
    A = int(lines[j+2].split(' ')[0])
    B = int(lines[j+2].split(' ')[1])
    if int(H[A-1]) <= int(H[B-1]):      
      Y.append(A-1)
    if int(H[B-1]) <= int(H[A-1]):
      Y.append(B-1)
Z = len(set(Y))
print(N-Z)

### FIXED CODE ###

import sys

lines = sys.stdin.readlines()

X = lines[0].split(' ')
N = int(X[0])
M = int(X[1])

H = []
Y = []

H=lines[1].split(' ')

for j in range(M):
    A = int(lines[j+2].split(' ')[0])
    B = int(lines[j+2].split(' ')[1])
    if int(H[A-1]) <= int(H[B-1]):      
      Y.append(A-1)
    if int(H[B-1]) <= int(H[A-1]):
      Y.append(B-1)
Z = len(set(Y))
print(N-Z)
### BUGGY CODE ###

# 小さいのでメモ化再帰でいけるか？
# （[ここまでの回答数, ここまでの点数]みたいなやつ）
# んーーーーーー？？？？ RE*1、あとTLEになる。。。
# REはどうせ再帰の制限
import sys

sys.setrecursionlimit(10 ** 8)

d, g = map(int, input().split())
memo = {}
points, bonus = [], []
for _ in range(d):
    p, c = map(int, input().split())
    points.append(p)
    bonus.append(c)


def f(c, p):
    # if (c, p) in memo:
    #     return memo[(c, p)]
    if p >= g:
        return c
    ret = 10 ** 10
    for i in range(d):
        if points[i] == 1:
            points[i] = 0
            ret = min(ret, f(c + 1, p + (i + 1) * 100 + bonus[i]))
            points[i] = 1
        elif points[i] > 1:
            points[i] -= 1
            ret = min(ret, f(c + 1, p + (i + 1) * 100))
            points[i] += 1
        elif points[i] == 0:
            continue
        else:
            print(3 / 0)
    memo[(c, p)] = ret
    return ret


print(f(0, 0))


### FIXED CODE ###

# 未知のアルゴリズムか天才系DPかと思ってすぐ諦めて解説読んでしまった

d, g = map(int, input().split())
points = []
for _ in range(d):
    p, c = map(int, input().split())
    points.append((p, c))
ans = 10**12
for bit in range(2**d):
    arr = [False] * d
    for i in range(d):
        if bit >> i & 1 == 1:
            arr[i] = True
    tmp_sum = 0
    count = 0
    for i in range(d):
        if arr[i]:
            # kompuli-to
            tmp_sum += points[i][1]
            tmp_sum += (i + 1) * 100 * points[i][0]
            count += points[i][0]
    if tmp_sum < g:
        # 達成できるまで得点の高いやつからやっていく
        for i in range(d - 1, -1, -1):
            if arr[i]:
                # すでにkompuli-toしてるので
                continue
            used = 0
            for j in range(points[i][0]):
                if tmp_sum < g:
                    tmp_sum += (i + 1) * 100
                    count += 1
                    used += 1
            if used == points[i][0]:
                tmp_sum += points[i][1]
            if tmp_sum >= g:
                break
    ans = min(ans, count)
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
 
ans = 0
for i in range(N-K+1):
  ans = max(ans, (sum(p[i:i+K])+K)/2)
  
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
  
# 「和の期待値」は「期待値の和」なので、先に期待値を求める
for i in range(N):
  p[i] = (1+p[i])/2

# 累積和
S = [0]*N
S[0] = p[0]
for i in range(N-1):
  S[i+1] = S[i] + p[i+1]

ans = S[K-1]
for i in range(N-K):
  ans = max(ans, S[i+K] - S[i])

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

# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))

    if n == 0:
        return '1' if A[0] == 1 else '-1'

    ret = 0
    R = np.zeros(n+1, int)
    R[0] = 1-A[0]
    left = 0
    for i in range(1, n+1):
        R[i] = 2*R[i-1]

        for _ in range(A[i]):
            if R[i] <= 0:
                return '-1'

            R[left:i+1] -= 1
            ret += 1+i-left
            left = left+np.searchsorted(R[left:i], 0, side='right')

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))

    if 0 < A[0]:
        return '1' if n == 0 and A[0] == 1 else '-1'

    R = [0]*(n+1)
    R[0] = 1
    for i in range(1, n+1):
        R[i] = 2*(R[i-1]-A[i-1])

    prev = 0
    ret = 0
    for i in range(n, -1, -1):
        if R[i] < A[i]:
            ret = -1
            break

        prev = min(R[i], A[i]+prev)
        ret += prev

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

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

dp=[False]*(k+1)

for i in range(1,len(dp)):
  for x in a:
    if i-x>=0:
      dp[i]|=not dp[i-x]

print(("Second","First")[dp[k]])

### FIXED CODE ###

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

dp=[False]*(k+1+max(a))

for i in range(1+k):
  if not dp[i]:
    for x in a:
      dp[i+x]=True

print(("Second","First")[dp[k]])
### BUGGY CODE ###

n = int(input())
a = [int(a) for a in input().split()]
aans =0
for i in range(n):
  ans=0
  for ii in range (i,n-1):
    if a[ii] >= a[ii+1]:
      ans +=1
    else:
      break
  if ans >aans:
    aans =ans
print(aans)
    
    

### FIXED CODE ###

n = int(input())
a = [int(a) for a in input().split()]
aans =0
ans =0
for i in range(n-1):
  if a[i] >= a[i+1]:
    ans +=1
  else :
    if ans >aans:
      aans =ans
      ans = 0
    else :
      ans =0
if ans >aans:
  aans =ans
print(aans)
### BUGGY CODE ###

N, B, R = map(int, input().split())
sum_B = 0
sum = 0
while 1:
  sum += (B + R)
  sum_B += B
  if sum > N:
    if (sum - N) > R:
      sum_B -= ((sum - N) - R)
      print(sum_B)
      break
    else:
      print(sum_B)
      break
    

### FIXED CODE ###

N, B, R = map(int, input().split())
sum_B = (N // (B+R)) * B
n = N % (B+R)
if n == 0:
  print(sum_B)
elif n > B:
  sum_B += B
  print(sum_B)
else:
  sum_B += n
  print(sum_B)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = int(1e+9 + 7)
a = sorted(a)

def main():
    kai = [1]*(n+1)
    gyaku = [1]*(n+1)
    
    for i in range(2, n+1):
        kai[i] = kai[i-1]*i % mod
        gyaku[i] = gyaku[i-1]*pow(i, mod-2, mod) %mod
    
    answer = 0
    for i in range(n-k+1):
        for j in range(i+k-1,n):
            answer = (answer + (((a[j] - a[i])%mod * kai[j-i-1])%mod *gyaku[j-i-1-(k-2)])%mod * gyaku[k-2])%mod
    
    if k == 1:
        print(0)
    else:
        print(answer)
        
if __name__ == "__main__":
    main()

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = int(1e+9 + 7)
a = sorted(a)

kai = [1]*(n+1)
gyaku = [1]*(n+1)

for i in range(2, n+1):
    kai[i] = kai[i-1]*i % mod
    gyaku[i] = gyaku[i-1]*pow(i, mod-2, mod) %mod

answer = 0
for i in range(k-1,n):
    answer = (answer + a[i] * kai[i] * gyaku[(i)-(k-1)] * gyaku[k-1]) % mod

answer2 = 0
for i in range(n-k+1):
    answer2 = (answer2 + a[i] * kai[n-i-1] * gyaku[(n-i)-k] * gyaku[k-1]) % mod


if k == 1:
    print(0)
else:
    print((answer - answer2)%mod)
### BUGGY CODE ###

a, b = map(int, input().split())
ans = 0

for i in range(1, min(a, b) + 1):
    if a % i == 0 and b % i == 0:
        if i == 1:
            ans += 1
        else:
            for s in range(2, i // 2 + 1):
                if i % s == 0:
                    break
            else:
                ans += 1

print(ans)

### FIXED CODE ###

import math
from fractions import gcd

a, b = map(int, input().split())
cd = set()
ans = set()

'''
g = gcd(a, b)

for i in range(1, g+1):
    if a % i == 0 and b % i == 0:
        cd.add(i)
        '''

i =  1
a_set = set()

for i in range(1, int(math.sqrt(a)) + 1):
    if a % i == 0:
        a_set.add(i)
        a_set.add(a // i)
    i += 1

i = 1
b_set = set()

for i in range(1, int(math.sqrt(b)) + 1):
    if b % i == 0:
        b_set.add(i)
        b_set.add(b // i)
    i += 1

cd = set(a_set) & set(b_set)

for s in sorted(list(cd)):
    if s == 1:
        ans.add(s)
    else:
        for t in sorted(list(ans)):
            if t == 1:
                continue
            elif s % t == 0:
                break
        else:
            ans.add(s)

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

#n,x=map(int,input().split())
#a=[int(i) for i in input().split()]
import string
alp=string.ascii_lowercase
di={}
for i in range(26):
    di[alp[i]]=i
s=input()
a=[]
for i in s:
    a.append(i)
l=a.pop()
if a:
    a=a[::-1]
k=int(input())
ans=''
i=0
while a:
    t=a.pop()
    d=(26-di[t])%26
    if d<=k:
        k-=d
        ans+='a'
    else:
        ans+=t
    i+=1
ans+=alp[(alp.index(l)+k%26)%26]
print(ans)

### FIXED CODE ###

#n,x=map(int,input().split())
#a=[int(i) for i in input().split()]
import string
alp=string.ascii_lowercase
di={}
for i in range(26):
    di[alp[i]]=i
s=input()
a=[]
for i in s:
    a.append(i)
l=a.pop()
if a:
    a=a[::-1]
k=int(input())
ans=''
i=0
while a:
    t=a.pop()
    d=(26-di[t])%26
    if d<=k:
        k-=d
        ans+='a'
    else:
        ans+=t
    i+=1
kk=k%26
ans+=alp[(alp.index(l)+kk)%26]
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
list1=list(map(int,input().split()))
list2=[]
for _ in range(M):
  B,C=map(int,input().split())
  list2+=[C]*B
list3=list1+list2
list4=sorted(list3,reverse=True)
list5=list4[:N]
SUM=sum(list5)
print(SUM)

### FIXED CODE ###

N,M = map(int, input().split())
listA = list(map(int, input().split()))
listA.sort()
 
listBC = [list(map(int, input().split())) for i in range(M)]
listBC = sorted(listBC, key=lambda x: x[1], reverse=True)
countB = 0
 
for i in range(M):
  B, C = listBC[i][0], listBC[i][1]
  listA += [C]*B
  countB += B
  if countB >= N:
    break

listA.sort(reverse=True)
print(sum(listA[:N]))
### BUGGY CODE ###



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

def cmp(a,b):
    if len(a) > len(b):
        return False
    elif len(a) < len(b):
        return True
    else:
        if int(a) >= int(b):
            return False
        else:
            return True

dp = [""] * (N+100)
l = [0,2,5,5,4,5,6,3,7,6]

for i in range(N+1):
    for s in A:
        if dp[i] == "" and i!=0:
            continue
        ss = dp[i] + s
        if cmp(dp[i + l[int(s)]] , ss):
            dp[i + l[int(s)]] = ss
            

print(dp[N])


                





### FIXED CODE ###

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

dp = [-1 for i in range(N+10)]
l = [0,2,5,5,4,5,6,3,7,6]
dp[0] = 0
for i in range(N-1):
    for s in A:
        if dp[i] == -1 and i!=0:
            continue
        if dp[i + l[s]] < dp[i]*10+s:
            dp[i + l[s]] = dp[i]*10+s
print(dp[N])
### BUGGY CODE ###

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

r, c, k = map(int, input().split())
itm = [[0]*(c) for _ in range(r)]
for i in range(k):
    ri, ci, vi = map(int, input().split())
    itm[ri-1][ci-1] = vi

dp0 = [[0]*4 for c_ in range(3005)]
dp1 = [[0]*4 for c_ in range(3005)]

for i in range(r):
    for j in range(c):
        nowv = itm[i][j]
        dp0[j][3] = max(dp0[j][3], dp0[j][2] + nowv)
        dp0[j][2] = max(dp0[j][2], dp0[j][1] + nowv)
        dp0[j][1] = max(dp0[j][1], dp0[j][0] + nowv)

        dp0[j+1][0] = max(dp0[j+1][0], dp0[j][0])
        dp0[j+1][1] = max(dp0[j+1][1], dp0[j][1])
        dp0[j+1][2] = max(dp0[j+1][2], dp0[j][2])
        dp0[j+1][3] = max(dp0[j+1][3], dp0[j][3])

        dp1[j][0] = max(dp1[j][0], max(dp0[j]))
    dp0 = dp1.copy()

print(max(dp1[c-1]))


### FIXED CODE ###

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

r, c, k = map(int, input().split())
itm = [[0]*(c) for _ in range(r)]
for i in range(k):
    ri, ci, vi = map(int, input().split())
    itm[ri-1][ci-1] = vi

dp0 = [[0]*4 for c_ in range(3005)]
dp1 = [[0]*4 for c_ in range(3005)]

for i in range(r):
    for j in range(c):
        nowv = itm[i][j]
        dp0[j][3] = max(dp0[j][3], dp0[j][2] + nowv)
        dp0[j][2] = max(dp0[j][2], dp0[j][1] + nowv)
        dp0[j][1] = max(dp0[j][1], dp0[j][0] + nowv)

        dp0[j+1][0] = max(dp0[j+1][0], dp0[j][0])
        dp0[j+1][1] = max(dp0[j+1][1], dp0[j][1])
        dp0[j+1][2] = max(dp0[j+1][2], dp0[j][2])
        dp0[j+1][3] = max(dp0[j+1][3], dp0[j][3])

        dp1[j][0] = max(dp1[j][0], max(dp0[j]))
    dp0 = dp1.copy()

print(max(dp1[c-1]))
### BUGGY CODE ###



h, w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
diff = [[0]*(w+1) for i in range(h+1)]

for i in range(h):
    for j in range(w):
        diff[i][j] = abs(a[i][j] - b[i][j])

n = 80 * 80 + 1
dp = [[False]*n for i in range(h*w)]
dp[0][diff[0][0]] = True

for k in range(h*w):
    for cnt in range(n):
        if dp[k][cnt]:
                i = k // w
                j = k % w
                tmp1 = diff[i+1][j]
                tmp2 = diff[i][j+1]
                if i+1 < h:
                    dp[k + w][abs(cnt - tmp1)] = True
                    if cnt + tmp1 < n:
                        dp[k + w][cnt + tmp1] = True

                if j+1 < w:
                    dp[k + 1][abs(cnt - tmp2)] = True 
                    if cnt + tmp2 < n:
                        dp[k + 1][cnt + tmp2] = True

for i, boo in enumerate(dp[w*h - 1][0:81]):
    if boo:
        print(i)
        exit()
print(a[10*9])

### FIXED CODE ###

import sys
input = sys.stdin.readline


h, w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]

diff = [[0]*(w) for i in range(h)]
for i in range(h):
    for j in range(w):
        diff[i][j] = abs(a[i][j] - b[i][j])

dp = [0] * (h*w)
dp[0] |= 1 << (13000 + diff[0][0])
dp[0] |= 1 << (13000 - diff[0][0])

for k in range(h*w):
    i = k // w
    j = k % w
    if i+1 < h:
        tmp1 = diff[i+1][j]
        dp[k + w] |= dp[k] << tmp1
        dp[k + w] |= dp[k] >> tmp1       
    if j+1 < w:
        tmp2 = diff[i][j+1]
        dp[k + 1] |= dp[k] << tmp2
        dp[k + 1] |= dp[k] >> tmp2


ans = 10**9
for i in range(81):
    if dp[w*h - 1] >> 13000 + i & 1:
        ans = min(ans, i)
for i in range(81):
    if dp[w*h - 1] >> 13000 - i & 1:
        ans = min(ans, i) 
print(ans)
### BUGGY CODE ###

N,W=map(int,input().split())
l=[]
for _ in range(N):
  L=list(map(int,input().split()))
  l.append(L)
dp=[[0 for i in range(W+1)] for i in range(N+1)]
for i in range(1,N+1):
  for j in range(W+1):
    if j>=l[i-1][0]:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-l[i-1][0]]+l[i-1][1])
    else:dp[i][j]=dp[i-1][j]
print(dp[N][W])

### FIXED CODE ###

N,W=map(int,input().split())
l=[]
for _ in range(N):
  L=list(map(int,input().split()))
  l.append(L)
dp=[[0 for i in range(W+1)] for i in range(N+1)]
for i in range(1,N+1):
  for j in range(W+1):
    if j>=l[i-1][0]:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-l[i-1][0]]+l[i-1][1])
    else:dp[i][j]=dp[i-1][j]
print(dp[N][W])
### BUGGY CODE ###

import re

class Node:
  key = None
  left = None
  right = None
  def __init__(self, k):
    self.key = k

class BST:
  root = None
  def insert(self, k):
    x = self.root
    y = None
    z = Node(k)
    while x is not None:
      y = x
      if z.key < y.key:
        x = x.left
      elif y.key < z.key:
        x = x.right
    
    if y is None:
      # 初回値
      self.root = z
    else:
      if z.key < y.key:
        y.left = z
      elif y.key < z.key:
        y.right = z
        
  def inorder(self):
    # 中間巡回順で出力
    # 単純にソートでいいのでは
    return sorted(self.preorder())
    
  def preorder(self):
    # 先行巡回順で出力
    res = []
    cur_node = self.root
    right_successor = []
    left_successor = []
    # 現在の木がなにもない場合
    if cur_node is None:
      return res
    # そうでない場合
    while cur_node is not None:
      res.append(cur_node.key)
      # 次に調べるやつを追加する
      if cur_node.left is not None:
        left_successor.append(cur_node.left)
      if cur_node.right is not None:
        right_successor.append(cur_node.right)
      # 次に調べるやつを左、右の順でやっていく
      cur_node = left_successor.pop() if len(left_successor) > 0 else right_successor.pop() if len(right_successor) else None
    return res
n = int(input())
bst = BST()
for _ in range(n):
  query = [int(x) if re.match('[+|-]?\d', x) else x for x in input().split()]
  if query[0] == 'insert':
    bst.insert(query[1])
  elif query[0] == 'print':
    ans = bst.inorder()
    print(" " + " ".join(list(map(str, ans))))
    ans = bst.preorder()
    print(" " + " ".join(list(map(str, ans))))


### FIXED CODE ###

class Node:
  key = None
  left = None
  right = None
  def __init__(self, k):
    self.key = k

class BST:
  root = None
  def insert(self, k):
    x = self.root
    y = None
    z = Node(k)
    while x is not None:
      y = x
      if z.key < y.key:
        x = x.left
      elif y.key < z.key:
        x = x.right
    
    if y is None:
      # 初回値
      self.root = z
    else:
      if z.key < y.key:
        y.left = z
      elif y.key < z.key:
        y.right = z

  def inorder(self, r, lis):
    # 中間巡回順で出力
    if r != None:
      self.inorder(r.left, lis)
      lis.append(r.key)
      self.inorder(r.right, lis)


  def preorder(self, r, lis):
    # 先行巡回順で出力
    if r != None:
      lis.append(r.key)
      self.preorder(r.left, lis)
      self.preorder(r.right, lis)

    
n = int(input())
bst = BST()
for _ in range(n):
  # query = [int(x) if re.match('[+|-]?\d', x) else x for x in input().split()]
  query = input().split()
  if query[0] == 'insert':
    bst.insert(int(query[1]))
  elif query[0] == 'print':
    root = bst.root
    in_lis = []
    pre_lis = []
    bst.preorder(root, pre_lis)
    bst.inorder(root, in_lis)
    print(" " + " ".join(list(map(str, in_lis))))
    print(" " + " ".join(list(map(str, pre_lis))))
### BUGGY CODE ###

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

### FIXED CODE ###

def solve():
  n,k=[int(i) for i in input().split()]
  step=[int(i) for i in input().split()]
  dp=[0]*n
  for i in range(1,n):
    dp[i]=min([dp[j] + abs(step[i]-step[j]) for j in range(max(i-k,0),i)])
  return dp[n-1]
print(solve())
### BUGGY CODE ###

N = int(input())
lis = list(map(int,input().split()))
cnt = 0
for i in range(1,N+1):
        tmp_lis = lis[0:i]
        x = min(tmp_lis)
        if lis[i-1] == x:
                cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
lis = list(map(int,input().split()))
cnt = 1
small = lis[0]
for i in range(2,N+1):
        if lis[i-1] <= small:
                cnt += 1
                small = lis[i-1]
print(cnt)