CodeEff/ECCO huggingface dataset:
# Original solution
def c_many_medians(N, X):
    x = [[0, 0] for _ in range(N)]
    for i, e in enumerate(X):
        x[i] = [i, e]
    x.sort(key=lambda k: k[1])
    mid = N // 2 - 1
    a, b = [0] * N, [0] * N
    for i, (k, v) in enumerate(x):
        p=x.index([k,v])
        a[k] = p
        b[i] = v
    ans = ['' for _ in range(N)]
    for i in a:
        if b[mid]>=b[a[i]]:
            ans[i]='{}'.format(b[mid+1])
        else:
            ans[i]='{}'.format(b[mid])
    return '\n'.join(ans)

N = int(eval(input()))
X = [int(i) for i in input().split()]
print((c_many_medians(N, X)))

# Optimized solution
def c_many_medians(N, X):
    # 解説どおり
    Y = sorted(X)
    ans = ['' for _ in range(N)]
    pos = N // 2
    for k, xi in enumerate(X):
        if xi < Y[pos]:
            ans[k] = str(Y[pos])
        else:
            ans[k] = str(Y[pos - 1])
    return '\n'.join(ans)

N = int(eval(input()))
X = [int(i) for i in input().split()]
print((c_many_medians(N, X)))
# Original solution
def C(m):
    if xsort[m] > x[i]: 
        return True
    return False
 
 
n = int(eval(input()))
x = list(map(int, input().split()))

xsort = sorted(x)

for i in range(n):
    mb = 0
    lb = n
    m = (mb+lb) // 2
    for j in range(100):
        if C(m):
            lb = m
        else: 
            mb = m
    if mb < n//2:
        print((xsort[n//2]))
    else:
        print((xsort[n//2-1]))

# Optimized solution
N = int(eval(input()))
X = list(map(int, input().split()))
Y = sorted(X)
m1 = Y[N//2]
m2 = Y[N//2-1]
 
for i in range(N):
    if m1 > X[i]:
        print(m1)  # left
    else:
        print(m2)  # right
# Original solution
N = int(eval(input()))
X_list = list(map(int, input().split()))

for i in range(N):
    tmp = X_list.copy()
    tmp.pop(i)
    tmp.sort()
    print((tmp[int(N/2)-1]))

# Optimized solution
N = int(eval(input()))
X_list = list(map(int, input().split()))
tmp = X_list.copy()

tmp.sort()
a = tmp[int(N/2)-1]
b = tmp[int(N/2)]
for i in range(N):
    if(X_list[i] <= a):
        print(b)
    else:
        print(a)
# Original solution
#!/usr/bin/env python3

def main():
    n = int(input())
    x = list(map(int, input().split()))
    ans = [0] * n
    for i in range(n):
        fix = x[0:i] + x[i + 1:n]
        fix.sort()
        ans[i] = fix[n // 2 - 1]
    print(*ans, sep='\n')


if __name__ == "__main__":
    main()


# Optimized solution
#!/usr/bin/env python3

def main():
    n = int(input())
    x = list(map(int, input().split()))
    ans = [0] * n
    x_sort = sorted(x)
    a = x_sort[1:n]
    a_med = a[n // 2 - 1]
    b = x_sort[0:n - 1]
    b_med = b[n // 2 - 1]
    for i in range(n):
        if x[i] < a_med:
            ans[i] = a_med
        else:
            ans[i] = b_med

    print(*ans, sep='\n')


if __name__ == "__main__":
    main()
# Original solution
N=int(eval(input()))
R=[0]*N
K=(N//2)-1
S=K+1
L=list(map(int,input().split()))
for i in range(N):
  R[i]=[L[i],i]
R=sorted(R)
for i in range(N):
  if R.index([L[i],i])<S:
    print((R[S][0]))
  else:
    print((R[K][0]))

# Optimized solution
N=int(eval(input()))
L=list(map(int,input().split()))
n=N//2
R=sorted(L)
for i in L:
  if i>R[n-1]:
    print((R[n-1]))
  else:
    print((R[n]))
# Original solution
# ABC094 C - Many Medians
n = int(eval(input()))
x = list(map(int,input().split()))

for i in range(n):
    y = x[:]
    y[i] = 0
    y.sort()
    print((y[int((n/2))]))



# Optimized solution
# ABC094 C - Many Medians
n = int(eval(input()))
x = list(map(int,input().split()))

y = sorted(x)
l = y[n//2 - 1]
r = y[n//2]
 
for x in x:
  print((l if x >= r else r))
# Original solution
N = int(eval(input()))
X = list(map(int, input().split()))

for i in range(N):
    C = sorted([x for index, x in enumerate(X) if index != i])
    print((C[len(C)//2]))


# Optimized solution
N = int(eval(input()))
X = list(map(int, input().split()))
Y = sorted(X)
CL = Y[N//2-1]
CR = Y[N//2]

for x in X:
    if x < CR:
        print(CR)
    else:
        print(CL)
# Original solution
n = int(eval(input()))
x = list(map(int, input().split()))
y = sorted(x)

for i in range(n):
    z = y.copy()
    z.remove(x[i])
    print((z[n//2 -1]))

# Optimized solution
n = int(eval(input()))
x = list(map(int, input().split()))
y = sorted(x)
a = y[n//2 - 1]
b = y[n//2]

for i in range(n):
    if x[i] >= b:
        print(a)
    else:
        print(b)
# Original solution
n = int(eval(input()))
A = list(map(int, input().split()))

for i in range(n):
    A2 = A.copy()
    A2.pop(i)
    A2.sort()
    print((A2[(n // 2) - 1]))

# Optimized solution
n = int(eval(input()))
A = list(map(int, input().split()))
sortA = sorted(A)

for i in range(n):
    if A[i] <= sortA[(n // 2) - 1]:
        print((sortA[n // 2]))
    else:
        print((sortA[(n // 2) - 1]))
# Original solution
n = int(eval(input()))
A = list(map(int, input().split()))
sortA = sorted(A)

for i in range(n):
    if A[i] <= sortA[(n // 2) - 1]:
        print((sortA[n // 2]))
    else:
        print((sortA[(n // 2) - 1]))

# Optimized solution
n = int(eval(input()))
A = [int(i) for i in input().split()]

sortA = sorted(A)
mid = sortA[n//2 - 1]
midnext = sortA[n//2]

for i in range(n):
    if A[i] <= mid:
        print(midnext)
    else:
        print(mid)
# Original solution
n = int(eval(input()))
A = [int(i) for i in input().split()]

sortA = sorted(A)
mid = sortA[n//2 - 1]
midnext = sortA[n//2]

for i in range(n):
    if A[i] <= mid:
        print(midnext)
    else:
        print(mid)

# Optimized solution
n = int(eval(input()))
X = [int(i) for i in input().split()]
sortX = sorted(X, reverse=True)
m1 = sortX[n // 2 - 1]
m2 = sortX[n // 2]

for i in range(n):
    if X[i] < m1:
        print(m1)
    else:
        print(m2)
# Original solution
n = int(eval(input()))
x = list(map(int, input().split()))
sx = sorted(x)
m = n//2
l = sx[m - 1: m + 1]

for i in range(n):
    if x[i] < l[1]:
        print((l[1]))
    else:
        print((l[0]))

# Optimized solution
n = int(eval(input()))
x = list(map(int, input().split()))
sx = sorted(x)
m = n//2
l = sx[m - 1: m + 1]

for i in x:
    if i < l[1]:
        print((l[1]))
    else:
        print((l[0]))
# Original solution
n = int(eval(input()))
x = list(map(int, input().split()))
num = (n // 2) - 1

for i in range(n):
    l = x[:]
    l.pop(i)
    l.sort()
    print((l[num]))

# Optimized solution
n = int(eval(input()))
x = list(map(int, input().split()))
y = sorted(x[:])

for i in range(n):
    if x[i] < y[n//2]:
        print((y[n//2]))
    else:
        print((y[n//2 - 1]))
# Original solution
import collections as cl

def get_median(arr) :
	
	idx = len(arr) + 1
	idx = int(idx / 2) - 1
	return arr[idx]

N = int(eval(input()))
X = [int(i) for i in input().split()]
X2 = X[:]
X2.sort(reverse=True)
dic = {}

for i in range(len(X)) :
	l = X2[:]
	key = l.pop(i)
	if (key not in dic) :
		dic[key] = get_median(l)

for i in X :
	print((dic[i]))

# Optimized solution
N = int(eval(input()))
X = [int(i) for i in input().split()]
X2 = sorted(X)
mapper = {}

for i in range(N//2) :
    if (X2[i] in mapper) :
        continue
    mapper[X2[i]] = X2[len(X2)//2]

for i in range(N//2,N) :
    if (X2[i] in mapper) :
        continue
    mapper[X2[i]] = X2[(len(X2)//2) - 1]

for x in X :
    print((mapper[x]))
# Original solution
N = int(eval(input()))
array = list(map(int, input().split()))
for i in range(0, N):
    konichiwa = list(array)
    konichiwa.pop(i)
    konichiwa.sort()
    print((konichiwa[int(N / 2) - 1]))


# Optimized solution
N = int(eval(input()))
array = list(map(int, input().split()))
test = list(array)
test.sort()
wow = test[int(N / 2) - 1: int(N / 2) + 1]
for i in range(0, N):
    if array[i] > wow[0]:
        print((wow[0]))
    else:
        print((wow[1]))
# Original solution
#!/usr/bin/env python
import sys 
import copy
input = sys.stdin.readline

n = int(eval(input()))
x = list(map(int, input().split()))

for i in range(n):
    xx = copy.deepcopy(x)
    xx.pop(i)
    xx = sorted(xx)
    print((xx[(n-1)//2]))


# Optimized solution
#!/usr/bin/env python
import sys 
import copy
input = sys.stdin.readline

n = int(eval(input()))
x = list(map(int, input().split()))
xx = sorted(x)

l = xx[(n-1)//2]
r = xx[n//2]
mid = (l+r)/2

for i in range(n):
    if x[i] >= mid:
        print(l)
    else:
        print(r)
# Original solution
N = int(eval(input()))
Alist = list(map(int, input().split()))
Alist = [Alist[i] - (i+1) for i in range(N)]
Alist.sort()

if N == 1:
    print((0))
else:    
    sumlist = []
    for i in range(N-1):
        if i < N // 2:
            sumlist.append(- sum(Alist[:i+1]) + sum(Alist[i+1:]) - Alist[i+1] * (N - 2 * (i + 1)))
        else:
            sumlist.append(- sum(Alist[:i+1]) + sum(Alist[i+1:]) + Alist[i] * (N - 2 * (N - i - 1)))
        
    print((min(sumlist)))


# Optimized solution
N = int(eval(input()))
Alist = list(map(int, input().split()))
Alist = [Alist[i] - (i+1) for i in range(N)]
Alist.sort()

b = Alist[N//2]

ans = 0
for i in range(N):
    ans += abs(Alist[i] - b)
print(ans)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))

def f(b):
    r = 0
    for i, ai in enumerate(A):
        r += abs(ai - (b + i + 1))
    return r

mx = (10 ** 9) + 1
mn = (-10 ** 9) - 1

# print(f(0))
while mx - mn > 10:
    m = (mx + mn) // 2
    x = f(m)
    y = f(m+1)
    if x < y:
        mx = m + 1
    else:
        mn = m


ans = []
for i in range(mn, mx+1):
    ans.append(f(i))
print((min(ans)))

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))

def f(b):
    r = 0
    for i, ai in enumerate(A):
        r += abs(ai - (b + i + 1))
    return r


A2 = []
for i, ai in enumerate(A):
    A2.append(ai - (i+1))

SA2 = sorted(A2)
ans = f(SA2[((N+1)//2) - 1])
print(ans)
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
b=[0]
c=[0]
d=[0]
e=[0]
count=0
count2=0
count3=0
count4=0
for i in range(n):
  a[i]-=i
a.sort()
for i in range(n-1):
  count+=a[i+1]-a[i]
  count3+=a[n-i-1]-a[n-i-2]
  b.append(count)
  d.append(count3)
for i in range(n-1):
  count2+=b[i+1]
  count4+=d[i+1]
  c.append(count2)
  e.append(count4)
ans=10**18
for i in range(n):
  ans=min(ans,c[-1]-c[i]-b[i]*(n-i-1)+e[-1]-e[n-i-1]-d[n-i-1]*i)
print(ans)

# Optimized solution
n=int(eval(input()))
a=list(map(int,input().split()))
for i in range(n):
  a[i]-=i
a.sort()
x=a[n//2]
ans=0
for i in range(n):
  ans+=abs(a[i]-x)
print(ans)
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
for i in range(n):
  a[i]-=i
a.sort()
x=a[n//2]
ans=0
for i in range(n):
  ans+=abs(a[i]-x)
print(ans)

# Optimized solution
n=int(eval(input()))
a=[int(i) for i in input().split()]
a=[a[i]-(i+1) for i in range(n)]
a.sort()
if n%2==0:
    print((sum(a[n//2:])-sum(a[0:n//2])))
else:
    print((sum(a[n//2+1:])-sum(a[0:n//2])))
# Original solution
import math

N = int(eval(input()))
A = list(map(int, input().split()))
# print(N, A)

_A = []
for i in range(len(A)):
    _A.append(A[i] - (i + 1))
_A.sort()
median = _A[math.floor(len(A) / 2)]

sadness = 0
for i in range(len(A)):
    sadness += abs(A[i] - (i + 1 + median))

print(sadness)


# Optimized solution
import math

N = int(eval(input()))
A = list(map(int, input().split()))
# print(N, A)

_A = [A[i] - (i + 1) for i in range(len(A))]
_A.sort()
median = _A[math.floor(len(A) / 2)]

sadness = 0
for i in range(len(A)):
    sadness += abs(A[i] - (i + 1 + median))

print(sadness)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
a = [a[i] - (i+1) for i in range(len(a))]

import statistics
b = int(statistics.median(a))
ans = sum([abs(i-b) for i in a])
print(ans)

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
a = [a[i] - (i+1) for i in range(len(a))]
b = sorted(a)[int(n/2)]
print((sum([abs(i-b) for i in a])))
# Original solution
import math
import statistics
n = int(eval(input()))
a = list(map(int,input().split()))
a = [aa-i-1 for i, aa in enumerate(a)]
answer = n*10**20
median_low = statistics.median_low(a)
median_high = statistics.median_high(a)

for m in (median_low,median_high):
  ans=0
  for aa in a:
    ans += abs(aa-m)
  answer = min(ans,answer)
print(answer)


# Optimized solution
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    difA = [0]*N

    for i in range(N):
        difA[i] = A[i]-(i+1)

    difA.sort()
    if N%2 == 0:
        g1 = difA[N//2]
        g2 = difA[N//2-1]
        a1 = 0
        a2 = 0
        for i in range(N):
            a1 += abs(difA[i]-g1)
            a2 += abs(difA[i]-g2)
        print((min(a1,a2)))
            
    else:
        g = difA[N//2]
        a = 0
        for i in range(N):
            a += abs(difA[i]-g)
        print(a)
    return


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
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()
# Original solution
import sys
import math
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
n=int(eval(input()))
A=list(map(int,input().split()))
SA=[0 for i in range(n)]
for i in range(n):
    SA[i]=A[i]-i-1
SA.sort()

if n%2==0:
    geta=(SA[n//2]+SA[n//2-1])//2
else:
    geta=SA[n//2]
ans=0
for i in range(n):
    ans+= abs(A[i]-(geta+i+1))
print(ans)


# Optimized solution
n=int(eval(input()))
A=list(map(int,input().split()))
if n==1:print((0));exit()
A=[A[i]-i-1 for i in range(n)]
B=sorted(A)

#print(B)

if n%2==1:
    d=B[n//2]
    print((sum([abs(A[i]-d) for i in range(n)])))
    exit()

ans=0
d=(B[n//2-1]+B[n//2])//2
print((sum([abs(A[i]-d) for i in range(n)])))
# Original solution
n = int(eval(input()))
nums = list(map(int, input().split()))

for i in range(n):
    nums[i] -= (i + 1)
    if i == 0:
        x = y =  nums[i]
    else:
        if nums[i] < x:
            x = nums[i]
        elif y < nums[i]:
            y = nums[i]

d = 0
for i in range(x, y):
    c = 0
    for j in range(n):
        c += abs(nums[j] - i)
    else:
        if d != 0 and d < c:
            print(d)
            break
        elif d == 0 and c == 0:
            print(d)
            break
        else:
            d = c
else:
    print(d)
            
    


# Optimized solution
n = int(eval(input()))
nums = list(map(int, input().split()))

for i in range(n):
    nums[i] -= (i + 1)

nums.sort()
        
if (n-1) % 2 != 0:
    m = n//2 - 1
else:
    m = (n-1)//2
    
a = sum(nums[m+1:]) - (n-m-1)*nums[m]
b = - sum(nums[0:m+1]) + (m+1)*nums[m]

print((a+b))
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))

A_sunuke = [a - (i+1) for (i,a) in enumerate(A)]

sunuke_cnts = set(A_sunuke) 

idx, cnt = 0, 0
for i in sunuke_cnts:
    a_cnt = A_sunuke.count(i)
    if cnt < a_cnt:
        cnt = a_cnt
        idx = i 

rtn = sum([abs(a - idx) for a in A_sunuke])
print(rtn)

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))

A_sunuke = sorted(a - (i+1) for (i,a) in enumerate(A))

center = A_sunuke[len(A) // 2]

rtn = sum([abs(a - center) for a in A_sunuke])
print(rtn)
# Original solution
n = int(eval(input()))
ary = list(map(int,input().split()))
a = []
ans = 0
for i in range(n):
    a += [ary[i] - (i+1)]
a.sort()
if n % 2 == 1:
    b = a[-(-n // 2)-1]
    for i in range(n):
        ans += abs(a[i] - b)
else:
    b = (a[n//2-1]+a[n//2])//2
    for i in range(n):
        ans += abs(a[i] - b)
print(ans)

# Optimized solution
n = int(eval(input()))
ary = sorted([j-(i+1) for i,j in enumerate(map(int,input().split()))])
if len(ary) % 2 == 0:
    a = (ary[len(ary)//2]+ary[len(ary)//2-1])//2
    ans = 0
    for i in ary:
        ans += abs(i - a)
else:
    a = ary[len(ary)//2]
    ans = 0
    for i in ary:
        ans += abs(i - a)
print(ans)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
max = max(A)
list = []
x = 0
for b in range(-max,max):
    for i in range(N):
        x = x + abs(A[i]-(b+i))
    list.append(x)
    x = 0
print((min(list)))

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
for i in range(N):
    A[i] = A[i] - i - 1
A = sorted(A)
medN = N//2

x = 0
for i in range(N):
    x = x + abs(A[i] - A[medN])
print(x)
# Original solution
N = int(eval(input()))
alist = list(map(int, input().split()))

blist = []
for i in range(N):
    blist.append(alist[i]-i-1)

blist.sort()
mid = blist[len(blist)//2]

ans = 0

for i in range(N):
    ans += abs(blist[i]-mid)

print(ans)


# Optimized solution
N = int(eval(input()))
alist = list(map(int, input().split()))

blist = []

for i in range(N):
    blist.append(alist[i]-i-1)

blist.sort()
mid = blist[N//2]

print((sum([abs(b-mid) for b in blist])))
# Original solution
N=int(eval(input()))
a=list (map(int,input().split()))
abs_list=[]
for b in range(-max(a),max(a)):
	c=0
	for i in range(N):
		c=abs(a[i]-(b+i+1))+c	
	abs_list.append(c)		
print((min(abs_list)))	

# Optimized solution
N=int(eval(input()))
a=list (map(int,input().split()))
abs_list=[]
c=0
for i in range(N):
	c=(a[i]-(i+1))
	abs_list.append(c)
abs_list.sort()
b=abs_list[int(N/2)]	
d=0
for i in range(N):
	d=abs(abs_list[i]-b)+d		
print(d)
# Original solution
# ABC102C - Linear Approximation (ARC100C)
from statistics import median_high, median_low


def main():
    n = int(eval(input()))
    A = tuple(map(int, input().rstrip().split()))
    A = tuple(j - i for i, j in enumerate(A, start=1))
    ans = float("inf")
    for b in range(median_low(A), median_high(A) + 1):
        ans = min(ans, sum(abs(a - b) for a in A))
    print(ans)


if __name__ == "__main__":
    main()

# Optimized solution
# ABC102C - Linear Approximation (ARC100C)
from statistics import median


def main():
    n = int(eval(input()))
    A = tuple(map(int, input().rstrip().split()))
    A = tuple(j - i for i, j in enumerate(A, start=1))
    b = median(A)
    ans = sum(abs(a - b) for a in A)
    print((int(ans)))


if __name__ == "__main__":
    main()
# Original solution
# ABC102C - Linear Approximation (ARC100C)
from statistics import median


def main():
    n = int(eval(input()))
    A = tuple(map(int, input().rstrip().split()))
    A = tuple(j - i for i, j in enumerate(A, start=1))
    b = median(A)
    ans = sum(abs(a - b) for a in A)
    print((int(ans)))


if __name__ == "__main__":
    main()

# Optimized solution
# ABC102C - Linear Approximation (ARC100C)
def main():
    n = int(eval(input()))
    A = tuple(map(int, input().rstrip().split()))
    A = sorted(j - i for i, j in enumerate(A, start=1))
    b = A[n // 2]
    ans = sum(abs(a - b) for a in A)
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
# ABC102 C - Linear Approximation
N = int(eval(input()))
A = list(map(int, input().split()))

bl = []
for i in range(N):
    bl.append(A[i] - (i+1))
bl.sort()
b = bl[N//2]

ans = 0
for i in range(N):
    ans += abs(A[i] - (b + (i+1)))
print(ans)

# Optimized solution
# ABC102 C - Linear Approximation
N = int(eval(input()))
A = list(map(int, input().split()))

bl = []
for i in range(N):
    bl.append(A[i] - (i+1))
bl.sort()
if N % 2 == 0:
    b = (bl[N//2-1] + bl[N//2]) // 2
else:
    b = bl[N//2]

ans = 0
for i in range(N):
    ans += abs(A[i] - (b + (i+1)))
print(ans)
# Original solution
from collections import Counter
N=int(eval(input()))
A=list(map(int,input().split()))
l=[]
n=1
for i in A:
    l.append(i-n)
    n+=1
c=Counter(l)
c=c.most_common(N)
ans_l=[]
for i in range(len(c)):
    b=c[i][0]
    ans=0
    for j in l:
        ans+=abs(j-b)
    ans_l.append(ans)
print((min(ans_l)))

# Optimized solution
#from collections import Counter
import math
N=int(eval(input()))
A=list(map(int,input().split()))
l=[]
n=1
for i in A:
    l.append(i-n)
    n+=1
l.sort()
#中央値
#切り捨て
c=int(math.floor(N/2))

ans_l=[]
ans=0
for j in l:
    ans+=abs(j-l[c])

print(ans)
# Original solution
#!/usr/bin/env python3
import math

def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    A = [A[i] - i - 1 for i in range(N)]
    A.sort()
    diff = A[(N-1)//2]
    print((sum([abs(a-diff) for a in A])))


if __name__ == "__main__":
    main()


# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
for i in range(N):
    A[i] -= i+1
A.sort()
b = A[(N-1)//2]

ans = 0
for i in range(N):
  ans += abs(A[i]-b)
print(ans)
# Original solution
import sys

N = int(eval(input()))
A_list = list(map(int, input().split()))

for i in range(N):
    A_list[i] = A_list[i] - i - 1

min_A = min(A_list)
max_A = max(A_list)

sadness = sys.maxsize
for b in range(min_A, max_A + 1):
    tmp_sadness = 0
    for A in A_list:
        tmp_sadness += abs(A - b)
    if(sadness > tmp_sadness):
        sadness = tmp_sadness

print(sadness)

# Optimized solution
N = int(eval(input()))
A_list = list(map(int, input().split()))

for i in range(N):
    A_list[i] = A_list[i] - i - 1

A_list = sorted(A_list)
if(N % 2 == 0):
    key = N // 2
else:
    key = (N - 1) // 2
b = A_list[key]
sadness = 0

for A in A_list:
    sadness += abs(A - b)

print(sadness)
# Original solution
from collections import Counter
n = int(eval(input()))
a = list(map(int, input().split()))
ans = -1
for i in range(n):
    a[i] = a[i] - i - 1
count = Counter(a)
for b in list(count.keys()):
    tmp = 0
    for i in range(n):
        tmp += abs(a[i] - b)
    if ans == -1 or tmp < ans:
        ans = tmp
print(ans)


# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
ans = 0
for i in range(n):
    a[i] = a[i] - i - 1
a.sort()
b = a[n // 2]
for i in range(n):
    ans += abs(a[i] - b)
print(ans)
# Original solution
import statistics
N = int(eval(input()))
A = list(map(int,input().rstrip().split()))

i = 0
kari =[]
for j in A:
    i +=1
    B = j-i
    kari.append(B)

sum = 0
for i in kari:
    sum+=abs(i-statistics.median(kari))
print((int(sum)))

# Optimized solution
import statistics
N = int(eval(input()))
A = input().rstrip().split()

i = 0
kari =[]
for j in A:
    i +=1
    B = int(j)-i
    kari.append(B)
b= statistics.median(kari)

sum = 0
for i in kari:
    sum+=abs(i-b)
print((int(sum)))
# Original solution
N = int(eval(input()))
A = list(map(int,input().split()))

ans = sum(A)

imin = min(A)-N
imax = max(A)+N

def calcAns(b):
        global A
        return sum([abs(A[i]-(b+i+1)) for i in range(N)])

while True:
        if imin == imax:
                break
        else:
                imid = imin + (imax - imin)//2
                tmp = calcAns(imid)
                if calcAns(imid+1)<tmp:
                        imin = imid+1
                elif calcAns(imid-1)<tmp:
                        imax = imid-1
                else:
                        imin = imid
                        imax = imid

print((calcAns(imin)))

# Optimized solution
N = int(eval(input()))
A = list(map(int,input().split()))

B = [A[i]-i-1 for i in range(N)]
B.sort()
if N%2:
        b = B[(N-1)//2]
else:
        b = (B[N//2]+B[N//2 - 1])//2

print((sum([abs(A[i]-b-i-1) for i in range(N)])))
# Original solution
n=int(eval(input()))
a=[int(i)-p-1 for p,i in enumerate(input().split())]
a.sort()
ans=0
for i in range(n):
    ans+=abs(a[i]-a[n//2])
print(ans)

# Optimized solution
n=int(eval(input()))
a=[int(i)-p for p,i in enumerate(input().split())]
a.sort()
ans=0
for i in a:
    ans+=abs(i-a[n//2])
print(ans)
# Original solution
def main():
    from statistics import median

    n, *a, = list(map(int, open(0).read().split()))
    a = [x - i for i, x in enumerate(a, 1)]
    a.sort()
    m = int(median(a))

    ans = sum([abs(x - m) for x in a])
    print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    n, *a, = list(map(int, open(0).read().split()))
    a = [x - i for i, x in enumerate(a, 1)]
    a.sort()
    if n % 2 == 0:
        ans = sum(a[n // 2:]) - sum(a[:n // 2])
    else:
        ans = sum(a[n // 2 + 1:]) - sum(a[:n // 2])
    print(ans)


if __name__ == '__main__':
    main()