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

N = int(input())
S = input()
min_num = 10**6

for i in range(0, N):
    num = 0
    num = sum(x == 'W' for x in S[:i]) + sum(x == 'E' for x in S[i+1:])    
    if num < min_num:
        min_num = num
        
print(min_num)

### FIXED CODE ###

N = int(input())
S = input()
min_num = 10**7
west_num = [0]
east_num = [0]
w_max = 0
e_max = 0
for i in range(0, N): #累積和を求める.
    if S[i] == 'W':
        w_max += 1
    else:
        e_max += 1
        
    west_num.append(w_max)
    east_num.append(e_max)

for i in range(0, N):
    num = west_num[i] + east_num[-1] - east_num[i+1]
    if num < min_num:
        min_num = num
        
print(min_num)
### BUGGY CODE ###

# import math
# import decimal
# import queue
# import bisect
# import heapq
# import time
# import itertools

mod = int(1e9+7)

def main():
    n,k = map(int,input().split())
    p = list(map(int,input().split()))
    x = [0]
    _sum = 0
    for i in range(1,max(p)+1):
        _sum += i
        x.append(_sum)
    v = []
    for i in range(n):
        v.append(x[p[i]]/p[i])
    ans = 0
    for i in range(n-k+1):
        ans = max(ans,sum(v[i:i+k]))
    print(ans)
    return

if __name__=='__main__':
    main()


### FIXED CODE ###

# import math
# import decimal
# import queue
# import bisect
# import heapq
# import time
# import itertools

mod = int(1e9+7)

def main():
    n,k = map(int,input().split())
    p = list(map(int,input().split()))
    x = [0]
    _sum = 0
    for i in range(1,max(p)+1):
        _sum += i
        x.append(_sum)
    v = []
    ans = 0
    res = 0
    for i in range(n):
        v.append(x[p[i]]/p[i])
        if i >= k:
            res += v[i] - v[i-k]
        else:
            res += v[i]
        ans = max(ans,res)
    print(ans)
    return

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

import collections

n = int(input())

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

q = int(input())

num_dict = dict(collections.Counter(a))
num_dict = {key : key * value for key, value in num_dict.items()}

for _ in range(q):
    b, c = map(int,input().split())

    num_dict[c] = int((c * num_dict.get(b, default=0) / b) + num_dict.get(c, default=0))

    if num_dict.get(b, default=0) != 0:
        del(num_dict[b])

    print(sum(num_dict.values()))

### FIXED CODE ###

import collections

n = int(input())

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

q = int(input())

num_dict = dict(collections.Counter(a))

temp = [key * value for key, value in num_dict.items()]

ans = sum(temp)

for _ in range(q):
    b, c = map(int,input().split())

    if num_dict.get(b):
        num_dict[c] = num_dict[b] + num_dict.get(c, default=0)

        ans = ans - num_dict[b] * b + num_dict[b] * c

        del(num_dict[b])

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

import time

N=int(input())

sieve= [0]*(N+1)
sieve[0]=-1
sieve[1]=-1
for i in range(2,N+1):
    if sieve[i] != 0:
        continue
    sieve[i] = i
    for j in range(i*i, N+1, i):
        if sieve[j] ==0:
            sieve[j] = i

def G(x):
    t=[]
    a = x
    while a!=1:
        if len(t) != 0 and t[-1][0] == sieve[a]:
            t[-1][1] += 1
        else:
            t.append([sieve[a],1])
        a //= sieve[a]
    result = 1
    for _,n  in t:
        result *= n+1
    return result

sum = 0
for i in range(1, N+1):
    sum += i*G(i)
print(sum)



### FIXED CODE ###

N=int(input())

sieve= [0]*(N+1)
sieve[0]=-1
sieve[1]=-1
for i in range(2,N+1):
    if sieve[i] != 0:
        continue
    sieve[i] = i
    for j in range(i*i, N+1, i):
        if sieve[j] ==0:
            sieve[j] = i
            
def G(x):
    t=[]
    a = x
    while a!=1:
        if len(t) != 0 and t[-1][0] == sieve[a]:
            t[-1][1] += 1
        else:
            t.append([sieve[a],1])
        a //= sieve[a]
    result = 1
    for _,n  in t:
        result *= n+1
    return result

sum = 0
for i in range(1, N+1):
    sum += i*G(i)
print(sum)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

MAX = 2000000
MOD = 1000000007

X, Y = map(int, input().split())
count_x = 2*X - Y
count_y = 2*Y - X
if count_x % 3 != 0 or count_y % 3 != 0:
    print(0)
    exit()
count_x = count_x // 3
count_y = count_y // 3

fac = [0]*MAX
inv = [0]*MAX
finv = [0]*MAX

fac[0], fac[1] = 1, 1
finv[0], finv[1] = 1, 1
inv[1] = 1
for i in range(2, MAX):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def COM(n, k):
    global fac
    global finv
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD

print(COM(count_x + count_y, min(count_x, count_y)))


### FIXED CODE ###

import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

def main():

    def fur(n,r):
        p,q = 1,1
        for i in range(r):
            p = p*(n-i)%mod
            q = q*(i+1)%mod
        return p * pow(q,mod-2,mod) % mod

    x, y = nm()

    if (x + y) % 3 != 0:
        print(0)
        exit()
    
    n = (2*y - x) // 3 # (X, Y) -> (X+1, Y+2) 
    m = (2*x - y) // 3 # (X, Y) -> (X+2, Y+1) 

    if n < 0 or m < 0:
        print(0)
        exit()

    print(fur(n+m, n))

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

R, G, B, N = map(int,input().split())
count = 0
x = int(N / R)
y = int(N / G)
z = int(N / B)
rg_list = []
for r in range(x + 1):
    for g in range(y + 1):
        buf = r * R + g * G
        if buf == N :
            count += 1
        if buf < N :
            rg_list.append(buf)
rg_list.sort()
# sprint(rg_list)

rg_count_list = []
for i in range(N):
    rg_count_list.append(rg_list.count(i))

for b in range(z + 1):
    for rg in range(len(rg_count_list)):
        if rg + b*B == N :
            count += rg_count_list[rg]
        if rg + b*B > N :
            break
print(count)


### FIXED CODE ###

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

#!/usr/bin/env python3
import sys

def solve(N: int, M: int, A: "List[int]"):
    
    A = sorted(A,reverse=True)
    while True:
        A[0] = A[0] // 2
        M -= 1
        if M == 0:
            break
        if N == 1:
            continue

        for i in range(N-1):
            if A[i] < A[i+1]:
                tmp = A[i+1]
                A[i+1] = A[i]
                A[i] = tmp
            else:
                break
    print(sum(A))

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import heapq

def solve(N: int, M: int, A: "List[int]"):

    while True:
        tmp = heapq.heappop(A) * -1
        heapq.heappush(A,tmp // 2 * -1)
        M -= 1
        if M == 0:
            break
    
    print(sum(A) * -1)

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = []
    heapq.heapify(A)
    for i in range(N):
        heapq.heappush(A,int(next(tokens)) * -1)

    solve(N, M, A)

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

N,K=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(N)]
x=[]
y=[]
for i,j in z:
    x.append(i)
    y.append(j)
x.sort()
y.sort()
a=10**20
for i in range(N):
    for j in range(i+1,N):
        for k in range(N):
            for l in range(k+1,N):
                l,r,d,u=x[i],x[j],y[k],y[l]
                if sum(l<=v<=r and d<=w<=u for v,w in z)>=K:
                    a=min(a,(r-l)*(u-d))
print(a)

### FIXED CODE ###

n,k=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(n)]
z.sort()
a=10**20
for i in range(n):
    for j in range(i+1,n):
        x=z[j][0]-z[i][0]
        l=sorted(t[1]for t in z[i:j+1])
        for u,v in zip(l,l[k-1:]):
            a=min(a,x*(v-u))
print(a)
### BUGGY CODE ###

def makelist(n, m, p):
	return [[[0 for k in range(p)] for i in range(m)] for j in range(n)]

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

dp = makelist(N+1, N+1, N*A+1)
dp[0][0][0] = 1
for i in range(N):
	for j in range(i+1):
		for k in range(N*A):
			if k + x[i] <= N * A:
				dp[i+1][j+1][k+x[i]] += dp[i][j][k]
			dp[i+1][j][k] += dp[i][j][k]

ans = 0
for i in range(1, N+1):
	ans += dp[N][i][i*A]

print(ans)


### FIXED CODE ###

def makelist(n, m, p):
	return [[[0 for k in range(p)] for i in range(m)] for j in range(n)]

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

dp = makelist(N+1, N+1, N*A+1)
dp[0][0][0] = 1
for i in range(N):
	for j in range(i+1):
		for k in range(N*A):
			if k + x[i] <= N * A:
				dp[i+1][j+1][k+x[i]] += dp[i][j][k]
			dp[i+1][j][k] += dp[i][j][k]

ans = 0
for i in range(1, N+1):
	ans += dp[N][i][i*A]

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

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import deque
import sys
def main(H, W, C, D, S):
    INF = 10**6
    dist = [[INF] * W for _ in range(H)]
    di, dj = D
    dist[di][dj] = 0
    q = deque([(di, dj, 0)])
    while q:
        i, j, d = q.popleft()
        if d > dist[i][j]: continue
        for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                if dist[ni][nj] > d:
                    dist[ni][nj] = d
                    q.append((ni, nj, d))
        for ni in range(i - 2, i + 2 + 1, 1):
            if not(0 <= ni < H): continue
            dni = dist[ni]
            sni = S[ni]
            for nj in range(j - 2, j + 2 + 1, 1):
                if 0 <= nj < W and sni[nj] == '.':
                    if dni[nj] > d + 1:
                        dni[nj] = d + 1
                        q.append((ni, nj, d + 1))

    ans = dist[C[0]][C[1]]
    print(ans if ans < INF else -1)


if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = tuple(map(lambda x: int(x) - 1, input().split()))
    D = tuple(map(lambda x: int(x) - 1, input().split()))
    S = [list(input().rstrip()) for _ in range(H)]
    main(H, W, C, D, S)


### FIXED CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import deque
import sys
def main(H, W, C, D, S):
    INF = 10**6
    dist = [[INF] * W for _ in range(H)]
    di, dj = D
    dist[di][dj] = 0
    q = deque([(di, dj, 0)])
    while q:
        i, j, d = q.popleft()
        if d > dist[i][j]: continue
        for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                if dist[ni][nj] > d:
                    dist[ni][nj] = d
                    q.appendleft((ni, nj, d))
        for ni in range(i - 2, i + 2 + 1, 1):
            if not(0 <= ni < H): continue
            dni = dist[ni]
            sni = S[ni]
            for nj in range(j - 2, j + 2 + 1, 1):
                if 0 <= nj < W and sni[nj] == '.':
                    if dni[nj] > d + 1:
                        dni[nj] = d + 1
                        q.append((ni, nj, d + 1))

    ans = dist[C[0]][C[1]]
    print(ans if ans < INF else -1)


if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = tuple(map(lambda x: int(x) - 1, input().split()))
    D = tuple(map(lambda x: int(x) - 1, input().split()))
    S = [list(input().rstrip()) for _ in range(H)]
    main(H, W, C, D, S)
### BUGGY CODE ###



from collections import defaultdict


N = int(input())
"""
before[(i,j)]
iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

nxt[(i,j)]
iとjの試合より後に行える対戦者の組

例２
4
2 3 4
1 3 4
4 1 2
3 1 2
について、
before[(1,3)] = 2
before[(1,4)] = 2
nxt[(1,2)] = set((1,3), (2,3))
みたいな
"""
before = defaultdict(int)
nxt = defaultdict(set)

for i in range(N):
    A = list(map(int, input().split()))

    for j,a in enumerate(A):
        l, h = min(i+1, a), max(i+1, a)
        if j == 0:
            b = (l,h)
        else:
            before[(l,h)] += 1
            nxt[b].add((l,h))
            b = (l,h)



match_today = []

for i in range(1, N):
    for j in range(i+1, N+1):
        if before[(i, j)] == 0:
            match_today.append((i,j))
            

match_tomorrow = []
ans = 0
cnt_match = 0 
while len(match_today) > 0:
    #print( match_today)
    ans += 1
    cnt_today = 0
    
    for l,h in match_today:
        cnt_match += 1
        for nl, nh in nxt[(l,h)]:
            before[(nl, nh)] -= 1
            
            if before[(nl, nh)] == 0:
                match_tomorrow.append((nl, nh))
    
    match_today = match_tomorrow
    match_tomorrow = []


if cnt_match == N*(N-1) // 2:
    print(ans)
else:
    print(-1)

### FIXED CODE ###


from collections import deque

N = int(input())
match_order = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]


q = deque(range(N))
finish_by = [0] * N
next_opponent = [None] * N

while q:
    a = q.popleft()
    # aの残りの順で一番初めに戦う対戦相手を取り出す
    b = match_order[a].popleft()
    if next_opponent[b] == a:
        finish_by[a] = finish_by[b] = max(finish_by[a], finish_by[b]) + 1
        # a,bについて、まだ対戦相手が残っているならキューに積む
        if match_order[a]:
            q.append(a)
        if match_order[b]:
            q.append(b)
    # bの残りの順で戦う相手がaではないなら、順番が来るまで待つ
    else:
        next_opponent[a] = b

# 対戦相手が残っている人がいる場合、条件通りに終わることができない
if any(match_order):
    print(-1)
else:
    print(max(finish_by))
### BUGGY CODE ###

from math import log,floor
N = int(input())
A = list(map(int, input().split()))

# log(10**9 + 10**9)/log(2) = 30.89 < 31
#print(log(2 * 10**9) / log(2))

A.sort(reverse=True)
usedI = [0] * N
cnt = 0

for i in range(N):
  if usedI[i] == 1:
    continue
  #print(i, log(A[i]) / log(2) )
  x = floor(log(A[i]) / log(2)) + 1 #実現可能なべき上
  search_x = 2 ** x - A[i]
  for j in range(N-1,i,-1):
    if search_x == A[j]:
      if usedI[j] == 1:
        continue
      else:
        cnt += 1
        usedI[i] = 1
        usedI[j] = 1
        break
    elif search_x < A[j]:
      break

print(cnt)
    

### FIXED CODE ###

from math import log,floor
from collections import Counter
N = int(input())
A = list(map(int, input().split()))

A.sort(reverse=True)
C = Counter(A)

cnt = 0
last_a = -1
for i in range(N):
  a = A[i]
  if last_a == a:
    continue
  last_a = a
  count_a = C[a]
  if count_a <= 0:
    continue
  b = pow(2,floor(log(a)/log(2))+1) - a
  count_b = C[b]
  if count_b <= 0:
    continue
  i += count_a - 1
  x = min(count_a, count_b) if a != b else count_a // 2
  cnt += x
  C[a] -= x
  C[b] -= x
  
print(cnt)
### BUGGY CODE ###

import sys
#import bisect
input = sys.stdin.buffer.readline
#lb = bisect.bisect_left

def main():
	H,N=map(int,input().split())
	#vA=list(map(int, input().split()))
	INF = 1001001001
	#H=int(input())
	mAB=[tuple(map(int,input().split())) for _ in [0,]*N]
	
	vN = [INF,]*(H+2)
	vN[0] = 0
	#mD = []
	#apD = mD.append
	#apD(vI)
	
	for h in range(H+2):
		#vN = mD[-1][:]
		for a,b in mAB:
			j = min(h+a,H+1)
			vN[j] = min(vN[h]+b, vN[j])
		#apD(vN)
		
	#res = min(mD[-1][-1],mD[-1][-2])
	res = min(vN[-2:])
	print(res)

main()


### FIXED CODE ###

import sys
#import bisect
input = sys.stdin.buffer.readline
#lb = bisect.bisect_left

def main():
	H,N=map(int,input().split())
	#vA=list(map(int, input().split()))
	INF = 1001001001
	#H=int(input())
	mAB=[tuple(map(int,input().split())) for _ in [0,]*N]
	
	vN = [INF,]*(H+2)
	vN[0] = 0
	#mD = []
	#apD = mD.append
	#apD(vI)
	
	for h in range(H+2):
		#vN = mD[-1][:]
		for a,b in mAB:
			j = min(h+a,H+1)
			vN[j] = min(vN[h]+b, vN[j])
		#apD(vN)
		
	#res = min(mD[-1][-1],mD[-1][-2])
	res = min(vN[-2:])
	print(res)

main()
### BUGGY CODE ###

n,W=map(int,input().split())
wei=[]
val=[]
for _ in range(n):
    x,y=map(int,input().split())
    wei.append(x)
    val.append(y)
dp=[[0 for p in range(W+1)] for q in range(n+1)]
for i in range(n):
    for w in range(W+1):
        if wei[i]<=w:
            dp[i+1][w]=max(dp[i][w-wei[i]]+val[i],dp[i][w])
        else:
            dp[i+1][w]=dp[i][w]
print(dp[n][W])


### FIXED CODE ###

n,W=map(int,input().split())
wei=[]
val=[]
for _ in range(n):
    x,y=map(int,input().split())
    wei.append(x)
    val.append(y)
dp=[[0 for p in range(W+1)] for q in range(n+1)]
for i in range(n):
    for w in range(W+1):
        if wei[i]<=w:
            dp[i+1][w]=max(dp[i][w-wei[i]]+val[i],dp[i][w])
        else:
            dp[i+1][w]=dp[i][w]
print(dp[n][W])
### BUGGY CODE ###

import heapq
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M, S = list(map(int, sys.stdin.buffer.readline().split()))
UVAB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
CD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
CD = [(0, 0)] + CD

graph = [[] for _ in range(N + 1)]
for u, v, a, b in UVAB:
    graph[u].append((a, b, v))
    graph[v].append((a, b, u))
for vs in graph:
    vs.sort()

mada = set(list(range(2, N + 1)))
heap = [(0, 1, S)]
ans = [INF] * (N + 1)
ans[1] = 0
# dp[v, s]: v にお金を s 持ってる状態で来たときの最小値
dp = defaultdict(lambda: INF)
dp[1, S] = 0
while heap and mada:
    d, v, s = heapq.heappop(heap)
    if d > dp[v, s]:
        continue
    if v in mada:
        mada.remove(v)

    ans[v] = min(ans[v], d)
    for a, b, u in graph[v]:
        if s - a < 0:
            break
        if d + b < dp[u, s - a]:
            dp[u, s - a] = d + b
            heapq.heappush(heap, (d + b, u, s - a))
    c, dd = CD[v]
    for _ in range(3):
        if d + dd < dp[v, s + c]:
            dp[v, s + c] = d + dd
            heapq.heappush(heap, (d + dd, v, s + c))

print(*ans[2:], sep='\n')


### FIXED CODE ###

import heapq
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M, S = list(map(int, sys.stdin.buffer.readline().split()))
UVAB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
CD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
CD = [(0, 0)] + CD

graph = [[] for _ in range(N + 1)]
for u, v, a, b in UVAB:
    graph[u].append((a, b, v))
    graph[v].append((a, b, u))
for vs in graph:
    vs.sort()

mada = set(list(range(2, N + 1)))
heap = [(0, 1, S)]
ans = [INF] * (N + 1)
ans[1] = 0
# dp[v, s]: v にお金を s 持ってる状態で来たときの最小値
dp = defaultdict(lambda: INF)
dp[1, S] = 0
while heap and mada:
    d, v, s = heapq.heappop(heap)
    if d > dp[v, s]:
        continue
    if v in mada:
        mada.remove(v)

    ans[v] = min(ans[v], d)
    for a, b, u in graph[v]:
        if s - a < 0:
            break
        if d + b < dp[u, s - a]:
            dp[u, s - a] = d + b
            heapq.heappush(heap, (d + b, u, s - a))
    c, dd = CD[v]
    sc = min(s + c, 50 * N + 10)
    if d + dd < dp[v, sc]:
        dp[v, sc] = d + dd
        heapq.heappush(heap, (d + dd, v, sc))

print(*ans[2:], sep='\n')
### BUGGY CODE ###

import sys
I = lambda:map(int,sys.stdin.readline().split())
pr = lambda x:sys.stdout.write(f'{x}\n')
sys.setrecursionlimit(2000000001)

def solve(n,ar,k,dp,x):
	ab = abs; s = solve; mn = min
	if x>=n-2: return dp[x]
	if dp[x] + 1: return dp[x]
	m = 1e9
	for i in range(x+1,mn(n,x+k+1)):
		t = ab(ar[x]-ar[i])+s(n,ar,k,dp,i)
		m = mn(m,t)
	dp[x] = m	#n([*map(lambda i:ab(ar[x]-ar[i])+solve(n,ar,k,dp,i), range(x+1,)])
	return dp[x]

def main():
	(n,k), ar = [[*map(int,s.split())] for s in [*open(0)]]
	dp = [-1]*(n-2)
	dp.append(abs(ar[-2]-ar[-1]))
	dp.append(0)
	pr(solve(n,ar,k,dp,0))

main()

### FIXED CODE ###

import sys
from functools import reduce
sys.setrecursionlimit(2000000001)

def solve(n,k,ar,dp,x):
	ab = abs; mn = min
	if x>=n-2: return dp[x]
	if not dp[x] is -1: return dp[x]
	# t = [ for i in range(x+1,mn(n,x+k+1))]
	t = map(lambda i:ab(ar[x]-ar[i])+solve(n,k,ar,dp,i), range(x+1,mn(n,x+k+1)))
	dp[x] = reduce(lambda a,b : a if a < b else b,t)
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	pr(solve(n,k,ar,dp,0))

main()
### BUGGY CODE ###

N = int(input())

# 因数分解
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

a = prime_factorize(N)
if len(a) == 1:
    print(N-1)
else:
    minAns = float('inf')
    for i in range(1 << len(a)):
        x = 1
        y = 1
        for j in range(len(a)):
            if (i >> j) & 1 == 1:
                x *= a[j]
            else:
                y *= a[j]
        if x-1 + y-1 < minAns:
            minAns = x-1 + y-1
    print(minAns)



### FIXED CODE ###

import math
N = int(input())
ans = float('inf')
for i in range(1,math.ceil(math.sqrt(N)+1)):
    if N % i == 0:
        j = N//i
        if ans > i+j-2:
            ans = i+j-2
print(ans)
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())

field=[]
m=[]
INF=10**6

for i in range(h):
    row=list(input())
    field.append(row)
    m.append([INF for i in range(w)])

dx=[1,0,-1,0]
dy=[0,1,0,-1]

queue=deque()
for i in range(h):
    for j in range(w):
        if field[i][j]=="#":
            m[i][j]=0
            queue.append([i,j])

while len(queue)>0:
    y,x=queue.popleft()
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=ny<h and 0<=nx<w:
            if m[ny][nx]>m[y][x]+1 and field[ny][nx]==".":
                m[ny][nx]=m[y][x]+1
                queue.append([ny,nx])
                field[ny][nx]="#"

ans=0

for i in range(h):
    ans=max(ans,max(m[i]))

print(ans)

### FIXED CODE ###

h,w=map(int,input().split())
INF=10**10
a=[[INF for i in range(w)] for j in range(h)]
ans=0
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]=="#":
            a[i][j]=0
            
for i in range(h):
    for j in range(w):
        k=a[i][j]+1

        if i!=h-1:
            if k<a[i+1][j]:
                a[i+1][j]=k
        if j!=w-1:
            if k<a[i][j+1]:
                a[i][j+1]=k

for i in range(h):
    for j in range(w):
        k=a[-1-i][-1-j]+1
        if i!=h-1:
            if k<a[-i-2][-j-1]:
                a[-i-2][-j-1]=k

        if j!=w-1:        
            if k<a[-i-1][-j-2]:
                a[-i-1][-j-2]=k

for i in range(h):
    ans=max(ans,max(a[i]))
print(ans)
### BUGGY CODE ###

data = input().split(" ")
data = list(map(int, data))

count=0

for x in range(data[0]+1):
    for y in range(data[0]+1):
        
        # 枝刈り
        if x+y>data[1]:
            break
        
        if data[0] >= (data[1]-(x+y)) >= 0:
            z = data[1]-(x+y)
            
            if x + y + z == data[1]:
                count+=1
print(count)

### FIXED CODE ###

data = input().split(" ")
data = list(map(int, data))

count=0

for x in range(data[0]+1):
    for y in range(data[0]+1):
        if data[0] >= (data[1]-(x+y)) >= 0:
            z = data[1]-(x+y)
            
            if x + y + z == data[1]:
                count+=1
print(count)