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

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,k = li()
h = list(li())

cost = [float("inf")]*(n)
cost[0] = 0

for i in range(n-1):
    cnt = 1
    while i+cnt < n and cnt <= k:
        cost[i+cnt] = min(cost[i+cnt],
                          cost[i] + abs(h[i+cnt]-h[i]))
        
        cnt += 1
             
print(cost[-1])

### FIXED CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,k = li()
h = list(li())

cost = [float("inf")]*(n)
cost[0] = 0

for i in range(n-1):
    cnt = 1
    while i+cnt < n and cnt <= k:
        cost[i+cnt] = min(cost[i+cnt],
                          cost[i] + abs(h[i+cnt]-h[i]))
        
        cnt += 1
             
print(cost[-1])
### BUGGY CODE ###

from sys import stdin

def checker(x):
    if not x: return 1
    if x[0] != '(' or x[-1] != ')': return 0

    l = x[1:-1].count('(')
    r = len(x[1:-1]) - l
    if l != r: return 0

    return 1

def main():
    from itertools import permutations
    readline = stdin.readline
    n = int(readline())
    s = tuple(readline().strip() for _ in range(n))
    comb_s = tuple(set(permutations(s)))

    res = tuple(filter(lambda x: checker(''.join(x)) == 1, comb_s))
    if not res:
        print('No')
    else:
        print('Yes')
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin

def main():
    readline = stdin.readline
    n = int(readline())
    s = tuple(readline().strip() for _ in range(n))

    plus, minus = [], []
    for c in s:
        if 2 * c.count('(') - len(c) > 0:
            plus.append(c)
        else:
            minus.append(c)

    plus.sort(key = lambda x: x.count(')'))
    minus.sort(key = lambda x: x.count('('), reverse = True)
    plus.extend(minus)
    sum = 0
    for v in plus:
        for vv in v:
            sum = sum + (1 if vv == '(' else -1)
            if sum < 0 : return print('No')
    if sum != 0:
        return print('No')

    return print('Yes')

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

# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/abc075/editorial.pdf
・自力ACしたのがO(N^4)でこれはO(N^5)の愚直解
・制約からして何とかなりそうだし、こっちのが実装全然軽いし実戦向きぽいね。
"""

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

X, Y = [0]*N, [0]*N
for i in range(N):
    X[i], Y[i] = map(int, input().split())

X2 = sorted(set(X))
Y2 = sorted(set(Y))

ans = float('inf')
# 可能性のある全長方形ループ
for x1 in X2:
    for y1 in Y2:
        for x2 in X2:
            for y2 in Y2:
                cnt = 0
                # 各頂点ループで範囲内にあるか1つずつ確認する
                for i in range(N):
                    if x1 <= X[i] <= x2 and y1 <= Y[i] <= y2:
                        cnt += 1
                if cnt >= K:
                    ans = min((x2 - x1) * (y2 - y1), ans)
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

"""
・座標圧縮
・2次元累積和
"""

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

X, Y = [0]*N, [0]*N
for i in range(N):
    X[i], Y[i] = map(int, input().split())

# 座標圧縮
zip_x, zip_y, unzip_x, unzip_y = {}, {}, {}, {}
X2 = sorted(set(X))
Y2 = sorted(set(Y))
# この後の処理のために添字は1-indexedにする
for i in range(len(X2)):
    zip_x[X2[i]] = i+1
    unzip_x[i+1] = X2[i]
for i in range(len(Y2)):
    zip_y[Y2[i]] = i+1
    unzip_y[i+1] = Y2[i]

# 圧縮した座標に点を割り当て(グリッドは累積和用に一回り大きく作る)
grid = [[0] * (len(X2)+1) for _ in range(len(Y2)+1)]
for i in range(N):
    grid[zip_y[Y[i]]][zip_x[X[i]]] += 1

# 2次元累積和
for i in range(len(Y2)+1):
    for j in range(1, len(X2)+1):
        grid[i][j] += grid[i][j-1]
for i in range(1, len(Y2)+1):
    for j in range(len(X2)+1):
        grid[i][j] += grid[i-1][j]

ans = float('inf')
for i in range(1, len(Y2)+1):
    for j in range(1, len(X2)+1):
        # 終点がK以上あれば始点を動かし始める
        if grid[i][j] >= K:
            for k in range(i):
                for l in range(j):
                    # 部分累積和を出して、点がK以上あるか確認
                    if grid[i][j] - grid[i][l] - grid[k][j] + grid[k][l] >= K:
                        # 長方形の面積を出して最小を保持
                        ans = min((unzip_x[j]-unzip_x[l+1]) * (unzip_y[i]-unzip_y[k+1]), ans)
print(ans)
### BUGGY CODE ###

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
d = Counter(a)
c = [0 for _ in range(max(a))]
for k, v in d.items():
    c[k - 1] = v * (v - 1) / 2

for i in range(n):
    ans = sum(c)
    p = a[i]
    res = c[p - 1] * (d[p] - 2) / d[p]
    ans -= c[p - 1] - res
    print(int(ans))


### FIXED CODE ###

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
d = Counter(a)
c = [0 for _ in range(max(a))]
for k, v in d.items():
    c[k - 1] = v * (v - 1) / 2

ans = sum(c)
for i in range(n):
    p = a[i]
    res = c[p - 1] * (d[p] - 2) / d[p]
    ans -= c[p - 1] - res
    print(int(ans))
    ans += c[p - 1] - res
### BUGGY CODE ###

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

count=0
for i in range(N):
    A=P[i]
    if min(P[0:i+1])==A:
        count += 1
    else:
        continue
print(count)

### FIXED CODE ###

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

count=0
mi=P[0]  #minimum

for i in range(N):
    A=P[i]
    if A<=mi:
        mi=A
        count+=1
    else:
        continue

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

k=int(input())
n=7
ans=1
if k%2==0:
    print(-1)
    exit()
while n%k!=0:
    n=(n*10+7)%k
    ans+=1
print(ans)

### FIXED CODE ###

k=int(input())
n=7
ans=1
if k%2==0 or k%5==0:
    print(-1)
    exit()
while n%k!=0:
    n=(n*10+7)%k
    ans+=1
print(ans)
### BUGGY CODE ###

# import sys
# s = input()
# n = len(s)

# if n < 4:
#     print(0)
#     sys.exit()

# ans = 0
# for i in range(n-3):
#     for j in range(i+3, n):
#         a = int(s[i:j+1])
#         # print(i, j, a, a%2019)
#         if a % 2019 == 0:
#             ans += 1
#             print(a)
# print(ans)

# count = 0
# s = input()
# a = int(s) // 2019
# print(a)
# for i in range(a):
#     if str(i*2019) in s:
#         print(str(i*2019))
#         count += 1
# print(count)

import sys
s = input()
n = len(s)
import numpy as np
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

res = [int(s[a:])%2019 for a in range(n)]
num, count = np.unique(res, return_counts=True)
ans = 0
for n, a in zip(num, count):
    if n == 0:
        ans += a
    else:
        if a > 1:
            ans += combinations_count(a, 2)
print(ans)

### FIXED CODE ###

s = input()[::-1]

sum_of_digits = 0

cnts = [0] * 2019

cnts[0] = 1

d = 1

for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019
    cnts[sum_of_digits] += 1

ans = 0
    
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2

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

import math
mod = 1000000007
N,M = list(map(int,input().strip().split()))
m_sqrt = int(math.sqrt(M))
def P(n, r):
  return math.factorial(n)//math.factorial(n-r)
def C(n, r):
  return P(n, r)//math.factorial(r)

ans = 1
cnt = 0
while  M%2 == 0:
  M = M//2
  cnt += 1
ans *= C(N+cnt-1,cnt)
cnt = 0

for i in range(3,m_sqrt+1,2):
  while M%i == 0:
    M = M//i
    cnt += 1
  if cnt != 0:
    ans *= C(N+cnt-1,cnt)
    cnt = 0
if M != 1:
    ans *= C(N,1)

print(ans%mod)


### FIXED CODE ###

import math
mod = 1000000007
N,M = list(map(int,input().strip().split()))
l = []

def P(n, r):
  return math.factorial(n)//math.factorial(n-r)

def C(n, r):
  return P(n, r)//math.factorial(r)

ans = 1
cnt = 0
while  M%2 == 0:
  M //= 2
  cnt += 1
l.append(cnt)
cnt = 0

i = 3
while i**2 <= M:
  cnt = 0
  while M%i == 0:
    M //= i
    cnt += 1
  if cnt != 0:
    l.append(cnt)
    cnt = 0
  i += 2
if M != 1:
    l.append(1)

for i in l:
  for j in range(i):
    ans = ans*(N+j)//(j+1)

print(ans%mod)
### BUGGY CODE ###

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

while abs(n-k) < n:
    n = abs(n - k)

print(n)

### FIXED CODE ###

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

if n > k:
    n = n % k

while abs(n-k) < n:
        n = abs(n - k)

print(n)
### BUGGY CODE ###

import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = list(sorted(map(int, readline().split())))

nums = [0] * (10 ** 6 + 5)

for a in A:
    nums[a] += 1

MAX = 10 ** 6 + 1
pr = set()
for a in A:
    nums[a] -= 1
    b = a
    while b <= MAX:
        if nums[b] > 0:
            pr.add(b)
        b += a
    nums[a] += 1

ans = len(A)
for a in A:
    if a in pr:
        ans -= 1
# print(pr)
print(ans)






### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = list(sorted(map(int, readline().split())))

amax = max(A)
dp = [True] * (amax + 1)
count = [0] * (amax + 1)

for a in A:
    count[a] += 1
    b = 2 * a
    while b <= amax:
        dp[b] = False
        b += a

ans = 0
for a in A:
    if count[a] > 1:
        continue
    if dp[a]:
        ans += 1
print(ans)
### BUGGY CODE ###

h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]
q = int(input())
lr = [list(map(int,input().split())) for _ in range(q)]
b = [0]*(h*w+1)
for i in range(h):
  for j in range(w):
    b[a[i][j]] = (i,j)
for l,r in lr:
  ans = 0
  while(l!=r):
    i,j = b[l]
    l += d
    x,y = b[l]
    ans += abs(x-i)+abs(y-j)
    x += d
  print(ans)

### FIXED CODE ###

h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]
q = int(input())
lr = [list(map(int,input().split())) for _ in range(q)]
b = [0]*(h*w+1)
for i in range(h):
  for j in range(w):
    b[a[i][j]] = (i,j)
c = [0]*(h*w+1)
for i in range(d+1,h*w+1):
  c[i] = c[i-d] + abs(b[i][0]-b[i-d][0])+abs(b[i][1]-b[i-d][1])
for l,r in lr:
  print(c[r]-c[l])
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

N = int(readline())

A = [None] * N
for i in range(N):
  A[i] = list(map(int,readline().split()))
  
# まずワーシャルフロイド表を作る
# ワーシャルフロイド表より大きな数値が元の表にあったら、最短距離の表ではないので-1
# 最短距離の表になっているのであれば、
# A[1][3]に行くときにA[1][2] + A[2][3]となるのであれば、
# A[1][3]のほうだけansに記録していく

ans = 0
for a in A:
  ans += sum(a)
  
for k in range(N):
  for i in range(N):
    for j in range(N):
      if i == k or k == j or i == j:
        continue
      if A[i][k] + A[k][j] < A[i][j]:
        print(-1)
        exit(0)
      if A[i][k] + A[k][j] == A[i][j]:
        ans -= A[i][j]
        
print(ans // 2)

### FIXED CODE ###

import sys
readline = sys.stdin.readline

N = int(readline())

A = [None] * N
for i in range(N):
  A[i] = list(map(int,readline().split()))
  
# まずワーシャルフロイド表を作る
# ワーシャルフロイド表より大きな数値が元の表にあったら、最短距離の表ではないので-1
# 最短距離の表になっているのであれば、
# A[1][3]に行くときにA[1][2] + A[2][3]となるのであれば、
# A[1][3]のほうだけansに記録していく

import copy
newA = copy.deepcopy(A)

for k in range(N):
  for i in range(N):
    for j in range(N):
      if i == k or k == j or i == j:
        continue
      if A[i][k] + A[k][j] < A[i][j]:
        print(-1)
        exit(0)
      elif A[i][k] + A[k][j] == A[i][j]:
        # A[i][j]の道路は不要
        newA[i][j] = 0

ans = 0
for a in newA:
  ans += sum(a)
print(ans // 2)
### BUGGY CODE ###

n,q = map(int,input().split())
s = list(str(input()))
t = [list(map(int,input().split())) for i in range(q)]

for i in range(q):
        r = s[t[i][0]-1:t[i][1]]
        r1 = ''.join(r)
        print(r1.count("AC"))

### FIXED CODE ###

n,q = map(int,input().split())
s = list(input())
c = 0
t = [0]
for i in range(1,n):
        if s[i] == "C" and s[i-1] == "A":
                c = c + 1
        t.append(c)

for i in range(q):
        t1,t2=map(int,input().split())
        print(t[t2-1]-t[t1-1])
### BUGGY CODE ###

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
Q = 10**9+7
def main():
    N = int( input())
    A = list( map( int, input().split()))
    s = 1
    for a in A:
        s = s*a//gcd(a,s)
    ans = 0
    for a in A:
        ans += s//a
        ans %= Q
    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

from collections import defaultdict

def prime_factors(d,N): #素因数 1を含まないことに注意
    ret = []
    middle = int( N**(1/2))
    tmp = N
    for i in range(2, middle+1):
        if tmp%i == 0:
            c = 0
            while tmp%i == 0:
                tmp //= i
                c += 1
            if d[i] < c:
                d[i] = c
    if tmp != 1:
        if d[tmp] == 0:
            d[tmp] = 1

Q = 10**9+7
def main():
    N = int( input())
    A = list( map( int, input().split()))
    d = defaultdict( int)
    for a in A:
        prime_factors(d, a)
    s = 1

    for key, value in d.items():
        s *= pow( key, value)
    ans = 0
    for a in A:
        ans += s*pow(a,Q-2,Q)
    print(ans%Q)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

x = []

for i, a in enumerate(A):
    if i == 0:
        x.append(a)
    else:
        r = len(x) - 1
        l = 0
        while r - l != 1 and r - l != 0:
            m = (r + l) // 2
            if a > x[m]:
                l = m
            else:
                r = m

        if a > x[r]:
            x[r] = a
        elif a > x[l]:
            x[l] = a
        else:
            x.append(a)
        x.sort()

print(len(x))


### FIXED CODE ###

import bisect
import  collections

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

x = collections.deque()

for i, a in enumerate(A):
    if i == 0:
        x.append(a)
    else:
        r = bisect.bisect_left(x, a)
        if r == 0:
            x.appendleft(a)
        else:
            x[r - 1] = a

print(len(x))
### BUGGY CODE ###

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod + x % mod)% mod
def comb(n,k,mod):
    c = 1
    for i in range(k):
        c = c*(n-i)%mod
        c = c*mod_inv(i+1,mod)%mod
    return c
n,a,b = map(int,input().split())
mod = 10**9+7
p = comb(n,a,mod)
q = comb(n,b,mod)
c = 1
k = 2
ans = 1
while n > 0:
    if n % (c*2) == c:
        n -= c
        ans *= k
        ans %= mod
    c *= 2
    k = k*k
    k %= mod
print((ans-p-q-1)%mod)

### FIXED CODE ###

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod + x % mod)% mod
def comb(n,k,mod):
    c = 1
    for i in range(k):
        c = c*(n-i)%mod
        c = c*mod_inv(i+1,mod)%mod
    return c
n,a,b = map(int,input().split())
mod = 10**9+7
p = comb(n,a,mod)
q = comb(n,b,mod)
c = 1
k = 2
ans = 1
while n > 0:
    if n % (c*2) == c:
        n -= c
        ans *= k
        ans %= mod
    c *= 2
    k = k*k
    k %= mod
print((ans-p-q-1)%mod)
### BUGGY CODE ###

# -*- coding utf-8 -*-
n=int(input())
ans=1

for i in range(1,n+1):
    ans=ans*i

print(ans%(10**9+7))


### FIXED CODE ###

# -*- coding utf-8 -*-
n=int(input())
ans=1

for i in range(1,n+1):
    ans=(ans*i)%(10**9+7)

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

# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


N,W = map(int, sys.stdin.readline().rstrip().split())
wv = []
for _ in range(N):
  wv.append(list(map(int, sys.stdin.readline().rstrip().split())))

dp = [[0 for j in range(W+1)] for i in range(N+1)]

for i in range(1,N+1):
  for j in range(1, W+1):
    if j < wv[i-1][0]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]] + wv[i-1][1])

print(max(dp[N]))

### FIXED CODE ###

# /user/bin/python
# -*- coding: utf-8 -*-
import numpy as np
import sys

N,W = map(int, sys.stdin.readline().rstrip().split())

dp = np.zeros(W+1, dtype=np.int64)

for _ in range(N):
  w,v = map(int, sys.stdin.readline().rstrip().split())
  np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])

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

N=int(input())

i=0
sortedSet=[]
result=0
while i<N:
  temp=''.join(sorted(input()))
  sortedSet.append(temp)
  j=0
  while j<i:
    if sortedSet[j]==temp:
      result=result+1
    j=j+1
  i=i+1

print(result)

### FIXED CODE ###

N=int(input())
 
i=0
sortedSet={}
while i<N:
  temp=''.join(sorted(input()))
  
  if temp in sortedSet:
    sortedSet[temp]=sortedSet[temp]+1
  else:
    sortedSet[temp]=1
  i=i+1

  
result=0
for v in sortedSet.values():
  result=int(result+v*(v-1)/2)
 
print(result)
### BUGGY CODE ###

from bisect import bisect
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
for i in range(M):
    b,c = map(int,input().split())
    j = bisect(A,c)
    if b < j:
        A = A[b:j]+[c]*b+A[j:]
    else:
        A[:j] = [c]*j
print(sum(A))

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for i in range(M)]
A.sort(key=lambda x:-x)
BC.sort(key=lambda x:x[1])
C = []
while BC and len(C) < N:
    b,c = BC.pop()
    for i in range(b):
        C.append(c)
        if len(C) == N:
            break
C.sort()
ans = 0
while C:
    a = A.pop()
    c = C.pop()
    ans += max(a,c)
ans += sum(A)
print(ans)
### BUGGY CODE ###

import copy
n = int(input())
xarray = list(map(int,input().split()))
newArray = copy.copy(xarray)
newArray.sort()


for item in xarray:
    if newArray.index(item)<=int(n/2-1):
        print(newArray[int(n/2)])
    else:
        print(newArray[int(n/2)-1])

### FIXED CODE ###

n = int(input())
xarray = list(map(int,input().split()))
newArray = xarray[:]
newArray.sort()

left = newArray[n//2-1]
right = newArray[n//2]


for item in xarray:
    if item<=left:
        print(right)
    else:
        print(left)
### BUGGY CODE ###

N = int(input())

c = 0
for i in range(N):
    c += i
print(c)

### FIXED CODE ###

N = int(input())

c = N*(N-1)//2

print(c)
### BUGGY CODE ###

S = input()
T = input()
s = len(S)
t = len(T)
dp = [[0] * (t + 1) for _ in range(s + 1)]
for i in range(s):
    for j in range(t):
        if S[i] == T[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
A = ''
i = s
j = t
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        A = S[i - 1] + A
        i -= 1
        j -= 1
print(A)

### FIXED CODE ###

s = input()
t = input()

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dpp = dp[i][j] + 1
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dpp)
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])

u = ''
i = len(s)
j = len(t)
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        u = s[i - 1] + u
        i -= 1
        j -= 1

print(u)
### BUGGY CODE ###

import heapq

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

for i in range(M):
  B, C = map(int, input().split())
  for j in range(B):
    c = heapq.heappushpop(A, C)
    if c == C:
      break

print(sum(A))


### FIXED CODE ###

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

CB = []
for i in range(M):
  b, c = map(int, input().split())
  CB.append([c, b])

D = [[a, 1] for a in A] + CB

D.sort()

ans = 0
while N > 0:
  c, b = D.pop()
  ans += min(N, b)*c
  N -= b

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

N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
T = sum(t)*2
vt = [(i/2) if i<T/2 else ((T-i)/2) for i in range(T+1)]
ts = 0
te = 0
for i,ti in enumerate(t):
    te += ti*2
    vi = v[i]
    vt = [min(vtj,vi+((-(j-ts)/2) if j<ts else ((j-te)/2) if j>te else 0)) for j,vtj in enumerate(vt)]
    ts = te
print(sum(vt)/2)

### FIXED CODE ###

N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
T = sum(t)*2
vt = [min(i/2,(T-i)/2) for i in range(T+1)]
ts = 0
te = 0
for i in range(N):
    te += t[i]*2
    for j in range(T+1):
        vt[j] = min(vt[j],v[i]+max(0,-(j-ts)/2,(j-te)/2))
    ts = te
print(sum(vt)/2)
### BUGGY CODE ###

count=0
def merge(A, left, mid, right):
    global count
    n1=mid - left
    n2=right - mid
    L=[i for i in range(n1)]
    R=[i for i in range(n2)]
    for i in range(n1):
        L[i] = A[left+i]
    for i in range(n2):
        R[i] = A[mid+i]
    L.append(1000000001)
    R.append(1000000001)
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
        count+=1
def merge_sort(A, left, right):
    if left+1 < right:
        mid=(left+right)//2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right) 

if __name__ == "__main__":
    n=int(input())
    A=list(map(int,input().split()))
    merge_sort(A,0,n)
    print(*A)
    print(count)


### FIXED CODE ###

count=0
def merge(A, left, mid, right):
    global count
    L=A[left:mid]+[2**32]
    R=A[mid:right]+[2**32]
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        count+=1
def merge_sort(A, left, right):
    if left+1 < right:
        mid=(left+right)//2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right) 

if __name__ == "__main__":
    n=int(input())
    A=list(map(int,input().split()))
    merge_sort(A,0,n)
    print(*A)
    print(count)