CodeEff/ECCO huggingface dataset:
# Original solution
def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, = read_line(int)

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

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

min_sadness = float('inf')
b = None
for i in range(min(AA), max(AA) + 1):
    sadness = 0
    for a in AA:
        sadness += abs(a - i)

    if min_sadness > sadness:
        min_sadness = sadness
        b = i

print(min_sadness)


# Optimized solution
import math

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, = read_line(int)

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

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

AA.sort()

if len(AA) % 2 == 0:
    b = int(len(AA) / 2 - 1)
else:
    b = int((len(AA) - 1) / 2)

sadness = 0
for i, a in enumerate(A):
    # sadness1 += abs(a - (i + b1 + 1))
    # sadness2 += abs(a - (i + b2 + 1))
    sadness += abs(a - (i + AA[b] + 1))

print(sadness)
# Original solution
n = int(eval(input()))
H = list(map(int,input().split()))
h = []
for i in range(n):
    h.append(H[i]-(i+1))
h.sort()
M = h[n//2]
s = 0
for i in h:
    s += abs(i-M)
print(s)

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

for i in range(0,N):
	li[i] = li[i] - i -1
a = []
d = copy.copy(li)
while len(d) >= 3:
	d.remove(max(d))
	d.remove(min(d))
for i in range(min(d),max(d)+1):
	k = 0
	for j in range(N):
		k = k + abs(li[j]-i)
	a.append(k)
print((min(a)))

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

for i in range(1,N+1):
  a[i-1] -= i

b = statistics.median(a)
for i in range(N):
  ans += abs(a[i]-b)
print((int(ans)))

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

p = [v - (i + 1) for i, v in enumerate(A)]

res = sum(map(abs, [i - statistics.median(p) for i in p]))
print((int(res)))

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

p = sorted([v - (i + 1) for i, v in enumerate(A)])

if len(p) >= 3:
    res = min(sum(map(abs, [i - p[N//2] for i in p])), sum(map(abs, [i - p[N//2-1] for i in p])), sum(map(abs, [i - p[N//2+1] for i in p])))
elif len(p) >= 2:
    res = min(sum(map(abs, [i - p[0] for i in p])), sum(map(abs, [i - p[1] for i in p])))
else:
    res = 0
print((int(res)))
# Original solution
N=int(eval(input()))
A=list(map(int,input().split()))
B=[A[i]-(i+1) for i in range(N)]

B.sort()
ans=float('inf')
for i in range(B[0],B[N-1]+1):
  val=0
  for j in range(N):
    val+=abs(B[j]-i)
  ans=min(ans,val)
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.sort()
b=B[N//2]
ans=0
for i in range(N):
  ans+=abs(B[i]-b)
print(ans)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
t = list(sorted(a[i] - (i + 1) for i in range(n)))
b = t[len(t) // 2]
print((sum(abs(a[i] - (b + i + 1)) for i in range(n))))


# Optimized solution
from sys import stdin
n, *a = list(map(int, stdin.read().split()))
t = list(sorted(a[i] - (i + 1) for i in range(n)))
b = t[len(t) // 2]
print((sum(abs(a[i] - (b + i + 1)) for i in range(n))))
# Original solution
n=int(eval(input()))
a=[int(i) for i in input().split()]
b=n*(-1)
k=0
ans=0

def sunuke(b):
    ans=0
    for i in range(n):
        ans+=abs(a[i]-b-i-1) 
    return ans 
        
while k<1:
    if sunuke(b)<sunuke(b+1):
        print((sunuke(b)))
        k=1
    else:
        b+=1

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

for i in range(n):
    a[i]-=i+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
def f(x,i,n):
    sadness = 0
    for j in range(n):
        sadness += abs(x[j]-i)
    return(sadness)
N = int(eval(input()))
H = [int(i) for i in input().split()]
for i in range(N):
    H[i] -= i+1
H = sorted(H)
D = f(H,1,N)

for i in range(N):
    D = min(D,f(H,H[i],N))
print(D)


# Optimized solution
def f(x,i,n):
    sadness = 0
    for j in range(n):
        sadness += abs(x[j]-i)
    return(sadness)
N = int(eval(input()))
H = [int(i) for i in input().split()]
for i in range(N):
    H[i] -= i+1
H = sorted(H)
k = N // 2
if N == 1 :
    print((0))
else:
    print((f(H,H[k],N)))
# Original solution
from statistics import median_low

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

A = [v-i-1 for i,v in enumerate(A)]
x = median_low(A)

print((sum(abs(v - x) for v in A)))


# Optimized solution
def median_low(A):
    A.sort()
    b=A
    n = len(A)
    if n%2==1:
        med =b[n//2]
    else:
        x=b[n//2-1]
        y=b[n//2]
        med=(x+y)/2
        if med!=int(med):
            med=x
        else:
            med=int(med)
    return med


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

A = [v-i-1 for i,v in enumerate(A)]
x = median_low(A)

print((sum(abs(v - x) for v in A)))
# Original solution
N = int(eval(input()))
A = list(map(int,input().split()))
B = list(range(-N//2 + 1, max(A)))
S = list()
s = 0

for b in B:
    for idx, it in enumerate(A):
        s += abs(it - (b+idx))
    S.append(s)
    s = 0
    
print((min(S)))

# Optimized solution
N = int(eval(input()))
A = list(map(int,input().split()))
B = [it - (idx + 1) for idx, it in enumerate(A)]
S = []

B.sort()
if N%2 == 1:
    b = B[(N-1)//2]
else:
    b = (B[(N-1)//2] + B[(N-1)//2 + 1]) // 2
    
S = sum([abs(i-b) for i in B])
    
print(S)
# Original solution
n=int(eval(input()))
lst=list(map(int,input().split()))
minu = min(lst)
maxi = max(lst)
sad = 1000000000000
for i in range(minu-maxi, maxi+minu+1):
  temp = 0
  for j in range(n):
    temp += abs(lst[j] - i - (j+1))
  if temp < sad:
    sad = temp
print(sad)

# Optimized solution
n=int(eval(input()))
lst=list(map(int,input().split()))
for i in range(n):
  lst[i] = lst[i] - 1 - i
lst.sort()
b=lst[n//2]
print((sum([abs(b - lst[j]) for j in range(n)])))
# Original solution
def absFunc(A_, b):
    result = 0
    for a_ in A_:
        result += abs(a_ - b)
    return result
    
eval(input())
A = list(map(int, input().split()))
A_ = []

for i, a in enumerate(A):
    A_.append(a - i - 1)

b = 0
result_o = absFunc(A_, b)
result_n = 0

while True:
    b += 1
    result_n = absFunc(A_, b)
    
    if result_n < result_o:
        result_o = result_n
        continue
    break

b = 0
while True:
    b -= 1
    result_n = absFunc(A_, b)
    
    if result_n < result_o:
        result_o = result_n
        continue
    break

print(result_o)


# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
A_ = []
result = 0

for i, a in enumerate(A):
    A_.append(a - i - 1)

b = sorted(A_)[N//2]

for a_ in A_:
    result += abs(a_ - b)

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

Bs = set()
for i in range(N):
    Bs.add(A[i] - (i+1))

mins = sum(A)
for b in Bs:
    s = 0
    for i, a in enumerate(A):
        s += abs(a - (b+i+1))
    mins = min(mins, s)
print(mins)

# Optimized solution
N = int(eval(input()))
A = tuple(map(int, input().split()))
B = [a-(i+1) for i, a in enumerate(A)]
B = sorted(B)
b = B[len(B) // 2]
s = 0
for b_ in B:
    s += abs(b_ - b)
print(s)
# Original solution
N = int(eval(input()))
A = [int(i) for i in input().split()]

bmax = max(A)
bmin = min(A)-N

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

def binSearch(bmin,bmax):
    b = (bmin+bmax)//2
    sadb = getSadNess(b)
    sadm = getSadNess(b-1)
    sadp = getSadNess(b+1)
    if sadb<=sadp and sadb<=sadm:
        return sadb
    elif sadb>sadm:
        return binSearch(bmin,b-1)
    else:
        return binSearch(b+1,bmax)
    
print((binSearch(bmin,bmax)))

# Optimized solution
N = int(eval(input()))
A = [int(i) for i in input().split()]
B = [A[i]-i-1 for i in range(N)]
B.sort()
b = N//2
ans = sum([abs(B[i]-B[b]) for i in range(N)])
print(ans)
# Original solution

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

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

def right(N, A):
    X = [0] * N
    for i in range(N):
        X[i] = abs(A[i] - (i+1))

    return max(X)

r = right(N, A)
#print(r)

ans = float('inf')
for b in range(-r, r+1):
    c = 0
    for i in range(1, N+1):
        c += abs(A[i-1] - (b+i))

    ans = min(ans, c)

print(ans)

# Optimized solution


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

N = int(eval(input()))
A = list(map(int, input().split()))
a = [0] * len(A)

# bの値は中央値
# https://qiita.com/Noiri/items/291ae9bf4a2eacab6f5f
for i in range(N):
    a[i] = A[i]-i-1

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

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

print(ans)
# Original solution
class Solver(object):
    def __init__(self):
        self.n = int(eval(input()))
        self.a_s = list(map(int, input().split(" ")))
        self._sadness = {}

    def do_solve(self, b, length):
        b = 0
        current = self.sadness(b)
        left = self.sadness(b-1)
        right = self.sadness(b+1)
        while True:
            # print("{}: {} {} {}".format(b, left, current, right))
            if (left >= current) and (right >= current):
                return b
            elif left < right:  # go left
                b -= 1
            else:  # go right
                b += 1
            current = self.sadness(b)
            left = self.sadness(b-1)
            right = self.sadness(b+1)

    def solve(self):
        b = self.a_s[0] - 1
        for i in range(1, self.n+1):
            b = self.do_solve(b, i)
        print((self.sadness(b)))
        
    def sadness(self, b):
        if b not in self._sadness:
            self._sadness[b] = sum(abs(self.a_s[i] - (b+i+1)) for i in range(self.n))
        return self._sadness[b]


if __name__ == "__main__":
    s = Solver()
    s.solve()

# Optimized solution
class Solver(object):
    def __init__(self):
        self.n = int(eval(input()))
        self.a_s = list(map(int, input().split(" ")))
        self._sadness = {}

    def solve(self):
        array = self.a_s.copy()
        for i in range(self.n):
            array[i] -= i + 1
        array.sort()
        b = array[len(array) // 2]
        print((self.sadness(b)))
        
    def sadness(self, b):
        if b not in self._sadness:
            self._sadness[b] = sum(abs(self.a_s[i] - (b+i+1)) for i in range(self.n))
        return self._sadness[b]


if __name__ == "__main__":
    s = Solver()
    s.solve()
# Original solution
import sys
N = int(eval(input()))
lists = [int(i) for i in input().split()]
sok = sys.maxsize
list2 = [xx - max(lists) for xx in range (2 * max(lists) + 1)]
for b in list2:
    kanashi = 0
    i = 1
    for x in lists:
        kanashi += abs(x - (b + i))
        i += 1
    if (kanashi < sok):
        sok = kanashi
print(sok)


# Optimized solution
def med(data):
    N = len(data)
    data.sort()
    if N % 2 == 0:
        median1 = N/2
        median2 = N/2 + 1
        median1 = int(median1) - 1
        median2 = int(median2) - 1
        median = (data[median1] + data[median2]) / 2
        return median
    else:
        median = (N + 1) / 2
        median = int(median) - 1
        median = data[median]
        return median

import sys
N = int(eval(input()))
lists = [int(i) for i in input().split()]
sok = sys.maxsize
list2 = [x - j - 1 for j, x in enumerate(lists)]
b = med(list2)
kanashi = 0
for xx in list2:
    kanashi += abs(xx - b)
print((int(kanashi)))
# Original solution
N = int(eval(input()))
B = [a - i -1 for i, a in enumerate(list(map(int, input().split())))]

b = sorted(B)[(N-1)//2]

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

print(ans)

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

b = sorted(B)[(N-1)//2]

print((sum([abs(B[i] - b) for i in range(N)])))
# Original solution
N=eval(input())
N=int(N)
M=list(map(int,input().split()))

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


min=10**14
for i in range(N):
  sum=0
  p=M[i]
  for j in range(N):
      sum=sum+abs(M[j]-p)
  if sum<min:
    min=sum

print(min)



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

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

M.sort()

if N%2==0:
  p=int((M[int(N/2)-1]+M[int(N/2)])/2)
else:
  p=M[int((N+1)/2)-1] 

sum=0
for i in range(N):
  sum=sum+abs(M[i]-p)

  
print(sum)
# Original solution
import copy

def get_diff(value, array):
  diff = 0
  for i in array:
    diff += abs(value - i)
  return diff

length = int(eval(input()))
inp = input().split(' ')
A = []
for i in range(0, length):
  A.append(int(inp[i]) - i - 1)

initial = int(sum(A)/len(A))
initial_diff = int(get_diff(initial, A))

end_flag = 1
initial_plus = copy.copy(initial)
max_diff = copy.copy(initial_diff)
# print(A)
# print(initial)
# print(initial_diff)

while end_flag == 1:
  initial_plus += 1
  if get_diff(initial_plus, A) < max_diff:
    max_diff = get_diff(initial_plus, A)
    print(max_diff)
  else:
    end_flag = 0

plus_max_diff = max_diff

end_flag = 1
initial_plus = copy.copy(initial)
max_diff = copy.copy(initial_diff)

while end_flag == 1:
  initial_plus -= 1
  if get_diff(initial_plus, A) < max_diff:
    max_diff = get_diff(initial_plus, A)
  else:
    end_flag = 0
    
minus_max_diff = max_diff

print((min(plus_max_diff, initial_diff, minus_max_diff)))

# Optimized solution
"""
中央値を求めれば良い.
"""
def get_diff(value, array):
  diff = 0
  for i in array:
    diff += abs(value - i)
  return diff

length = int(eval(input()))
inp = input().split(' ')
A = []
for i in range(0, length):
  A.append(int(inp[i]) - i - 1)

A.sort()

# print(A)

# odd numbers
if len(A) % 2 == 1:
  center_number = A[len(A) // 2]
else:
  center_number = int(A[len(A) // 2 ] + A[len(A) // 2]) / 2

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

a.sort()
w=10**9
for j in range(a[0],a[n-1]+1):
    s=0

    for k in range(n):
        s+=abs(a[k]-j)
    if s<w :
        w=s
print(w)

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

a.sort()

#bはaの最小から最大まで
x=0
z=n-1
y=(x+z)//2
while z!=x:
    s1=0
    s2=0
    for k in range(n):
        s1+=abs(a[k]-a[y])
    for k in range(n):
        s2+=abs(a[k]-a[y+1])
    if s1<s2 :
        z=y
        y=(x+z)//2
    elif s1==s2:
        x=y
        z=y
    else:
        x=y+1
        y=(x+z)//2
#x=y=zとなっている
s=0
for k in range(n):
    s+=abs(a[k]-a[y])

print(s)
# Original solution
N = int(eval(input()))
A_list = list(map(int, input().split()))
A_sub_list = [a - (i + 1) for i, a in enumerate(A_list)]
b_max = max(A_sub_list)
b_min = min(A_sub_list)
min_s = pow(10, 10)
for b in range(b_min, b_max + 1):
    s = sum([abs(a - b) for a in A_sub_list])
    min_s = min(min_s, s)
print(min_s)

# Optimized solution
N = int(eval(input()))
A_list = list(map(int, input().split()))
B_list = [a - (i + 1) for i, a in enumerate(A_list)]
B_list.sort()
b = B_list[int(len(B_list) / 2)]
s = sum([abs(B - b) for B in B_list])
print(s)
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
dp=[0]*n
for i in range(n):
  dp[i]=a[i]-i
dp.sort()
ans=0
for j in range(n):
  ans+=abs(dp[j]-dp[n//2])
print(ans)


# Optimized solution
n=int(eval(input()))
a=list(map(int,input().split()))
dp=[0]*n
for i in range(n):
  dp[i]=a[i]-i
dp.sort()
print((sum(abs(x-dp[n//2]) for x in dp)))
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
a2 = []
for i in range(n):
    a2.append(a[i]-i-1)
a3 = []
for i in range(n):
    m = min(a2)
    a3.append(m)
    a2.remove(m)
if n % 2 == 0:
    b = (a3[n//2-1]+a3[n//2])//2
else:
    b = a3[n//2]
s = 0
for i in a3:
    s += abs(i-b)
print(s)

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
a2 = []
mi = 0
for i in range(n):
    a2.append(a[i]-i-1)
a3 = sorted(a2)
if n % 2 == 0:
    b = (a3[n//2-1]+a3[n//2])//2
else:
    b = a3[n//2]
s = 0
for i in a3:
    s += abs(i-b)
print(s)
# Original solution
n = int(eval(input()))
aa = list(map(int,input().split()))

a = []
for i in range(n):
    a.append(aa[i]-(i+1))
    
b = {}
for i in a:
    if i in b:
        b[i] += 1
    else:
        b.update({i:1})
        
ans_l = []
for k in list(b.keys()):
    counts = 0
    for k_, val in list(b.items()):
        counts += (abs(k - k_)) * val
    ans_l.append(counts)
    
print((min(ans_l)))

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

a = []
for i in range(n):
    a.append(aa[i]-(i+1))
b = list(sorted(a))

ans = 0

for i in range(n//2):
    ans += b[-i-1] - b[i]
print(ans)
# Original solution
N = int(eval(input()))
A = [int(i) for i in input().split()]
A = [A[_] - (_ + 1) for _ in range(N)]
AA = sorted(A)
ans = 0
ans1 = 0
center = N // 2
num = AA[center]

if N % 2 != 0:
    for i in range(N):
        ans += abs(AA[i] - num)
    print(ans)
else:
    center = len(AA) // 2
    for i in range(N):
        ans += abs(AA[i]- num)
        ans1 += abs(AA[i]-(AA[center-1]))
    print((min(ans, ans1)))

# Optimized solution
N = int(eval(input()))
A = [int(i) for i in input().split()]
for i in range(N):
    A[i] -= (i+1)

A.sort()

if N % 2 != 0:
    num = A[N//2]
    A = [abs(i - num) for i in A]
    print((sum(A)))
else:
    num1 = A[N//2]
    num2 = num1 -1
    A1 = [abs(i - num1) for i in A]
    A2 = [abs(i - num2) for i in A]
    print((min(sum(A1), sum(A2))))
# Original solution
n = int(eval(input()))
a = [int(_) for _ in input().split()]
i = 1
result = 0
result2=[]
for b in range(abs(max(a))*-1,abs(max(a))):
  for data in a:
    result = result + abs(data - b -i)
    i += 1
  result2.append(result)
  result = 0
  i = 0

print((min(result2)))

# Optimized solution
n = int(eval(input()))
a = [int(_) for _ in input().split()]
B = [ av - i  for i, av in enumerate(a,1)]
B.sort()

middle = n //2
b = B[middle]

result = 0
for a2 in B:
  result = result + abs(a2 -b)
print(result)
# Original solution
n = int(eval(input()))
A = list(map(int, input().split()))
B = []
for i in range(n): B.append(A[i] - (i+1))
B.sort()
r = B[n//2] # median right
l = B[n//2] if n%2 else B[n//2-1] # median left
# print(n,A)
# print(B)
# print(l,r)
ans_l = 0
ans_r = 0
for bi in B:
    ans_l += abs(bi-l)
    ans_r += abs(bi-r)
print((min([ans_l, ans_r])))


# Optimized solution
n = int(eval(input()))
B = list(a-i for i,a in zip(list(range(1,n+1)), list(map(int,input().split()))))
B.sort()
l = r = B[n//2] # median left, right
if n%2 == 0: l -= 1 # left fix
ans_l, ans_r = 0, 0
for bi in B:
    ans_l += abs(bi-l)
    ans_r += abs(bi-r)
print((min([ans_l, ans_r])))
# Original solution
n = int(eval(input()))
B = list(a-i for i,a in zip(list(range(1,n+1)), list(map(int,input().split()))))
B.sort()
l = r = B[n//2] # median left, right
if n%2 == 0: l -= 1 # left fix
ans_l, ans_r = 0, 0
for bi in B:
    ans_l += abs(bi-l)
    ans_r += abs(bi-r)
print((min([ans_l, ans_r])))


# Optimized solution
n = int(eval(input()))
B = list(a-i-1 for i,a in zip(list(range(n)), list(map(int,input().split()))))
B.sort()
ans = sum(B[n//2 + (n%2) :]) - sum(B[: n//2]) # sum(median left) - sum(median right)
print(ans)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))

aa = sorted([a[i]-i-1 for i in range(n)])
aa = [_-min(aa) for _ in aa]

if n % 2 == 1:
    idx = n // 2
    res = 0
    for ai in aa[:idx]:
        res += aa[idx] - ai
    for ai in aa[idx:]:
        res += ai - aa[idx]

else:
    idx_1 = n // 2 -1
    idx_2 = n // 2
    res_1 = 0
    for ai in aa[:idx_1]:
        res_1 += aa[idx_1] - ai
    for ai in aa[idx_1:]:
        res_1 += ai - aa[idx_1]
    res_2 = 0
    for ai in aa[:idx_2]:
        res_2 += aa[idx_2] - ai
    for ai in aa[idx_2:]:
        res_2 += ai - aa[idx_2]
    res = min(res_1, res_2)

print(res)

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

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

if n % 2 == 1:
    idx = n // 2
    res = 0
    for ai in aa[:idx]:
        res += aa[idx] - ai
    for ai in aa[idx:]:
        res += ai - aa[idx]

else:
    idx_1 = n // 2 -1
    idx_2 = n // 2
    res_1 = 0
    for ai in aa[:idx_1]:
        res_1 += aa[idx_1] - ai
    for ai in aa[idx_1:]:
        res_1 += ai - aa[idx_1]
    res_2 = 0
    for ai in aa[:idx_2]:
        res_2 += aa[idx_2] - ai
    for ai in aa[idx_2:]:
        res_2 += ai - aa[idx_2]
    res = min(res_1, res_2)

print(res)
# Original solution
N=int(eval(input()))
a=list(map(int,input().split()))
a=[a[i]-i for i in range(N)]
from statistics import median
print((sum([abs(b-int(median(a))) for b in a])))

# Optimized solution
N=int(eval(input()))
a=list(map(int,input().split()))
a=[a[i]-i for i in range(N)]
from statistics import median
m=int(median(a))
print((sum([abs(b-m) for b in a])))
# Original solution
N = int(eval(input()))
A = list(map(int,input().split()))
for x in range(N):
    A[x] -= (x+1)

sorted_A = sorted(A)

if len(A) == 1:
    ans = 0
elif N % 2 == 1 and not len(A) == 1 :
    ans = sum([abs(x-sorted_A[N//2+2]) for x in A])
    for x in range(sorted_A[N//2],sorted_A[N//2+2]):
        y = sum([abs(z -x) for z in A])
        if ans > y :
            ans = y
else:
    ans = sum([abs(x-sorted_A[N//2+1]) for x in A])
    for x in range(sorted_A[N//2],sorted_A[N//2+1]):
        y = sum([abs(z -x) for z in A])
        if ans > y :
            ans = y
    
print(ans)

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

sorted_A = sorted(A)

if len(A) == 1:
    ans = 0
else:
    ans = sum([abs(x-sorted_A[N//2]) for x in A])

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

pro_list = [a_list[i-1] - i for i in range(1, n+1)]
ave = int(statistics.mean(pro_list))

b_list = [ave - 1 for i in range(5000)] + [ave + i for i in range(5000)]

ans = [sum([abs(pro-b)for pro in pro_list]) for b in b_list]
print((min(ans)))

# Optimized solution
import statistics
n = int(eval(input()))
a_list = list(map(int, input().split()))

pro_list = [a_list[i-1] - i for i in range(1, n+1)]
ave = int(statistics.mean(pro_list))
med = int(statistics.median(pro_list))
b_list = [ave - 1 for i in range(10)] + [ave + i for i in range(10)]
b_list += [med - 1 for i in range(10)] + [med + i for i in range(10)]

ans = [sum([abs(pro-b)for pro in pro_list]) for b in b_list]
print((min(ans)))
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
c=[a[i]-i-1 for i in range(n)]
cum_c=[0]*n
c.sort()
cum_c[0]=c[0]
for i in range(1,n):
  cum_c[i]=cum_c[i-1]+c[i]
ans=min(cum_c[n-1]-n*c[0],n*c[n-1]-cum_c[n-1])
for i in range(1,n):
  for b in range(c[i-1],c[i]+1):
    ans=min(ans,cum_c[n-1]-2*cum_c[i-1]+(2*i-n)*b)
print(ans)

# Optimized solution
n=int(eval(input()))
a=list(map(int,input().split()))
c=[a[i]-i-1 for i in range(n)]
cum_c=[0]*n
c.sort()
cum_c[0]=c[0]
for i in range(1,n):
  cum_c[i]=cum_c[i-1]+c[i]
ans=min(cum_c[n-1]-n*c[0],n*c[n-1]-cum_c[n-1])
for i in range(1,n):
  ans=min(ans,cum_c[n-1]-2*cum_c[i-1]+(2*i-n)*c[i-1])
  ans=min(ans,cum_c[n-1]-2*cum_c[i-1]+(2*i-n)*c[i])
print(ans)