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

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    a=tuple(map(int,input().split()))
    dp0=[1]*N
    dp1=[1]*N
    mask=(1<<K)-1
    for i in range(N-1):
        if a[i]<K:
            dp0[i+1]=(dp0[i]|(dp0[i]<<a[i]))&mask
        else:
            dp0[i+1]=dp0[i]
        if a[N-i-1]<K:
            dp1[N-i-2]=(dp1[N-i-1]|(dp1[N-i-1]<<a[N-i-1]))&mask
        else:
            dp1[N-i-2]=dp1[N-i-1]
    ans=0
    for i in range(N):
        if a[i]<K:
            mask2=((1<<a[i])-1)<<(K-a[i])
            dp_0=dp0[i]
            dp_1=dp1[i]
            for j in range(dp_0.bit_length()):
                if dp_0&1:
                    if dp_1&mask2:
                        break
                dp_0>>=1
                dp_1<<=1
                dp_1&=mask
                if not dp1:
                    break
            else:
                ans+=1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=1)
    dp0=[1]*N
    dp1=[1]*N
    mask=(1<<K)-1
    for i in range(N-1):
        if a[i]<K:
            dp0[i+1]=(dp0[i]|(dp0[i]<<a[i]))&mask
        else:
            dp0[i+1]=dp0[i]
        if a[N-i-1]<K:
            dp1[N-i-2]=(dp1[N-i-1]|(dp1[N-i-1]<<a[N-i-1]))&mask
        else:
            dp1[N-i-2]=dp1[N-i-1]
    ans=0
    def nibutan(ok,ng):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(i):
        if a[i]<K:
            mask2=((1<<a[i])-1)<<(K-a[i])
            for j in range(dp0[i].bit_length()):
                if j>mask2.bit_length():
                    return True
                if (dp0[i]>>j)&1:
                    if dp1[i]&(mask2>>j):
                        return True
        else:
            return True
        return False
    
    res=nibutan(-1,N)
    print(N-1-res)
    


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

import math
import sys
input = sys.stdin.readline


def main():
    sc = Scan()
    a, b, c, d = sc.intarr()
    count = 0
    for i in range(a, b+1):
        if i % c != 0 and i % d != 0:
            count += 1
    print(count)


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


main()


### FIXED CODE ###

import sys
import math
input = sys.stdin.readline


def main():
    sc = Scan()
    A, B, C, D = sc.intarr()
    div_b = B//C + B//D - B//(lcm(C, D))
    div_a = (A-1)//C + (A-1)//D - (A-1)//(lcm(C, D))

    ans = B - (A-1) - div_b + div_a

    print(ans)


def format_str(num):
    if num < 10:
        return "00" + str(num)
    elif num < 100:
        return "0" + str(num)
    else:
        return str(num)


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def intarr_ver(self, n):
        return [int(input()) for _ in range(n)]

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


def display(array):
    for a in range(len(array)):
        if len(array) - a != 1:
            print(array[a], end=' ')
        else:
            print(array[a])


def gcd(a, b):  # 最大公約数
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):  # 最小公倍数
    return a * b // gcd(a, b)


main()
### BUGGY CODE ###

N = int(input().strip())
S = input().strip()

max_length = 0

for i in range(N):
    for length in range(N - i):
        if S[i:i+length] in S[i+length:]:
            if length > max_length:
                max_length = length

print(max_length)


### FIXED CODE ###

N = int(input().strip())
S = input().strip()

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

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

max_length = 0
for i in range(N):
    for j in range(N):
        if i < j:
            length = min(j - i, dp[i][j])
            max_length = max(length, max_length)

print(max_length)
### BUGGY CODE ###

n = int(input())
arr = []
passed = []
for i in range(n):
  a = int(input())
  arr.append(a)
  
next_position = 1
ans = 0

while(1):
  next_position = arr[next_position-1]
  #print(position)
  if next_position in passed:
    print(-1)
    break
  passed.append(next_position)
  ans += 1
  if next_position == 2:
    print(ans)
    break
  

### FIXED CODE ###

n = int(input())
arr = []
passed = []
for i in range(n):
  a = int(input())
  arr.append(a)
  
next_position = 1
ans = 0

while(1):
  next_position = arr[next_position-1]
  #print(position)
  if ans == n:
    print(-1)
    break
  #passed.append(next_position)
  ans += 1
  if next_position == 2:
    print(ans)
    break
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
import functools
import operator

result = functools.reduce(operator.mul, a)

if result > 10**18 :
    print(-1)
else :
    print(result)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
if 0 in a :
    ans  = 0
    print(ans)
else :
    ans = 1
    for i in range(n):
        ans *= a[i]
        if ans > 10**18 :
            print(-1)
            break
if ans <= 10**18 and ans != 0 :
    print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = ''
for i in range(n):
  i += 1
  ans += str(a.index(i)+1) + ' '
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = [0 for _ in range(n)]
for i,j in enumerate(a):
  ans[j-1] = str(i+1)
print(' '.join(ans))
### BUGGY CODE ###

import numpy as np

N, M = list(map(int, input().split()))
jobs = [[] for _ in range(M)]

for i in range(N):
    d, r = list(map(int, input().split()))
    if d-1 < M:
        jobs[d-1].append(r)

rewords = 0
li = []
for i in range(M):
    li.extend(jobs[i])
    if len(li) >0:
        reword = np.max(li)
        rewords += reword
        li.remove(reword)
    
print(rewords)

### FIXED CODE ###

import heapq

N, M = list(map(int, input().split()))
jobs = [[] for _ in range(M)]

for i in range(N):
    d, r = list(map(int, input().split()))
    if d-1 < M:
        jobs[d-1].append(-r)

rewords = 0
heap = []

for i in range(M):
    for reword in jobs[i]:
        heapq.heappush(heap, reword)
    if len(heap) >0:
        r = heapq.heappop(heap)
        rewords -= r

print(rewords)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

n,m,k = map(int,input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.append(1)
b.append(1)
ans = 0

def dfs(time,count,i,j):
    global ans,n,m,k,a,b
    if (i == n or time + a[i] > k) and (j == m or time + b[j] > k):
        ans = max(ans, count)
    else:
        if i <= n-1 and time + a[i] <= k:
            dfs(time + a[i],count + 1,i+1,j)
        if j <= m-1 and time + b[j] <= k:
           dfs(time + b[j],count + 1,i,j+1)  

shoki_time = 0
shoki_count = 0
shoki_i = 0
shoki_j = 0
dfs(shoki_time,shoki_count,shoki_i,shoki_j)
print(ans)

### FIXED CODE ###

n,m,k=map(int,input().split())
arr1=list(map(int,input().split()))
arr2=list(map(int,input().split()))
acum1=[0]
for i in range(n): #累積和ai,bjを求める
 acum1.append(acum1[-1]+arr1[i])
acum2=[0]
for i in range(m):
 acum2.append(acum2[-1]+arr2[i])
ans=0
j=m
for i in range(n+1):
 if acum1[i]>k: #ai>Kであれば、どのようにjを選んでもai+bj<=Kとなることはないので探索を終了する
   break
 while acum2[j]>k-acum1[i] and j>0: #各iについて、bj<=K-aiを満たす最大のjを求める
   j-=1
 ans=max(ans,i+j)
print(ans)
### BUGGY CODE ###

import sys
for line in sys.stdin:
	lis = []
	num = int(line)
	if num >= 2:
		lis.append(2)
	if  num >= 3:
		lis.append(3)
	if num >= 5:
		for i in xrange(5,num+1,2):
			for item in lis:
				if item > (i**0.5):
					lis.append(i)
					break
				if i % item == 0:
					break
			else:
				lis.append(i)
	print len(lis)

### FIXED CODE ###

import sys
N = 999999
lis = []
if N >= 2:
	lis.append(2)
if  N >= 3:
	lis.append(3)
if N >= 5:
	for i in xrange(5,N+1,2):
		for item in lis:
			if item > (i**0.5):
				lis.append(i)
				break
			if i % item == 0:
				break
		else:
			lis.append(i)
dp = [0]*999999
for item in lis:
	dp[item-1] += 1
for i in xrange(1,999999):
	dp[i] += dp[i-1]

for line in sys.stdin:
	num = int(line)
	print dp[num-1]
### BUGGY CODE ###

n = int(input())
lis = list(map(int, input().split()))
ans = 0
for i in range(len(lis)):
    if min(lis[:i+1]) == lis[i]:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
lis = list(map(int, input().split()))
ans = 0
minl = lis[0]
for i in lis:
    if minl >= i:
        minl = i
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
s = [input() for _ in range(n)]

l = []
list_num = []
for i in range(n):
  l.append([s[i], s.count(s[i])])
  list_num.append(s.count(s[i]))

max_num = max(list_num)

se = set()
for i in range(n):
  if l[i][1] == max_num:
    se.add(l[i][0])
l_2 =list(se)
l_2.sort()

print(*l_2, sep = "\n")

### FIXED CODE ###

from collections import Counter

n = int(input())
s = [input() for _ in range(n)]

c = Counter(s)
c = c.most_common()
ans_number = c[0][1]
c.sort()

for i in range(len(c)):
  if c[i][1] == ans_number:
    print(c[i][0])
### BUGGY CODE ###

N=int(input())
s=[]
cnt=0
for i in range(N):
    s.append(input())
s=list(map(sorted,s))
s=sorted(s)
for j in range(N-1):
    for k in range(j+1,N):
        if s[j]==s[k]:
            cnt+=1
        else:
            break
print(cnt)

### FIXED CODE ###

N=int(input())
dic={}
cnt=0
for i in range(N):
    temp=' '.join(sorted(input()))
    if temp in dic:
        dic[temp]+=1
    else:
        dic[temp]=1
for k,v in dic.items():
    cnt+=v*(v-1)//2
print(cnt)
### BUGGY CODE ###

n, a, b, c, d = map(int, raw_input().split())
MOD = 10**9+7
fact = [1]*(n+1)
frev = [1]*(n+1)

rcd = range(c, d+1)

dp = [0]*(n+1)
dp[0] = 1

for i in xrange(1, n+1):
    v = fact[i] = (fact[i-1] * i) % MOD
    frev[i] = pow(v, MOD-2, MOD)
Y = [None]*(d+1-c)
for g in xrange(a, min(n/c, b)+1):
    p = c*g
    y = frev[g]
    Y[:min(d,n/g)+1-c] = (pow(y, j, MOD)*frev[j] for j in xrange(c, min(d, n/g)+1) if p<=i)
    dp[:c*g-1:-1] = (dp[i] + frev[n-i]*sum(dp[i-g*j] * fact[n-i+g*j] * Y[j-c] for j in xrange(c, min(d, i/g)+1)) % MOD for i in xrange(n, p-1, -1))
print dp[n]%MOD

### FIXED CODE ###

n, a, b, c, d = map(int, raw_input().split())
dp = [0]*(n+1)
dp[0] = 1

MOD = 10**9+7
fact = [1]*(n+1)
frev = [1]*(n+1)

rn = range(n, -1, -1)

for i in xrange(1, n+1):
    fact[i] = (fact[i-1] * i) % MOD
    frev[i] = pow(fact[i], MOD-2, MOD)
for g in xrange(a, b+1):
    y = frev[g]
    for i in rn:
        x = frev[n-i]
        dp[i] = (dp[i] + sum(dp[i-g*j] * fact[n-i+g*j] * x * pow(y, j, MOD) * frev[j] for j in xrange(c, min(d, i/g)+1))) % MOD
print dp[n]
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[]
for m in range(M):
    b,c=map(int,input().split())
    B+=[c]*b
A=sorted(A)
B=sorted(B)[::-1]
Max=0
for i in range(N+1):
    New=sum(A[i:])+sum(B[:i])
    if New>Max:
        Max=New
print(Max)

### FIXED CODE ###

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

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

A.sort()
BC.sort(key=lambda x:x[1],reverse=True)

D=[]
for [b,c] in BC:
    D+=[c]*b
    if len(D)>N:
        break

if len(D)<N:
    D+=[0]*(N-len(D))

AD=[max(A[i],D[i]) for i in range(N)]
 
print(sum(AD))
### BUGGY CODE ###

import numpy as np
n = int(input())
a = list(map(int, input().split()))
A = []
for i in range(n):
    c = [0] * n
    if i != n-1:
        c[i], c[i+1] = 0.5, 0.5
    else:
        c[0], c[n-1] = 0.5, 0.5
    A.append(c)

A = np.array(A)
b = np.array(a)
ans = list(np.linalg.solve(A, b))
ans = map(int, ans)
ans = map(str, ans)
print(" ".join(ans))


### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]
s = sum(a)
ans = [0] * n
even_a = 0
for i in a[1::2]:
    even_a += i
ans[0] = s - 2 * even_a
for i in range(1, n):
    ans[i] = 2 * a[i-1] - ans[i-1]
print(" ".join(map(str, ans)))
### BUGGY CODE ###

N = int(input())

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

d = {}
for i in range(N):
    if A[i] not in d:
        d[A[i]] = 0
    d[A[i]] += 1


ans = 0
for k in d:
    if d[k] >= 4:
        ans = max(ans, k ** 2)
    
    if d[k] >= 2:
        for l in d:
            if k == l: continue
            elif d[l] >= 2:
                ans = max(ans, k * l)

print(ans) 

### FIXED CODE ###

N = int(input())

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

d = {}
for i in range(N):
    if A[i] not in d:
        d[A[i]] = 0
    d[A[i]] += 1


ans = {0}
s1 = [k for k, v in d.items() if v >= 4]
if len(s1) > 0:
    s1.sort()
    ans.add(s1[-1] ** 2)

s2 = [k for k, v in d.items() if v >= 2]
if len(s2) >= 2:
    s2.sort()
    ans.add(s2[-1] * s2[-2])

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

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

A.sort()

factorial = [1]
for i in range(1, N + 1):
    factorial.append(factorial[-1] * i)
inv_factorial = [-1] * (N + 1)
inv_factorial[-1] = pow(factorial[-1], MOD - 2, MOD)
for i in reversed(range(N)):
    inv_factorial[i] = inv_factorial[i + 1] * (i + 1) % MOD


ans = 0
for i in range(N - K + 1):
    c = factorial[N - 1 - i] * inv_factorial[K - 1] * inv_factorial[N - K - i]
    ans += c * (A[-1 - i] - A[i])
    ans %= MOD

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

A.sort()

factorial = [1]
for i in range(1, N + 1):
    factorial.append(factorial[-1] * i  % MOD)
inv_factorial = [-1] * (N + 1)
inv_factorial[-1] = pow(factorial[-1], MOD - 2, MOD)
for i in reversed(range(N)):
    inv_factorial[i] = inv_factorial[i + 1] * (i + 1) % MOD


ans = 0
for i in range(N - K + 1):
    c = factorial[N - 1 - i] * inv_factorial[K - 1] * inv_factorial[N - K - i]
    ans += c * (A[-1 - i] - A[i])
    ans %= MOD

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

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

if n==1:
  print(p)
else:
  ans=1
  for i in range(1,int(p**(1/n))+2):
    tmp=i**n
    if (p>=tmp) and (p%tmp == 0):
     ans=i
    if(p<tmp):
      break
  print(ans)


### FIXED CODE ###

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

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

kekka=factorize(p)

ans=1
for i in range(len(kekka)):
    ans=ans* kekka[i][0] ** (kekka[i][1]//n)
print(ans)
### BUGGY CODE ###

n,a,b=map(int,input().split())
s=input()
passed=0
oversea=[]
for i in range(n):
    if s[i]=="b":
        oversea.append(i)
for i in range(n):
    if s[i]=="c":
        print("No")
    elif s[i]=="a":
        if passed<(a+b):
            print("Yes")
            passed+=1
        else:
            print("No")
    else:
        if oversea.index(i)<b and passed<(a+b):
            print("Yes")
            passed+=1
        else:
            print("No")
    

### FIXED CODE ###

n,a,b=map(int,input().split())
s=input()
passed=0
oversea=0
yep=False
cnt=0
for i in range(n):
    if s[i]=="c":
        print("No")
    elif s[i]=="a":
        if passed<(a+b):
            print("Yes")
            passed+=1
        else:
            print("No")
    else:
        if oversea<b and passed<(a+b):
            print("Yes")
            passed+=1
            oversea+=1
        else:
            print("No")
#     if passed>=(a+b):
#         yep=True
#         cnt=len(s)-(i+1)
#         break
# if yep:
#     for i in range(cnt):
#         print("No")
### BUGGY CODE ###

n,a,b=map(int,input().split())
s=0
if n>=(a+b):

    while True:

        n=n-(a+b)

        s+=1

        if n-(a+b)<=0:

            break
        else:pass

    if n>=a:

        print(a*(s+1))
    else:
        print(a*s+n)

else:

    if n>=a:

        print(a)

    else:
        print(n)
        


### FIXED CODE ###

n,a,b=map(int,input().split())

if n>=(a+b):

    k=int(n/(a+b))

    l=int(n%(a+b))

    if l>=a:

        print(a*k+a)

    else:
        print(a*k+l)

else:

    if n>=a:

        print(a)

    else:
        print(n)
### BUGGY CODE ###

#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy

# from typing import Dict, List, Optional, Set, Tuple


# def solve(values: List[int], nb_vertices: int, nb_edges: int) -> int:
def solve(values, nb_vertices, nb_edges) -> int:
    succ = defaultdict(set)
    for s, d in values:
        succ[s].add(d)
    # all edges have a 0 length path starting at the edge
    dp = [True] * nb_vertices
    max_length_path = 0
    for length in range(1, nb_edges + 1):
        prev = dp.copy()
        dp = [False] * nb_vertices
        # vertices are indexed from 1
        for vertex in range(1, nb_vertices + 1):
            for d in succ[vertex]:
                if prev[d - 1]:
                    dp[vertex - 1] = True
                    max_length_path = length
                    break
    return max_length_path


def do_job():
    "Do the work"
    # first line is number of test cases
    N, M = map(int, input().split())
    values = []
    for _ in range(M):
        values.append(tuple(map(int, input().split())))
    result = solve(values, N, M)
    print(result)


def main():
    "Program wrapper."
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


### FIXED CODE ###

#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys
from collections import defaultdict

sys.setrecursionlimit(pow(2, 31) - 1)

# from typing import Dict, List, Optional, Set, Tuple

# def dfs(vertex: int, succ: Dict[int, List[int]], dp: Dict[int, int]) -> int:
def dfs(vertex, succ, dp):
    if vertex in dp:
        return dp[vertex]
    length = 0
    for s in succ[vertex]:
        length = max(length, 1 + dfs(s, succ, dp))
    dp[vertex] = length
    return length


# def solve(values: List[int], nb_vertices: int, nb_edges: int) -> int:
def solve(values, _nb_vertices, _nb_edges) -> int:
    succ = defaultdict(list)
    for s, d in values:
        succ[s].append(d)
    # all edges have a 0 length path starting at the edge
    dp = defaultdict(lambda: -1)
    for vertex in frozenset(succ.keys()):
        if vertex in dp:
            dp[vertex] = max(dp[vertex], dfs(vertex, succ, dp))
        else:
            dp[vertex] = dfs(vertex, succ, dp)
    return max(dp.values())


def do_job():
    "Do the work"
    # first line is number of test cases
    N, M = map(int, input().split())
    values = []
    for _ in range(M):
        values.append(tuple(map(int, input().split())))
    result = solve(values, N, M)
    print(result)


if __name__ == "__main__":
    do_job()
### BUGGY CODE ###

from itertools import combinations

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

devide_num = min(N -1, M - 1)

devides = combinations(range(len(X)), devide_num)


mincost = X[-1] - X[0]
for devide in devides:
    previous = 0
    cost = 0
    for next_point in devide:
        cost += X[next_point] - X[previous]
        if next_point + 1 < M:
            previous = next_point + 1
        else:
            break
    # last
    cost += X[-1] - X[previous]

    mincost = min(cost, mincost)

print(mincost)






### FIXED CODE ###

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

diffs = [X[i+ 1] - X[i] for i in range(len(X) - 1)]
diffs.sort(reverse=True)

skip = N - 1
print(sum(diffs[skip:]))
### BUGGY CODE ###

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

b = [(a[i]-i-1) for i in range(n)]
#print(b)

res1 = min(b)
res2 = max(b)
ans = float('inf')
for j in range(res1, res2+1, 1):
  res = 0
  for i in range(n):
    res += abs(b[i]-j)
    
  ans = min(ans, res)
  
print(ans)

### FIXED CODE ###

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

b = [(a[i]-i-1) for i in range(n)]
b = sorted(b)

if n % 2 == 1:
  res = b[(n-1)//2]
else:
  res = (b[n//2-1] + b[n//2])//2
  
print(sum(map(abs, [b[i]-res for i in range(n)])))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+7

def gcd(a,b):
    x = max([a,b])
    y = min([a,b])
    while y:
        x, y = y, x % y
    return x

# x * y = lcm(x, y) // gcd(x, y)より
def lcm(x, y):
    return x * y // gcd(x, y)


tmp = A[0]
for a in A[1:]:
    tmp = lcm(tmp, a)

B = [0] * N
for i in range(N):
    B[i] = tmp // A[i]

ans = 0
for b in B:
    ans += b
    ans %= MOD
    

print(ans)

### FIXED CODE ###

from fractions import gcd


def main():
        
    N = int(input())
    A = list(map(int, input().split())) 
    MOD = 10**9 + 7


    l = 1

    for a in A:
        l = l * a // gcd(l, a)


    ans = 0
    for a in A:
        ans += (l // a)
    ans %= MOD

    print(ans)


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

from collections import deque
n = int(input())
a_list = [None for _ in range(n)]
num = 0
day = 0
for i in range(n):
    a_list[i] = deque([int(i) - 1 for i in input().split()])

while (num < n * (n - 1) // 2):
    visit = set([])
    day += 1
    for j in range(n):
        if j not in visit:
            if len(a_list[j]) > 0:
                k = a_list[j][0]
                if k not in visit:
                    if a_list[k][0] == j:
                        num += 1
                        visit.add(a_list[j].popleft())
                        visit.add(a_list[k].popleft())
    if ((j == n - 1) & (len(visit) == 0)):
        day = -1
        break
print(day)

### FIXED CODE ###

from collections import deque
n = int(input())
a_list = []
for i in range(n):
    a_list.append(deque([int(aa) - 1 for aa in input().split()]))
day = 0
battle = 0
for _ in range(n * (n - 1) // 2):
    if battle == n * (n - 1) // 2:
        break
    day += 1
    battle_today = 0
    tomorrow = set([])
    if (day == 1):
        player = set([i for i in range(n)])
    for i in player:
        if len(a_list[i]) == 0:
            continue
        j = a_list[i][0]
        if (i == a_list[j][0]) & (j not in tomorrow) & (len(a_list[j]) > 0) & (i not in tomorrow):
            tomorrow.add(i)
            tomorrow.add(a_list[i][0])
            battle += 1
            battle_today += 1
            a_list[i].popleft()
            a_list[j].popleft()
    player = tomorrow
    if battle_today == 0:
        day = -1
        break
print(day)