CodeEff/ECCO huggingface dataset:
# Original solution
def abs(x):
    if x>0:
        return x
    else:
        return x * (-1)

if __name__ == '__main__':
    n = int(eval(input()))
    a = list(map(int, input().split()))
    a_mi = list(a[idx] - (idx + 1) for idx in range(len(a)))
    a_mi_sorted = sorted(a_mi)
    a_mi_sorted.append(a_mi_sorted[-1]+1)##bのrangeを取るため
    setAMI = sorted(list(set(a_mi_sorted)))

    ##print(a_mi_sorted)
    ans = float('inf')
    for i in range(n):
        #i番目までa[i]-bが0以下（absで負扱い）
        buf = sum(a_mi_sorted[:n]) - 2 * (sum(a_mi_sorted[:i+1]))
        for b in range(a_mi_sorted[i], setAMI[setAMI.index(a_mi_sorted[i])+1]):
            ans = min(ans, buf + (2 * (i + 1) - n) * b)
            ##print(i,b,ans)
    print(ans)

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
B = list(A_i - (i + 1) for i, A_i in enumerate(A))
B_sorted = sorted(B)

ans = []
##中央値のインデックスmを求める
if N % 2 == 1:
    ##Nが奇数: 中央値のインデックスを求める
    m = int((N - 1) / 2 + 1) - 1
    b = B_sorted[m]
    ans += [sum(abs(x - b) for x in B_sorted)]
else:
    ##Nが偶数: 中央値を計算する元になる2数のインデックスを求める
    for m in range(int(N / 2) - 1, int(N / 2) + 1):
        b = B_sorted[m]
        ans += [sum(abs(x - b) for x in B_sorted)]    
print((min(ans)))
# Original solution
from operator import sub

N = int(eval(input()))
a = tuple(map(int, input().split()))

b = list(map(sub, a, list(range(1, N + 1))))
b.sort()
mb = b[N // 2]
print((sum([abs(x - mb) for x in b])))


# Optimized solution
n = int(eval(input()))
*a, = list(map(int, input().split()))
a = [x - i for i, x in enumerate(a, 1)]

a.sort()
m = n // 2
b = a[m] if n % 2 == 1 else (a[m - 1] + a[m]) // 2

print((sum(abs(x - b) for x in a)))
# Original solution
# coding: utf-8

import statistics

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

for i,num in enumerate(a):
    a[i] = a[i] - (i + 1)

b = int(statistics.median(a))

res = 0
for i in a:
    res += abs(i - b)

print(res)


# Optimized solution
# coding: utf-8

import statistics

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

for i,num in enumerate(a):
    a[i] = a[i] - (i + 1)

b = statistics.median_low(a)

res = 0
for i in a:
    res += abs(i - b)

print(res)
# Original solution
n = int(eval(input()))
arr = list(map(int, input().split()))
A = sorted([a-i for i, a in enumerate(arr, 1)])
print((sum(abs(a-A[n//2]) for a in A)))

# Optimized solution
# マンハッタン距離の総和を最小化するときは、中央値を使うという典型がある。

N = int(eval(input()))
A = [int(a)-i for i, a in enumerate(input().split(), 1)]
A.sort()

b = A[N//2]
ans = sum([abs(a-b) for a in A])

print(ans)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))

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

s = sum(b)
m = int(s/n)
ans = float('inf')
if m<0:
  m = m-1
  for i in range(m, 1, 1):
    res = 0
    for j in range(n):
      res += abs(b[j]-i)
    ans = min(ans, res)
else:
  m = m+1
  for i in range(m+1):
    res = 0
    for j in range(n):
      res += abs(b[j]-i)
    ans = min(ans, res)
  
print(ans)

# Optimized solution
n = int(eval(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)]))))
# Original solution
# -*- coding: utf-8 -*-
INF = 10**10
n = int(eval(input()))
a = [int(_) - (i + 1) for i, _ in enumerate(input().split())]

grief = INF
for b in set(a):
    tmp = sum([abs(ai - b) for ai in a])
    if tmp < grief:
        bb = b
        grief = tmp

print(grief)


# Optimized solution
# -*- coding: utf-8 -*-
n = int(eval(input()))
a = [int(_) - (i + 1) for i, _ in enumerate(input().split())]

# INF = 10**10
# grief = INF
# for b in set(a):
#     tmp = sum([abs(ai - b) for ai in a])
#     if tmp < grief:
#         bb = b
#         grief = tmp

# print(grief)  # running time limit error

a.sort()
med = a[len(a) // 2]
grief = sum([abs(ai - med) for ai in a])
print(grief)
# Original solution
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

def check(m):
    sm = 0
    for i, a in enumerate(A):
        sm += abs(a - (m+i+1))
    return sm

# 三分探索
low = -INF
hi = INF
while low+2 < hi:
    m1 = (low*2+hi) // 3
    m2 = (low+hi*2) // 3
    res1 = check(m1)
    res2 = check(m2)
    # 今回は下に凸な関数なので値の小さい方に向かって狭めていく
    if res1 <= res2:
        hi = m2
    else:
        low = m1

ans = INF
for i in range(low, low+2):
    ans = min(ans, check(i))
print(ans)


# Optimized solution
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

# bをmとした時の悲しさ値
def check(m):
    sm = 0
    for i, a in enumerate(A):
        sm += abs(a - (m+i+1))
    return sm

# 三分探索
low = -10**9
hi = 10**9
while low+2 < hi:
    m1 = (low*2+hi) // 3
    m2 = (low+hi*2) // 3
    res1 = check(m1)
    res2 = check(m2)
    # 今回は下に凸な関数なので値の小さい方に向かって狭めていく
    if res1 <= res2:
        hi = m2
    else:
        low = m1

print((min(check(m1), check(m2))))
# Original solution
n = int(eval(input()))
a = list(map(int,input().split()))
ami = [a[i]-(i+1) for i in range(n)]
ami.sort()
# print(ami)
ans = 0
if n % 2 == 1:
    for i in range(n):
        ans += abs(ami[i]-ami[n//2])
else:
    cnt1 = 0
    cnt2 = 0
    for i in range(n):
        cnt1 += abs(ami[i]-ami[n//2])
        cnt2 += abs(ami[i]-ami[n//2-1])
    ans = min(cnt1,cnt2)
print(ans)


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

ans = 0
sub = []
for i, a in enumerate(A, 1):
    sub.append(a - i)
    ans += abs(a - i)

#print(sub)

#b = min(sub)
for b in range(min(sub), max(sub) + 1):
    #cand = 0
    cand = sum([abs(s - b) for s in sub])
    #for s in sub:
    #    cand += abs(s - b)
    ans = min(ans, cand)
print(ans)


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

for i, a in enumerate(A):
    A[i] = a - i

A = sorted(A)
b = A[len(A)//2]

ans = 0
for a in A:
    ans += abs(a - b)

print(ans)
# Original solution
import math
import statistics
N = int(eval(input()))
L = [i for i in map(int,input().split())]
Q = []
for i in range(len(L)):
  Q.append(L[i] - (i+1))
b = statistics.median(Q)
a = b - 1
c = b + 1
res = 0
res2 = 0
res3 = 0
for i in range(N):
  res += abs(L[i] - (i+1) - b)
  res2 += abs(L[i] - (i+1) - a)
  res3 += abs(L[i] - (i+1) - c)
print((int(min(res,res2,res3))))

# Optimized solution
import math
import statistics
N = int(eval(input()))
L = [i for i in map(int,input().split())]
Q = []
for i in range(len(L)):
  Q.append(L[i] - (i+1))
b = statistics.median(Q)
res = 0
for i in range(N):
  res += abs(L[i] - (i+1) - b)
print((int(res)))
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
for j in range(n):
    a[j] = a[j] - (j + 1)
a.sort()
asum = sum(a)
sadlist = [asum - n * a[0]]
for i in range(1, n+1):
    sad = asum - 2 * sum(a[:i])
    if i < n/2:
        sad = sad - (n - 2 * i) * a[i]
    elif i > n/2:
        sad = sad - (n - 2 * i) * a[i-1]
    else:
        pass
    sadlist.append(sad)
    if sad == 0 or sadlist[-2] < sad:
        break
print((min(sadlist)))

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
for j in range(n):
    a[j] = a[j] - (j + 1)
a.sort()
if n % 2 == 0:
    print((sum(a[int(n / 2):]) - sum(a[:int(n / 2)])))
else:
    print((sum(a[int((n + 1) / 2):]) - sum(a[:int((n - 1) / 2)])))
# Original solution
n = int(input())
a = list(map(int, input().split()))
for i in range(len(a)):
  a[i] -= (i+1)
min_total = sum([abs(t) for t in a])
for item in a:
  total = sum([abs(t-item) for t in a])
  if total < min_total:
    min_total = total

print(min_total)


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


b = sorted(a)
i = n // 2
what = b[i]
print((sum([abs(t - what) for t in b])))
# Original solution
N=int(eval(input()))
A=[a-i-1 for i,a in enumerate(map(int,input().split()))]
k=sum(A)//N+1
print((min(sum(abs(a-x)for a in A)for x in range(min(0,k-1),max(k+1,1)))))

# Optimized solution
N=int(eval(input()))//2
A=sorted(a-i-1 for i,a in enumerate(map(int,input().split())))
print((sum(abs(a-A[N])for a in A)))
# Original solution

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

#b_init = sum(A)//N - N*(N+1)//(2*N)
b_init = min(A) + N*(N+1)//(2*N)

while 1:
    #calculate sadness
    sadness = sum([abs(A[i] - (b_init+(i+1))) for i in range(N)])
    sadness_plus1 = sum([abs(A[i] - (b_init+1+(i+1))) for i in range(N)])
    sadness_minus1 = sum([abs(A[i] - (b_init-1+(i+1))) for i in range(N)])
    
    # initial equal ans
    if sadness <= sadness_plus1 and sadness <= sadness_minus1:
        print(sadness)
        break
    
    # right way
    if sadness_plus1 < sadness:
        sad_righter = sadness_plus1
        b = b_init
        while sad_righter <= sadness:
            b+=1
            sadness = sad_righter
            sad_righter = sum([abs(A[i] - (b+(i+1))) for i in range(N)])
    
        print(sadness)
        break
    
    # left way
    if sadness_minus1 < sadness:
        sad_lefter = sadness_minus1
        b = b_init
        while sad_lefter <= sadness:
            b-=1
            sadness = sad_lefter
            sad_lefter = sum([abs(A[i] - (b+(i+1))) for i in range(N)])
    
        print(sadness)
        break

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

if N==1:
    print((0))
else:
    B = [A[i]-i for i in range(N)]
    B.sort()
    b_pl = B[N//2]
    b_mn = B[N//2-1]
    
    sadness_pl = sum([abs(B[i]-b_pl) for i in range(N)])
    sadness_mn = sum([abs(B[i]-b_mn) for i in range(N)])
    
    print((min(sadness_pl, sadness_mn)))
# Original solution
N = int(eval(input()))
A = list(map(int,input().split()))

#N = 1
#A = [10**9]*N

A_n = [A[i-1] - i for i in range(1,N+1)]

A_n.sort()

if N%2 == 0:
    cent_max = A_n[N//2]
    cent_min = A_n[N//2-1]
else:
    cent = A_n[N//2]
    
if N%2 == 0:    
    sadness1 = sum([abs(A_n[i]-cent_min) for i in range(N)])
    sadness2 = sum([abs(A_n[i]-cent_max) for i in range(N)])
    sadness = min(sadness1, sadness2)

else:
    sadness = sum([abs(A_n[i]-cent) for i in range(N)])

print(sadness)

# Optimized solution
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return list(map(int, stdin.readline().split()))
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return list(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 = ni()
a = list(li())

amini = [ai-(i+1) for i,ai in enumerate(a)]
amini.sort()
b = amini[n//2]

print((sum([abs(ai-(b+i+1)) for i, ai in enumerate(a)])))
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
B = [A[i] - 1 - i for i in range(N)]
B.sort()
if N % 2 == 0:
    med = [B[int(N / 2) - 1], int((B[int(N / 2) - 1] + B[int(N / 2)]) / 2), B[int(N / 2)]]
else:
    med = [B[int((N + 1) / 2) - 1]]
ans = 10 ** 100
for b in med:
    S = 0
    for i in range(N):
        S += abs(B[i] - b)
    ans = min(ans, S)
print(ans)


# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
B = [A[i] - 1 - i for i in range(N)]
B.sort()
if N % 2 == 0:
    med = int((B[int(N / 2) - 1] + B[int(N / 2)]) / 2)
else:
    med = B[int((N + 1) / 2) - 1]
S = 0
for i in range(N):
    S += abs(B[i] - med)
print(S)
# Original solution
N=int(eval(input()))
A=list(map(int,input().split()))
total=0
total2=0
count=1
ans=0
for i in range(N):
    total+=A[i]
for i in range(1,N+1):
    total2+=i
while True:
    if total>total2:
        if total//N+total%N>total2:
            count+=(total-total//N+total%N)//N
            total=total//N+total%N
        else:
            break
    elif total<total2:
        if total+total*N<total2:
            count+=total
            total+=total*N
        else:
            break
    else:
        break

if total>total2:
    while True:
        total2 +=N
        count+=1
        if total2>=total:
            if abs(total2-total)<=abs(total2-total-N):
                break
            else:
                count-=1
                break
elif total<total2:
    while True:
        total2 -=N
        count-=1
        if total2<=total:
            if abs(total2-total)<=abs(total2-total-N):
                break
            else:
                count+=1
                break

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

print(ans)


# Optimized solution
N=int(eval(input()))
A=list(map(int,input().split()))
B=[]
total=0
for i in range(N):
    B.append(A[i]-i-1)

B.sort()
#print(B)
if len(A)%2==1:
    for i in range(N):
        total+=abs(A[i]-(B[len(B)//2]+i+1))
        #print(B[len(B)//2+1],total)
else:
    for i in range(N):
        total+=abs(A[i]-(B[len(B)//2]+i+1))
print(total)
# Original solution
import statistics
N = int(eval(input()))
A = [int(a)-(i+1) for i, a in enumerate(input().split())]
ans = float('inf')
medi = int(statistics.median(A))
for b in range(medi-1, medi+2):
  ans = min(ans, sum([abs(A[i]-b) for i in range(N)]))
print(ans)


# Optimized solution
def calc_sadness(b):
    ans = 0
    for a in A:
        ans += abs(a - b)
    return ans


N = int(eval(input()))
A = []
for idx, a in enumerate(map(int, input().split())):
    A.append(a - idx - 1)
A.sort()

if N % 2 == 0:
    b = [A[N // 2]]
else:
    b = [A[N // 2 - 1], A[N // 2]]

print((min(list(map(calc_sadness, b)))))
# Original solution
n=int(eval(input()))
a=[int(x) for x in input().split()]
s=[0 for x in range(n)]
 
for i in range(n):
  a[i] -= i+1
 
a.sort()
 
if n%2:
  s=0
  for i in range(n):
    s += abs(a[i]-a[n//2])
  print(s)
else:
  m=10**14
  for i in range(a[n//2-1],a[n//2]+1):
    s = 0
    for j in range(n):
      s += abs(a[j]-i)
    m = min(m,s)
  print(m)


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

def kei(b):
    ANS=0
    for i in range(N):
        ANS+=abs(A[i]-(b+i+1))
    return ANS

x=kei(A[0])
for i,j in enumerate(A):
    x=min(x,kei(j-i-1))
    
print(x)

# Optimized solution
N=int(eval(input()))
A=list(map(int,input().split()))
B=[None]*N

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

B.sort()

Left=0
Right=sum(B)-B[0]*N
ANS=Left+Right
#print(B)
#print(Left,Right)

for i in range(1,N):
    Left=Left+(B[i]-B[i-1])*i
    Right=Right-(B[i]-B[i-1])*(N-i)
    #print(Left,Right)

    if ANS>Left+Right:
        ANS=Left+Right

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

x = [A[i-1]-i for i in range(1, N+1)]
x.sort()
if len(x)%2==1:
    mid = x[len(x)//2]
    ans = 0
    for i in range(1, N+1):
        ans += abs(A[i-1]-(mid+i))
    print(ans)
else:
    mid1 = x[len(x)//2-1]
    mid2 = x[len(x)//2]
    ans1 = ans2 = 0
    for i in range(1, N+1):
        ans1 += abs(A[i-1]-(mid1+i))
        ans2 += abs(A[i-1]-(mid2+i))
    print((min(ans1, ans2)))

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

x = [A[i-1]-i for i in range(1, N+1)]
x.sort()

mid = x[len(x)//2]
ans = 0
for i in range(1, N+1):
    ans += abs(A[i-1]-(mid+i))
print(ans)
# Original solution
from functools import lru_cache
N = int(eval(input()))
A = list(map(int, input().split()))

def search_wb():
    sub = 1
    max_abs = abs(A[0] - sub)
    for a in A:
        if max_abs < abs(a - sub):
            max_abs = abs(a-sub)
        sub += 1
    return max_abs, -max_abs

@lru_cache(maxsize=None)
def sunuke(b):
    ret = 0
    sub = 1
    for a in A:
        ret += abs(a - (b+ sub))
        sub += 1
    return ret


maxb, minb= search_wb()

while abs(maxb - minb) > 1:
    mid = (maxb + minb) // 2
    #print("max{} min{} mid{}".format(maxb, minb, mid))
    if sunuke(mid) >  sunuke(mid + 1):
        minb = mid
    else:
        maxb = mid


mins = sunuke(minb)
maxs = sunuke(maxb)
if mins < maxs:
    print(mins)
else:
    print(maxs)



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

def sunuke(b):
    ret = 0
    sub = 1
    for a in A:
        ret += abs(a - (b+ sub))
        sub += 1
    return ret


B = []

sub = 1
for a in A:
    b = a - sub
    B.append(b)
    sub += 1

B.sort()
b1 = N // 2
if N < 3:
    print((sunuke(B[b1])))
    exit()

b2 = b1 + 1
b1_s = sunuke(B[b1])
b2_s = sunuke(B[b2])
if b1_s < b2_s:
    print(b1_s)
else:
    print(b2_s)
# Original solution
n = int(eval(input()))
li = list(map(int,input().split()))
for i in range(n):
  li[i] -= i+1
li.sort()
ans = 10**15
for i in range(n):
  ans = min(ans,i*li[i]-sum(li[:i])+sum(li[i:])-(n-i)*li[i])
print(ans)

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

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

dif = []
for idx, v in enumerate(A_list, 1):
    dif.append(v - idx)
b = 0
dif_num = sum(map(abs, ([x + b for x in dif])))
b = 1
dif_num_plus = sum(map(abs, ([x + b for x in dif])))
b = -1
dif_num_minus = sum(map(abs, ([x + b for x in dif])))
if dif_num <= dif_num_plus and dif_num < dif_num_minus:
    print(dif_num)
    sys.exit()

p_f = True
if dif_num_plus < dif_num_minus:
    p_f = True
    b = 1
else:
    p_f = False
    b = -1

dif_num = min(dif_num, dif_num_plus, dif_num_minus)

while True:
    if p_f:
        b += 1
    else:
        b -= 1
    l = list(([x + b for x in dif]))
    dif_num2 = sum(map(abs, ([x + b for x in dif])))
    if dif_num2 < dif_num:
        dif_num = dif_num2
    else:
        break
print(dif_num)


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

dif = []
for idx, v in enumerate(A_list, 1):
    dif.append(v - idx)

dif.sort()
if len(dif) % 2 == 1:
    b = dif[len(dif) // 2]
    print((sum(map(abs, ([x - b for x in dif])))))
else:
    b1 = dif[len(dif) // 2 - 1]
    b2 = dif[len(dif) // 2]
    print((min(sum(map(abs, ([x - b1 for x in dif]))),
              sum(map(abs, ([x - b2 for x in dif]))))))
# Original solution
import sys
input = sys.stdin.readline
n = int(eval(input()))
a = list(map(int,input().split()))
A = [a[i] - i - 1  for i in range(n)]
ave = sorted(A)[n//2] 
ans = sum([abs(A[i]-ave) for i in range(n)])
print(ans)

# Optimized solution
n = int(eval(input()))
a = list(map(int,input().split()))
A = [a[i] - i - 1  for i in range(n)]
ave = sorted(A)[n//2] 
ans = sum([abs(A[i]-ave) for i in range(n)])
print(ans)
# Original solution
from collections import Counter
N = int(eval(input()))
A = list(map(int,input().split()))
B = [a-i-1 for i,a in enumerate(A)]
ctr = Counter(B)
st = sorted(list(ctr.items()))

left = l_sum = 0
ans = r_sum = sum([(k - st[0][0])*v for k,v in st[1:]])

for (k1,v1),(k2,v2) in zip(st,st[1:]):
    left += v1
    l_sum += left * (k2-k1)
    right = N-left
    r_sum -= right * (k2-k1)
    ans = min(ans, l_sum + r_sum)
print(ans)

# Optimized solution
N = int(eval(input()))
A = list(map(int,input().split()))
B = [a-i-1 for i,a in enumerate(A)]
med = list(sorted(B))[N//2]
print((sum([abs(a-med) for a in B])))
# Original solution
def sadden_value(a, b):
    total = 0
    for i in range(0, len(a)):
        total += abs(a[i]-b-i-1)
    return total

n = int(eval(input()))
a = list(map(int, input().split()))
b = 1 - n
now = sadden_value(a, b)
while True:
    nex = sadden_value(a, b + 1)
    if now <= nex:
        print(now)
        break
    now = nex
    b += 1


# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
tmp = [a[x] - (x+1) for x in range(0,n)]
tmp.sort()
b = tmp[n // 2]
print((sum((abs(tmp[i] - b) for i in range(0,n)))))
# Original solution
def main():
	N = int(eval(input()))
	seq = list(map(int, input().split()))
	seq = [seq[i] - i - 1 for i in range(N)]
	def helper(b):
		return sum([abs(seq[i] - b) for i in range(N)])
	temp = []
	for i in range(N):
		temp.append(helper(seq[i]))
	print((min(temp)))
	return 0
main()

# Optimized solution
def main():
	N = int(eval(input()))
	seq = list(map(int, input().split()))
	seq = [seq[i] - i - 1 for i in range(N)]
	se = sorted(list(set(seq)))
	def helper(b):
		return sum([abs(seq[i] - b) for i in range(N)])
	L = 0
	R = len(se)
	while True:
		ind = (L + R) // 2
		temp = helper(se[ind])
		if helper(se[ind - 1]) > temp and temp > helper(se[ind + 1]):
			L = ind
		elif helper(se[ind - 1]) < temp:
			R = ind
		else:
			print(temp)
			return 0
main()
# Original solution
import bisect
n=int(eval(input()))
lists=list(map(int,input().split()))
uselists=[]
for _ in range(n):
    uselists.append(lists[_]-_-1)
uselist=sorted(uselists)
numbers=uselist[0]
while bisect.bisect_right(uselist,numbers)<n-bisect.bisect_right(uselist,numbers):
    numbers+=1
ans=0
for x in range(n):
    ans+=abs(uselist[x]-numbers)
print(ans)

# Optimized solution
n=int(eval(input()))
lists=list(map(int,input().split()))
uselists=[]
for _ in range(n):
    uselists.append(lists[_]-_-1)
uselist=sorted(uselists)
if n%2==0:
    num1=int(n/2-1)
    num2=int(n/2)
    numbers=min(uselist[num1],uselist[num2])
    
if n%2!=0:
    num1=int((n-1)/2)
    numbers=uselist[num1] 
ans=0
for x in range(n):
    ans+=abs(uselist[x]-numbers)
print(ans)
# Original solution
import sys
from statistics import median_low
inputs = sys.stdin.readlines()

n = int(inputs[0])
A = list(map(int, inputs[1].split()))

B = list([x[1]-x[0] for x in enumerate(A, 1)])
b = median_low(B)
C = list([abs(x-b) for x in B])
print((sum(C)))

# Optimized solution
import sys
from statistics import median_low
inputs = sys.stdin.readlines()

n = int(inputs[0])
A = list(map(int, inputs[1].split()))

B = list([x[1]-x[0] for x in enumerate(A, 1)])
b = median_low(B)
print((sum([abs(x-b) for x in B])))
# Original solution
# -*- coding: utf-8 -*-

from copy import deepcopy
n = int(eval(input()))
A = list(map(int, input().split()))
for i in range(len(A)):
    A[i] -= i + 1

ans = 10 ** 100
for a in A:
    B = deepcopy(A)
    for i in range(len(A)):
        B[i] -= a
    count = 0
    for b in B:
        count += abs(b)
    ans = min(ans, count)

print(ans)


# Optimized solution
# -*- coding: utf-8 -*-

n = int(eval(input()))
A = list(map(int, input().split()))
A = [A[i]-(i+1) for i in range(n)]
A.sort()

if n == 1:
    print((0))
    exit()

ans = 10**100
for i in [n//2-1, n//2]:
    ans = min(ans, sum([abs(A[j]-A[i]) for j in range(n)]))

print(ans)