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

from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

ans = 1000
for n in range(2**N):
    n = bin(n)[2:]
    if n.count('1')%2!=0:
        continue
    n = '0'*(N-len(n))+n
    l = []
    for i in range(N):
        if n[i]=='0':
            l.append([A[i],i])
        else:
            l.append([B[i],i+1])
    inversion = 0
    for i in range(N):
        if inversion>=ans:
            break
        for j in range(i+1,N):
            if l[i][0]>l[j][0]:
                inversion += 1
    if inversion>=ans:
        continue
    l.sort()
    d = defaultdict(list)
    for i in range(N):
        v,j = l[i]
        if (i-j)%2==1:
            d[v].append(i)
    possible = True
    for v in d:
        if len(d[v])%2==1:
            possible = False
        else:
            for i in range(len(d[v])//2):
                if (d[v][2*i+1]-d[v][2*i])%2==1:
                    inversion += d[v][2*i+1]-d[v][2*i]
                else:
                    possible = False
                    break
        if not possible:
            break
    if possible:
        ans = min(ans,inversion)

if ans == 1000:
    ans = -1
print(ans)

### FIXED CODE ###

from collections import defaultdict
from operator import itemgetter
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

ans = 1000
for n in range(2**N):
    n = bin(n)[2:]
    if n.count('1')%2!=0:
        continue
    n = '0'*(N-len(n))+n
    l = []
    for i in range(N):
        if n[i]=='0':
            l.append([A[i],i])
        else:
            l.append([B[i],i+1])
    inversion = 0
    for i in range(N):
        if inversion>=ans:
            break
        for j in range(i+1,N):
            if l[i][0]>l[j][0]:
                inversion += 1
    if inversion>=ans:
        continue
    l.sort(key=itemgetter(0))
    d = defaultdict(list)
    for i in range(N):
        v,j = l[i]
        if (i-j)%2==1:
            d[v].append(i)
    possible = True
    for v in d:
        if len(d[v])%2==1:
            possible = False
        else:
            for i in range(len(d[v])//2):
                if (d[v][2*i+1]-d[v][2*i])%2==1:
                    inversion += d[v][2*i+1]-d[v][2*i]
                else:
                    possible = False
                    break
        if not possible:
            break
    if possible:
        ans = min(ans,inversion)

if ans == 1000:
    ans = -1
print(ans)
### BUGGY CODE ###

N = int(input())
hList = list(map(int, input().split()))
count = 0

for i in range(N):
  for j in range(i,N):
    if (j-i) == (hList[i]+hList[j]):
      count += 1
print(count)

### FIXED CODE ###

import collections

N = int(input())
hList = list(map(int, input().split()))
count = 0
n_p = collections.Counter([ i + hList[i] for i in range(len(hList))])

for i in range(N):
  if i - hList[i] > 0:
    count += n_p.get(i - hList[i], 0)

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

from collections import Counter
from collections import defaultdict

def li():
    return [int(x) for x in input().split()]

H, W, M = li()
PH = []
PW = []

for i in range(M):
    h, w = li()
    PH.append(h)
    PW.append(w)

frequency_h_list = Counter(PH).most_common()
frequency_w_list = Counter(PW).most_common()
most_common_h_cnt = frequency_h_list[0][1]
most_common_w_cnt = frequency_w_list[0][1]

most_common_h_list = []
for x in frequency_h_list:
    if x[1] < most_common_h_cnt:
        break
    most_common_h_list.append(x[0])

most_common_w_list = []
for x in frequency_w_list:
    if x[1] < most_common_w_cnt:
        break
    most_common_w_list.append(x[0])

contain_intersection = {}
for h in most_common_h_list:
    for w in most_common_w_list:
        contain_intersection[h, w] = False

for i in range(M):
    h, w = PH[i], PW[i]
    if (h, w) in contain_intersection:
        contain_intersection[h, w] = True
cnt = most_common_h_cnt + most_common_w_cnt
if all([contain_intersection[key] for key in contain_intersection]):
    cnt -= 1

print(cnt)

### FIXED CODE ###

from collections import Counter
from collections import defaultdict

def li():
    return [int(x) for x in input().split()]

H, W, M = li()
PH = []
PW = []
PHF = defaultdict(int)
PWF = defaultdict(int)
PF = defaultdict(int)

for i in range(M):
    h, w = li()
    PH.append(h)
    PW.append(w)
    PHF[h] += 1
    PWF[w] += 1
    PF[h, w] += 1

sorted_PHF = sorted(PHF.items(), key=lambda x: x[1], reverse=True)
sorted_PWF = sorted(PWF.items(), key=lambda x: x[1], reverse=True)
most_common_h_cnt = sorted_PHF[0][1]
most_common_w_cnt = sorted_PWF[0][1]

most_common_h_list = []
for x in sorted_PHF:
    if x[1] < most_common_h_cnt:
        break
    most_common_h_list.append(x[0])

most_common_w_list = []
for x in sorted_PWF:
    if x[1] < most_common_w_cnt:
        break
    most_common_w_list.append(x[0])

add = -1
for h in most_common_h_list:
    for w in most_common_w_list:
        if PF[h, w] == 0:
            add = 0
            break

cnt = most_common_h_cnt + most_common_w_cnt + add

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

import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
A = sorted(list(map(int,readline().split())))
allA = sum(A)
sumA = [0] + A.copy()
for i in range(1,len(sumA)):
  sumA[i] += sumA[i - 1]

# 左手34,33,19,14,10
# 右手34,33,19,14,10
# X以上の握手をできる組だけ採用する
# 例：50以上の握手をできるのは、
# 左手34に対しては34,33,19
# 右手33に対しては34,33,19
# この合計がM回を越えると採用できない。
# M回を下回る場合は、すべての握手の合計で最大値を更新

ok = -1
ng = 200

import bisect
def isOk(x):
  # x以上の握手だけ採用するとき、採用できる場合に全体の合計点はいくつになるか
  cnt = 0
  for left in A:
    right = x - left
    ind = bisect.bisect_left(A, right)
    #print("N - ind",N - ind)
    cnt += N - ind
  #print("x",x,"cnt",cnt)
  if cnt >= M:
    return True
  else:
    return False

while abs(ng - ok) > 1:
  #print("ng",ng,"ok",ok)
  mid = abs(ng + ok) // 2
  if isOk(mid):
    ok = mid
  else:
    ng = mid
    
#print("ok",ok)

# ok以上の握手だけ許容する場合の点数を算出
ans = []
#print("A",A)
for left in A:
  right = ok - left
  ind = bisect.bisect_left(A, right)
  #print("ok",ok,"left",left,"right",right,"ind",ind)
  for r in range(ind, len(A)):
    #print("left",left,"A[r]",A[r])
    ans.append(A[r] + left)

ans = sorted(ans, reverse = True)
#print(ans)
print(sum(ans[:M]))


### FIXED CODE ###

n,m=map(int,input().split())
A=sorted(list(map(int,input().split())))

# M回の握手の幸福度最大化
# X以上になる握手を全て採用したときに、M通りを越える
# Xの最大値を求める

import bisect

ok=-1
ng=(10**10)+2

# x以上の握手をm通り以上作れるか
def isOk(x,m):
  cnt=0
  # 左手をループする
  for i in range(len(A)):
    left=A[i]
    minright=x-left
    # minright以上の数を数える
    cnt+=n-bisect.bisect_left(A,minright)
    if cnt>=m:
      return True
  return cnt>=m

while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOk(mid,m):
    ok=mid
  else:
    ng=mid

x=ok
# x以上となる幸福度を足し合わせる
# 足し合わせた握手がMを越える場合、xぴったりを足し過ぎている

# 効率化のため累積和を作成
Asum=[0]+A
for i in range(1,len(Asum)):
  Asum[i]=Asum[i-1]+Asum[i]
  
# Aの添字i以降を全て足すときは、
# Asum[-1]-Asum[i]

ans=0
cnt=0
for i in range(len(A)):
  left=A[i]
  minright=x-left
  start=bisect.bisect_left(A,minright)
  cnt+=n-start
  ans+=left*(n-start)+(Asum[-1]-Asum[start])
  
if cnt>m:
  ans-=(cnt-m)*x
  
print(ans)
### BUGGY CODE ###

import math
def func(x,y,z):
    ans = x**2 + y**2 + z**2+ x*y + y*z + z*x
    #print("x={},y={},z={},ans={}".format(x,y,z,ans))
    return ans

N = int(input())
root_n = round(math.sqrt(N+1))
for n in range(1,N+1):
    count = 0
    for x in range(1,root_n):
        for y in range(1,root_n):
            for z in range(1,root_n):
                if func(x,y,z)==n:
                    count=count+1
    print(count)
                
                

### FIXED CODE ###


import math
def func(x,y,z):
    ans = x**2 + y**2 + z**2+ x*y + y*z + z*x
    return ans

N = int(input())
array_N = [0]*N
root_n = round(math.sqrt(N+1))

for x in range(1,root_n):
    for y in range(1,root_n):
        for z in range(1,root_n):
            if func(x,y,z) <= N:
                array_N[func(x,y,z)-1] = array_N[func(x,y,z)-1] +1
                
for i in range(N):
    print(array_N[i])
### BUGGY CODE ###

import bisect

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
L = [list(map(int,input().split())) for i in range(M)]
L = sorted(L, key=lambda x: x[1], reverse=True)

ans = 0

for i in range(M) :
    b,c = L[i]
    
    bi = bisect.bisect(A,c)
    
    K = min(b,bi)
    ans += c*K
    A = A[K:]
ans += sum(A)
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
L = [list(map(int,input().split())) for i in range(M)]

P = sorted(([[1,A[i]] for i in range(N)] + L),key=lambda x: x[1],reverse=True)

ans = 0
rest = N

for cost,value in P :
    K = min(cost, rest)
    K = max(0,K)
    ans += K * value
    rest -= cost

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

N=int(input())
H=[int(s) for s in input().split()]

count_max=0
for j in range(N):
    count=0
    for i in range(j,N-1):
        if H[i] >= H[i+1]:
            count+=1
        else:
            break
    if count > count_max:
        count_max=count
        X=j

print(count_max)
            

### FIXED CODE ###

N=int(input())
H=[int(s) for s in input().split()]

count_max=0
count=0
for i in range(N-1):
    if H[i]-H[i+1] >= 0:
        count+=1
        if count > count_max:
            count_max=count
    else:
        count=0

print(count_max)
### BUGGY CODE ###

n = int(input())
count = 0
for l in range(1, n+1):
  for i in range(1, 41):
    for j in range(1, 41):
      for k in range(1, 41):
        if (i+j+k)**2-(i*j+j*k+i*k) == l:
          count +=1
  print(count)
  count = 0    

### FIXED CODE ###

n = int(input())
count = 0
a = [0]*(10**5)
for i in range(1, 100):
  for j in range(1, 100):
    for k in range(1, 100):
      a[(i+j+k)**2-(i*j+j*k+i*k)] += 1


for i in range(n):
  print(a[i+1])
### BUGGY CODE ###

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


import numpy as np
import bisect

N, M = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)
A.sort()
for _ in range(M):
    b, c = map(int, input().split())
    index = bisect.bisect_left(A, c)
    edge = max(0, index - b)
    A[:edge] = A[index-edge:index]
    A[edge:index] = c

print(sum(A))


### FIXED CODE ###

from collections import defaultdict

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

d = defaultdict(int)
for i in range(N):
    d[A[i]] += 1
for i in range(M):
    b, c = map(int, input().split())
    d[c] += b
    

key = sorted(list(d.keys()))

num = N
i = 0
S = 0
while num > 0:
    i -= 1
    n = d[key[i]]
    num -= n
    S += key[i] * n
    
S += key[i] * num

print(S)
### BUGGY CODE ###

import re
s = input()
x = s[0]
l = len(s)

i =0
while s != 'W' * (l ) and s != 'B' * (l):
    x = s[0]
    if x == 'B':
        k = s.find('W')
        s = s[k:]
        s = 'W' * (k+1) + s

    else:
        k = s.find('B')
        s = s[k:]
        s = 'B' * (k+1) + s

    i += 1
    l = len(s)
print(i)


### FIXED CODE ###

s = input()
l = len(s)
i =0
while s != 'W' * (l) and s != 'B' * (l):
    x = s[0]
    if x == 'B':
        k = s.find('W')
        s = s[k:]
    else:
        k = s.find('B')
        s = s[k:]
    i += 1
    l = len(s)
print(i)
### BUGGY CODE ###

from collections import Counter

n, x, y = map(int, input().split())
ans = []
for i in range(1, n+1):
    for j in range(1, n+1):
        ans.append(min(abs(j - i),
                       abs(x - i)+1+abs(j - y),
                       abs(y - i)+1+abs(j - x)))
ans_cnt = Counter(ans)
for i in range(1, n):
    print(ans_cnt[i] // 2)


### FIXED CODE ###

from collections import Counter

n, x, y = map(int, input().split())
ans = []
for i in range(1, n+1):
    for j in range(1, n+1):
        ans.append(min(abs(j - i),
                       abs(x - i)+1+abs(j - y),
                       abs(y - i)+1+abs(j - x)))
ans_cnt = Counter(ans)
for i in range(1, n):
    print(ans_cnt[i] // 2)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(250000)
from collections import defaultdict

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

nl = [[] for _ in range(N + 1)]
for a, b in [tuple(map(int, input().split())) for _ in range(N - 1)]:
    nl[a].append(b)
    nl[b].append(a)

val = defaultdict(int)
for p, x in [tuple(map(int, input().split())) for _ in range(Q)]:
    val[p] += x

seen = set()
ans = [0 for _ in range(N + 1)]


def dfs(v, cnt):
    seen.add(v)
    cnt += val[v]
    ans[v] = cnt
    for next_v in nl[v]:
        if next_v not in seen:
            dfs(next_v, cnt)


dfs(1, 0)
c = [0 for _ in range(N + 1)]
print(' '.join([str(a) for a in ans[1:]]))


### FIXED CODE ###

from collections import defaultdict

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

nl = [[] for _ in range(N + 1)]
for a, b in [tuple(map(int, input().split())) for _ in range(N - 1)]:
    nl[a].append(b)
    nl[b].append(a)
nl[0].append(1)

val = defaultdict(int)
for p, x in [tuple(map(int, input().split())) for _ in range(Q)]:
    val[p] += x

ans = [0 for _ in range(N + 1)]

stack = list()
stack.append((0, -1, 0))
while len(stack) > 0:
    v, p, cnt = stack.pop()
    cnt += val[v]
    ans[v] = cnt
    for next_v in nl[v]:
        if next_v != p:
            stack.append((next_v, v, cnt))

print(' '.join([str(a) for a in ans[1:]]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
a_tuple = tuple(map(int, input().split()))
a_set = set(a_tuple)
count_list = []

if k >= len(a_set):
    print(0)
else:
    for i in a_set:
        count = a_tuple.count(i)
        count_list.append(count)
    count_list.sort()
    ans = sum(count_list[:len(a_set)-k])
    print(ans)


### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline

n, k = map(int, input().split())
a_tuple = tuple(map(int, input().split()))
count_dict = defaultdict(int)

for i in a_tuple:
    count_dict[i] += 1

n = len(count_dict.keys())

if n <= k:
    print(0)
else:
    ans = sum(tuple(sorted(count_dict.values()))[:n-k])
    print(ans)
### BUGGY CODE ###

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

maxIndex = [i for i, x in enumerate(a) if x == max(a)]
if len(maxIndex)>=2:
    for i in range(n):
        print(max(a))
else:
    z = int(maxIndex[0])
    s = max(a[0:z],a[z+1:n+1])
    for k in range(n):
        if k==z:
            print(s[0])
        else:
            print(max(a))


### FIXED CODE ###

import sys
n= int(input())
a =[int(input()) for i in range (n)]
b=max(a)
c=sorted(a)[-2]
for i in (a):
    if i == b:
        print(c)
    else:
        print(b)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())  # 迷路の縦、横の長さ
maze = []
for _ in range(H):
    maze.append(input())
# print(maze)
dist = [[-1] * W for iii in range(H)]  # スタートからの距離
check_que = deque()

d = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            dist[i][j] = 0
            check_que.append((i, j))
# print(dist)


def bfs(initial_d):  # distを編集する関数
    #print("{},{}".format(tate, yoko))
    while check_que:

        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 <= h_prime <= H - 1 and 0 <= w_prime <= W - 1:
                if dist[h_prime][w_prime] == -1:
                    dist[h_prime][w_prime] = d + 1
                    check_que.append((h_prime, w_prime))

    return d


dis = bfs(0)
# print(dist)
print(dis)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())  # 迷路の縦、横の長さ
maze = []
for _ in range(H):
    maze.append(input())
# print(maze)
dist = [[-1] * W for iii in range(H)]  # スタートからの距離
check_que = deque()

d = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            dist[i][j] = 0
            check_que.append((i, j))
# print(dist)


def bfs(initial_d):  # distを編集する関数
    dis = 0
    #print("{},{}".format(tate, yoko))
    while len(check_que) != 0:

        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 <= h_prime <= H - 1 and 0 <= w_prime <= W - 1:
                if dist[h_prime][w_prime] == -1:
                    dist[h_prime][w_prime] = d + 1
                    check_que.append((h_prime, w_prime))
                    if d + 1 > dis:
                        dis = d+1
    return dis


dis = bfs(0)
# print(dist)
print(dis)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC66 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def f(a, b):
    if b == 0: 
        return 1
    elif b % 2 == 0:
        d = f(a, b // 2)
        return d * d % mod
    else:
        return (a * f(a, b - 1)) % mod


def comb(n,r):
    if n - r < 0:
        return 0
    return fact[n] * invfact[r] * invfact[n-r] % mod

n = I()
a = LI()
c = list(Counter(a).items())
c.sort(key = itemgetter(1),reverse = True)
x = c[0][0]

fact = [1]*(n+2)
invfact = [1]*(n+2)
for i in range(1,n+2):
    fact[i] = i*fact[i-1]
    invfact[i] = invfact[i-1] * f(i,mod-2) % mod

lst = []
for i in range(n+1):
    if a[i] == x:
        lst.append(i+1)
a,b = lst[0],lst[1]
for i in range(n+1):
    res = 0
    res = (res + comb(n+1,i+1)) % mod
    res = (res - comb((a-1)+(n+1-b),i)) % mod
    print(res)
    

### FIXED CODE ###

#!/usr/bin/env python3
#ABC66 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def f(a, b):
    if b == 0: 
        return 1
    if b % 2 == 0:
        d = f(a, b // 2)
        return d * d % mod
    if b % 2 == 1:
        return (a * f(a, b - 1)) % mod


def comb(n,r):
    if n - r < 0:
        return 0
    return fact[n] * invfact[r] * invfact[n-r] % mod

n = I()
a = LI()
cnt = [0]*(n+1)
for i in range(n+1):
    if cnt[a[i]]:
        a = cnt[a[i]]
        b = i+1
        break
    else:
        cnt[a[i]] = i+1

fact = [1]*(n+2)
invfact = [1]*(n+2)
for i in range(1,n+2):
    fact[i] = i*fact[i-1] % mod
    invfact[i] = invfact[i-1] * f(i,mod-2) % mod

for i in range(n+1):
    res = 0
    res = (res + comb(n+1,i+1)) % mod
    res = (res - comb((a-1)+(n+1-b),i)) % mod
    print(res)
### BUGGY CODE ###

n,m,q=map(int,input().split())
abcd=[]
for i in range(q):
  abcd.append(list(map(int,input().split())))
ans=0
for i in range(1<<q):
  A=[1]*n
  sumd=0
  hantei=True
  for j in range(q):
    if ((i>>j)&1):
      a,b,c,d=abcd[j][0],abcd[j][1],abcd[j][2],abcd[j][3]
      if A[a-1]!=1 and A[b-1]!=1:
        if A[b-1]-A[a-1]!=c:
          hantei=False
          break
      elif A[a-1]==1 and A[b-1]!=1:
        A[a-1]=A[b-1]-c
        if A[a-1]<1:
          hantei=False
          break
      else:
        A[b-1]=A[a-1]+c
        if A[b-1]>m:
          hantei=False
          break
      sumd+=d
  if hantei:
    for j in range(q):
      if ((i>>j)&1):
        a,b,c,d=abcd[j][0],abcd[j][1],abcd[j][2],abcd[j][3]
        if A[b-1]-A[a-1]!=c:
          hantei=False
          break
  if hantei:
    for j in range(n-1):
      if A[j]>A[j+1]:
        hantei=False
        break
  if hantei and sumd>ans:
    ans=sumd
print(ans)

     
      

### FIXED CODE ###

n,m,q=map(int,input().split())
abcd=[list(map(int,input().split())) for i in range(q)]
ans=0

def calc(arr):
  score=0
  for a,b,c,d in abcd:
    if arr[b-1]-arr[a-1]==c:
      score+=d
  return score

def dfs(arr, i):
  global ans
  if len(arr)==n:
    ans=max(ans,calc(arr))
    return
  for j in range(i,m+1):
    arr.append(j)
    dfs(arr, j)
    arr.pop()
dfs([], 1)
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(input().split())
b = []
for i in a:
    b.append(i)
    b = b[::-1]
print(" ".join(b))

### FIXED CODE ###

n = int(input())
a = list(input().split())
b = []
if n%2==1:
    b = a[::-2]+a[1::2]
else:
    b = a[::-2]+a[::2]
print(" ".join(b))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(250000)
input = sys.stdin.readline
import queue


def main():
    n, k = map(int, input().split())
    h = list(map(int,input().split()))

    cost = [sys.maxsize]*n
    cost[0] = 0
    for i in range(0,n):
        for j in range(1, k + 1):
            if (i+ j>= n):
                break
            abs_ = abs(h[i] - h[i+j])
            if cost[i+j] >cost[i] + abs_ :
                cost[i+j] = cost[i] + abs_
    print(cost[n-1])
main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(250000)
input = sys.stdin.readline
import queue


def main():
    n, k = map(int, input().split())
    h = list(map(int,input().split()))

    cost = [sys.maxsize]*n
    cost[0] = 0
    for i in range(0,n):
        for j in range(1, k + 1):
            if (i+ j>= n):
                break
            abs_ = abs(h[i] - h[i+j])
            if cost[i+j] >cost[i] + abs_ :
                cost[i+j] = cost[i] + abs_
    print(cost[n-1])
main()
### BUGGY CODE ###

import bisect

n = int(input())
a = [int(input()) for _ in range(n)]
# それぞれの色の最大値を入れる筒のリスト
t = []

for i in a:
    # それぞれの色のどの値よりも小さかったとき
    idx = bisect.bisect_left(t, i)
    # print(i, idx)
    if idx == 0:
        t.insert(0, i)
    # 効率的な色の探索
    else:
        t[idx-1] = i
    # print(t)

print(len(t))

### FIXED CODE ###

import bisect

n = int(input())
a = [int(input()) for _ in range(n)]
# それぞれの色の最大値を入れる筒のリスト
t = [a[-1]]

for i in reversed(a[:-1]):
    # それぞれの色のどの値よりも小さかったとき
    idx = bisect.bisect_left(t, i+1)
    # print(i, idx)
    if idx == len(t):
        t.append(i)
    # 効率的な色の探索
    else:
        t[idx] = i
    # print(t)

print(len(t))
### BUGGY CODE ###

import math

N,K=map(int,input().split())
S=input()
L=[]
seq=0
prev='2'
for i in S:
  if i == prev:
    seq += 1
  else:
    L.append(seq)
    prev = i
    seq = 1
L.append(seq)
L.append(0)

L_cum = [0]*(len(L)+1)
for i in range(len(L)):
  L_cum[i]=sum(L[0:i+1])

if S[0] == '0':
  num_0 = math.ceil((len(L)-2)/2)
  if num_0<=K:
    ans=N
  else:
    rev=[]
    for i in range(num_0-K+1):
      rev.append(L_cum[2*(K+i)]-L_cum[i*2-1])
    ans=max(rev)
else:
  num_0 = math.floor((len(L)-2)/2)
  if num_0<=K:
    ans=N
  else:
    rev=[]
    for i in range(num_0-K+1):
      rev.append(L_cum[2*(K+i)+1]-L_cum[2*i])
    ans=max(rev)
print(ans)

### FIXED CODE ###

import math

N,K=map(int,input().split())
S=input()
L=[]
seq=0
prev='2'
for i in S:
  if i == prev:
    seq += 1
  else:
    L.append(seq)
    prev = i
    seq = 1
L.append(seq)
L.append(0)

L_cum = [0]*(len(L)+1)
for i in range(len(L)):
  L_cum[i]=L_cum[i-1]+L[i]

if S[0] == '0':
  num_0 = math.ceil((len(L)-2)/2)
  if num_0<=K:
    ans=N
  else:
    rev=[0]*(num_0-K+1)
    for i in range(num_0-K+1):
      rev[i]=L_cum[2*(K+i)]-L_cum[i*2-1]
    ans=max(rev)
else:
  num_0 = math.floor((len(L)-2)/2)
  if num_0<=K:
    ans=N
  else:
    rev=[0]*(num_0-K+1)
    for i in range(num_0-K+1):
      rev[i]=L_cum[2*(K+i)+1]-L_cum[2*i]
    ans=max(rev)
print(ans)