CodeEff/ECCO huggingface dataset:
# Original solution
n = int(eval(input()))
l = list(map(int,input().split()))
l = list(l[i]-i for i in range(n))
import statistics as st
m = int(st.median(l))
print((sum(abs(m-i) for i in l)))

# Optimized solution
n=int(eval(input()))
l=list(map(int,input().split()))
l=sorted(l[i]-i for i in range(n))
print((sum(abs(i-l[n//2]) for i in l)))
# Original solution
N = int(eval(input()))
A = [int(i) for i in input().split()]
nums = []
total = 0
for i in range(N):
    A[i] = A[i] - (i+1)
    if A[i] not in nums:
        nums.append(A[i])
    total = total + A[i]

avg = (total/N)

'''
up = 0
down = 0
for i in range(N):
    if avg >= A[i]:
        down = down + 1
    else:
        up = up + 1


if down > up:
    if avg < 0:
        avg = int(avg) - 1
    else:
        avg = int(avg)
else:
    avg = round(avg)



sad = 0
for i in range(N):
    sad = sad + abs(A[i]-avg)
'''

l = [int(avg)-1,int(avg),int(avg) + 1]
sad = []
for i in range(3):
    tmp = 0
    for j in range(N):
        tmp = tmp + abs(A[j]-l[i])
    sad.append(tmp)

for i in range(len(nums)):
    tmp = 0
    for j in range(N):
        tmp = tmp + abs(A[j]-nums[i])
    sad.append(tmp)
    
print((min(sad)))

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

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

A.sort()

medium = A[int(N/2)]

s = 0
for i in range(N):
    s = s + abs(A[i]-medium)

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

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

def f(x):
    sum = 0
    for i in alta:
        sum += abs(x - i)
    return sum

left, right = 0, max(alta)
while abs(right - left) > 3:
    mid1 = (right * 2 + left) // 3 + 1
    mid2 = (right + left * 2) // 3
    if f(mid1) >= f(mid2):
        # 上限を下げる（最小値をとるxはもうちょい下めの数だな）
        right = mid1
    else:
        # 下限を上げる（最小値をとるxはもうちょい上めの数だな）
        left = mid2
ans = float('inf')
for i in range(left, right + 1):
    ans = min(ans, f(i))
print(ans)

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
alta = []
for i in range(N):
    alta.append(A[i] - (i + 1))
# 最小値を0に揃えないとバグる
plus = min(alta)
for i in range(N):
    alta[i] -= plus

def f(x):
    sum = 0
    for i in alta:
        sum += abs(x - i)
    return sum

# 極値があるので三分探索使う
left, right = 0, max(alta)
# 答えが整数になる問題の場合このrightとleftの幅を3未満にするとバグる
while abs(right - left) > 3:
    mid1 = (right * 2 + left) // 3 + 1
    mid2 = (right + left * 2) // 3
    if f(mid1) >= f(mid2):
        # 上限を下げる（最小値をとるxはもうちょい下めの数だな）
        right = mid1
    else:
        # 下限を上げる（最小値をとるxはもうちょい上めの数だな）
        left = mid2
ans = float('inf')
for i in range(left, right + 1):
    ans = min(ans, f(i))
print(ans)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))

#y seppen wo motomeru

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

m=min(I)
M=max(I)

opp=10**100
for i in range(m, M+1):
    #print(i)
    temp=sum([abs(val-i) for val in I])
    if temp<opp:
        opp=temp
print(opp)

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

def func(b):
    return sum([abs(val - b) for val in I])

#y seppen wo motomeru

I=[A[i]-i-1 for i in range(N)]
I.sort()

if N % 2 ==1:
    print((func(I[N//2])))
else:
    print((func(I[N//2])))
# Original solution

def calc(A, b):
    retval = 0
    for a in A:
        retval += abs(a - b)
    return retval


def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    for i in range(N):
        A[i] -= (i + 1)

    left = min(A)
    right = max(A)

    while left < right:
        c1 = (left + left + right) // 3       # floor
        c2 = -(-(left + right + right) // 3)  # ceil
        if calc(A, c1) <= calc(A, c2):
            right = c2 - 1
        else:
            left = c1 + 1
    print((calc(A, left)))


if __name__ == "__main__":
    main()


# Optimized solution

def calc(A, b):
    retval = 0
    for a in A:
        retval += abs(a - b)
    return retval


def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    for i in range(N):
        A[i] -= (i + 1)

    print((calc(A, sorted(A)[(N)//2])))

#    left = min(A)
#    right = max(A)
#
#    while left < right:
#        c1 = (left + left + right) // 3       # floor
#        c2 = -(-(left + right + right) // 3)  # ceil
#        if calc(A, c1) <= calc(A, c2):
#            right = c2 - 1
#        else:
#            left = c1 + 1
#    print(calc(A, left))


if __name__ == "__main__":
    main()
# Original solution
N=int(input().strip())
A=list(map(int, input().strip().split()))
A_posi=[]
A_nega=[]
for i in range(N):
    A[i]=A[i]-(i+1)
    if A[i]<0:
        A_nega.append(A[i]*(-1))
    elif A[i]>0:
        A_posi.append(A[i])
sm=sum(abs(i) for i in A)

A_tgt=A_nega if len(A_nega)>len(A_posi) else A_posi
A_tgt=sorted(A_tgt)
b=0
max_diff=0
if len(A_tgt):
    while b<A_tgt[-1]:
        b+=1
        diff=0
        for i,a in enumerate(A_tgt):
            if a>=b:
                diff+=(len(A_tgt)-i)*b
                break
            else:
                diff+=2*a-b
        diff-=(N-len(A_tgt))*b
        if diff >max_diff:
            max_diff=diff
        else:
            break
print((sm-max_diff))

# Optimized solution
N=int(input().strip())
A=list(map(int, input().strip().split()))
A_posi=[]
A_nega=[]
for i in range(N):
    A[i]=A[i]-(i+1)
    if A[i]<0:
        A_nega.append(A[i]*(-1))
    elif A[i]>0:
        A_posi.append(A[i])
sm=sum(abs(i) for i in A)

A_tgt=A_nega if len(A_nega)>len(A_posi) else A_posi
A_tgt=sorted(A_tgt)

diff=0
old=0
mindiff=0
for i,a in enumerate(A_tgt):
    if old<a:
        diffdiff=(-i+(len(A_tgt)-i))*(a-old)
    else:
        continue
    if diffdiff<0:
        break
    old=a
    diff = diff+diffdiff
    total_diff=-diff+a*(N-len(A_tgt))
    if total_diff<mindiff:
        mindiff=total_diff
print((sm+mindiff))
# Original solution
import statistics
from decimal import Decimal,ROUND_HALF_UP

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

for i in range(n):
    a[i] -= i+1
a.sort()

med = Decimal(str(statistics.median(a))).quantize(Decimal('0'), rounding=ROUND_HALF_UP)
print((sum([abs(i-med) for i in a])))

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

for i in range(n):
    a[i] -= i+1
a.sort()

ans = 0
for i in range(n):
    ans += abs(a[i] - a[n//2])
print(ans)
# Original solution
from statistics import median

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

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

def calc_score(b):
    score = 0
    for a in A_star:
        score += abs(a - b)
    return score

def decide_direction(b):
    score0 = calc_score(b)
    score1 = calc_score(b + 1)
    if score0 > score1:
        return 1
    else:
        return -1

b = int(median(A_star))
direction = decide_direction(b)
pre_score = calc_score(b)

while True:
    b += direction
    score = calc_score(b)
    if score >= pre_score:
        print(pre_score)
        break
    else:
        pre_score = score






# Optimized solution
from statistics import median

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

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

def calc_score(b):
    score = 0
    for a in A_star:
        score += abs(a - b)
    return score

print((calc_score(int(median(A_star)))))
# Original solution
import sys
from collections import deque
from collections import  Counter
import statistics
import math
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
a_li = na()
for i in range(n):
    a_li[i] = a_li[i] - (i + 1)
m1 = statistics.median_low(a_li)
m2 = statistics.median_high(a_li)
ans1 = 0
ans2 = 0
for i in range(n):
    ans1 += abs(a_li[i] - m1)
    ans2 += abs(a_li[i] - m2)
print((min(ans1, ans2)))


# Optimized solution
import sys
from collections import deque
from collections import  Counter
import statistics
import math
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
a_li = na()
for i in range(n):
    a_li[i] = a_li[i] - (i + 1)
m1 = statistics.median_low(a_li)
#m2 = statistics.median_high(a_li)
ans1 = 0
#ans2 = 0
for i in range(n):
    ans1 += abs(a_li[i] - m1)
    #ans2 += abs(a_li[i] - m2)
print(ans1)
# Original solution
import sys
from collections import deque
from collections import  Counter
import statistics
import math
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
a_li = na()
for i in range(n):
    a_li[i] = a_li[i] - (i + 1)
m1 = statistics.median_low(a_li)
#m2 = statistics.median_high(a_li)
ans1 = 0
#ans2 = 0
for i in range(n):
    ans1 += abs(a_li[i] - m1)
    #ans2 += abs(a_li[i] - m2)
print(ans1)


# Optimized solution
import sys
from collections import deque
from collections import  Counter
import statistics
import math
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
a_li = na()
for i in range(n):
    a_li[i] = a_li[i] - (i + 1)
m1 = statistics.median_high(a_li)
#m2 = statistics.median_high(a_li)
ans1 = 0
#ans2 = 0
for i in range(n):
    ans1 += abs(a_li[i] - m1)
    #ans2 += abs(a_li[i] - m2)
print(ans1)
# Original solution
N = int(eval(input()))
A = [int(x) for x in input().split()]
B = sorted([A[i]-i for i in range(N)])
# return -A[0]-...-A[k-1]+A[k]+...+A[N-1]
def partial_sum(k):
    return -sum(B[:k]) + sum(B[k:])

l = [partial_sum(i) -(N-2*i)*B[i] for i in range(N)]
print((min(l)))


# Optimized solution
N = int(eval(input()))
A = [int(x) for x in input().split()]
B = sorted([A[i]-i for i in range(N)])
b = B[(N-1)//2] if N % 2 != 0 else (B[N//2-1]+B[N//2])//2
print((sum(abs(B[i]-b) for i in range(N))))
# Original solution
# https://atcoder.jp/contests/abc102/tasks/arc100_a
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


class cumsum1d:
    def __init__(self, ls: list):
        '''
        1次元リストを受け取る
        '''
        from itertools import accumulate
        self.ls_accum = [0] + list(accumulate(ls))

    def total(self, i, j):
        # もとの配列lsにおける[i,j)の中合計
        return self.ls_accum[j] - self.ls_accum[i]


N = read_a_int()
A = read_ints()
if N == 1:
    print((0))
    exit()
B = [a - i for a, i in zip(A, list(range(1, N + 1)))]
B.sort()

# 絶対値を区切る境目はどこがよいか？
B_cum = cumsum1d(B)
ans = 10**15
for k in range(1, N):
    tmp_sum = -B_cum.total(0, k) + B_cum.total(k, N)
    add = min((2 * k - N) * B[k - 1], (2 * k - N) * B[k])
    ans = min(ans, tmp_sum + add)


print(ans)
# 式ごちゃごちゃやったけど絶対楽な方法がある。
# 明日復習


# Optimized solution
# https://atcoder.jp/contests/abc102/tasks/arc100_a
# Aの数列を前処理で加工し、順番に依存しない数列Bに加工する
# abs(Bi-x)の和を最小化するxはBの中央値である。(立式しxで微分したのちKについて増減表を書いてみよ)
# それを答えとすれば良い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


N = read_a_int()
A = read_ints()
B = [a - i for a, i in zip(A, list(range(1, N + 1)))]
B.sort()

x = B[N // 2]
ans = 0
for b in B:
    ans += abs(x - b)


print(ans)
# Original solution
from statistics import mean
import math
N = int(eval(input()))
*A, = list(map(int, input().split()))
B = [A[i]-i for i in range(N)]
b = mean(B)
bm = math.floor(b)
K = [x - bm for x in B]
KZ = [abs(x) for x in K]
Z = sum(KZ)
for i in range(2000):
    C = [abs(x-i+1000) for x in K]
    Z = min([sum(C),Z])
print((int(Z)))

# Optimized solution
from statistics import median
import math
N = int(eval(input()))
*A, = list(map(int, input().split()))
B = [A[i]-i for i in range(N)]
b = median(B)
bm = math.floor(b)
K = [x - bm for x in B]
KZ = [abs(x) for x in K]
Z = sum(KZ)
for i in range(20):
    C = [abs(x-i+10) for x in K]
    Z = min([sum(C),Z])
print((int(Z)))
# Original solution
from statistics import median
import math
N = int(eval(input()))
*A, = list(map(int, input().split()))
B = [A[i]-i for i in range(N)]
b = median(B)
bm = math.floor(b)
K = [x - bm for x in B]
KZ = [abs(x) for x in K]
Z = sum(KZ)
for i in range(20):
    C = [abs(x-i+10) for x in K]
    Z = min([sum(C),Z])
print((int(Z)))

# Optimized solution
from statistics import median
import math
N = int(eval(input()))
*A, = list(map(int, input().split()))
B = [A[i]-i for i in range(N)]
b = median(B)
bm = math.floor(b)
bM = math.ceil(b)
Bm = [abs(x - bm) for x in B]
BM = [abs(x - bM) for x in B]
m = sum(Bm)
M = sum(BM)
print((int(min([m,M]))))
# Original solution
n=int(eval(input()))

X=list(map(int,input().split()))
Y=[]
for i in range(n):
    Y.append(X[i]-(i+1))

Z=list(set(Y))
res=10000000000000000
for i in range(len(Z)):
    cnt=0
    for j in  range(n):
        cnt+=abs(Y[j]-Z[i])
    if cnt<res:
        res=cnt
    
print(res)

# Optimized solution
n=int(eval(input()))

X=list(map(int,input().split()))
Y=[]
for i in range(n):
    Y.append(X[i]-(i+1))
Y.sort()
res_1=0

if n%2==1:
    m=Y[int((n-1)/2)]
    for j in range(n):
        res_1+=abs(Y[j]-m)
else:
    m=(Y[int(n/2)-1]+Y[int(n/2)])//2
    for j in range(n):
        res_1+=abs(Y[j]-m)
        

        
print(res_1)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
ans = 10 ** 9
for i in range(n):
    b = a[i] - (i+1)
    f = 0
    for j in range(n):
        f += abs(a[j] - (b + j + 1))
    ans = min(f,ans)
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]
f = 0
for i in range(n):
    f += abs(B[i] - b)
print(f)
# Original solution
# -*- coding: utf-8 -*-
# AtCoder Beginner Contest


if __name__ == '__main__':
    from statistics import median

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

    # See:
    # https://www.youtube.com/watch?v=UX4AuiCVtN4
    # https://beta.atcoder.jp/contests/abc102/submissions/2768315
    mod_a = sorted([ai - i for i, ai in enumerate(a, 1)])
    b = median(mod_a)

    for i in range(n):
        total += abs(mod_a[i] - b)

    print((int(total)))


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


def main():
    from statistics import median

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

    for index, ai in enumerate(a, 1):
        mod_a.append(ai - index)

    b = int(median(mod_a))

    for mod_ai in mod_a:
        ans += abs(mod_ai - b)

    print(ans)


if __name__ == '__main__':
    main()
# Original solution
from math import ceil, floor

N = int(eval(input()))
A = [int(t) for t in input().split()]
if len(A) != N: raise

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

q = []
for b in p:
    q.append(sum(abs(x - b) for x in p))
print((min(q)))

# Optimized solution
from math import ceil, floor

N = int(eval(input()))
A = [int(t) for t in input().split()]
if len(A) != N: raise

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

q = []
for b in p[N//2 - 1 : N//2 + 2]:
    q.append(sum(abs(x - b) for x in p))
print((min(q)))
# Original solution
from math import ceil, floor

N = int(eval(input()))
A = [int(t) for t in input().split()]
if len(A) != N: raise

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

q = []
for b in p[N//2 - 1 : N//2 + 2]:
    q.append(sum(abs(x - b) for x in p))
print((min(q)))


# Optimized solution
N = int(eval(input()))
A = [int(t) for t in input().split()]
if len(A) != N: raise

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

b = p[N // 2]
print((sum(abs(x - b) for x in p)))
# Original solution
from statistics import median as m
n=int(eval(input()))
A=list(map(int,input().split()))
B=sorted([A[i]-i-1 for i in range(n)])
print((int(sum([abs(b-m(B)) for b in B]))))

# Optimized solution
from statistics import median as m
n=int(eval(input()))
A=list(map(int,input().split()))
B=sorted([A[i]-i-1 for i in range(n)])
mb=m(B)
print((int(sum([abs(b-mb) for b in B]))))
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))

b_low=-1*(10**20)
b_high=10**20
b_low_d=sum([abs(a[i]-(b_low+2+i)) for i in range(n)])-sum([abs(a[i]-(b_low+1+i)) for i in range(n)])
b_high_d=sum([abs(a[i]-(b_high+2+i)) for i in range(n)])-sum([abs(a[i]-(b_high+1+i)) for i in range(n)])

while b_high-b_low>10:
  b_tmp=(b_low+b_high)//2
  b_tmp_d=sum([abs(a[i]-(b_tmp+2+i)) for i in range(n)])-sum([abs(a[i]-(b_tmp+1+i)) for i in range(n)])
  if b_tmp_d>0:
    b_high=b_tmp
  else:
    b_low=b_tmp

ans=10**20
for j in range(b_low,b_high):
  ans=min(ans,sum([abs(a[i]-(j+2+i)) for i in range(n)]))

print(ans)

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

b_low=-1*(10**12)
b_high=10**12
b_low_d=sum([abs(a[i]-(b_low+2+i)) for i in range(n)])-sum([abs(a[i]-(b_low+1+i)) for i in range(n)])
b_high_d=sum([abs(a[i]-(b_high+2+i)) for i in range(n)])-sum([abs(a[i]-(b_high+1+i)) for i in range(n)])

while b_high-b_low>10:
  b_tmp=(b_low+b_high)//2
  b_tmp_d=sum([abs(a[i]-(b_tmp+2+i)) for i in range(n)])-sum([abs(a[i]-(b_tmp+1+i)) for i in range(n)])
  if b_tmp_d>0:
    b_high=b_tmp
  else:
    b_low=b_tmp

ans=10**20
for j in range(b_low,b_high):
  ans=min(ans,sum([abs(a[i]-(j+2+i)) for i in range(n)]))

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

b_low=-1*(10**10)
b_high=10**10
b_low_d=sum([abs(a[i]-(b_low+2+i)) for i in range(n)])-sum([abs(a[i]-(b_low+1+i)) for i in range(n)])
b_high_d=sum([abs(a[i]-(b_high+2+i)) for i in range(n)])-sum([abs(a[i]-(b_high+1+i)) for i in range(n)])

while b_high-b_low>10:
  b_tmp=(b_low+b_high)//2
  b_tmp_d=sum([abs(a[i]-(b_tmp+2+i)) for i in range(n)])-sum([abs(a[i]-(b_tmp+1+i)) for i in range(n)])
  if b_tmp_d>0:
    b_high=b_tmp
  else:
    b_low=b_tmp

ans=10**20
for j in range(b_low,b_high):
  ans=min(ans,sum([abs(a[i]-(j+2+i)) for i in range(n)]))

print(ans)

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

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

if len(arr)%2==0:
  tmp=[arr[len(arr)//2-1],arr[len(arr)//2]]
else:
  tmp=[arr[len(arr)//2]]

ans=10**20
for b in tmp:
  ans=min(ans,sum([abs(a[i]-b-i-1) for i in range(n)]))
print(ans)
# Original solution
#                         author:  kagemeka 
#                         created: 2019-11-08 14:51:29(JST)
## internal modules
import sys
# import collections
# import math
# import string
# import bisect
# import re
# import itertools
import statistics
# import functools
# import operator
## external modules
# import scipy.special   # if use comb function on AtCoder, 
# import scipy.misc      # select scipy.misc.comb (old version) 

def main():
    n, *a = (int(x) for x in sys.stdin.read().split())
    
    for i in range(n):
        a[i] -= (i + 1)

    if n % 2 != 0:
        b = statistics.median(a)
    else:
        if a.count(statistics.median_high(a)) >= a.count(statistics.median_low(a)):
            b = statistics.median_high(a)
        else:
            b = statistics.median_low(a)
    
    ans = sum([abs(a[i] - b) for i in range(n)])
    print(ans)


if __name__ == "__main__":
    # execute only if run as a script
    main()




# Optimized solution
import sys

n, *a = list(map(int, sys.stdin.read().split()))

def main():
    for i in range(n):
        a[i] -= (i + 1)
    a.sort()
    b = a[n // 2]
    res = 0
    for i in range(n):
        res += abs(a[i] - b)
    
    return res
    
if __name__ == '__main__':
    ans = main()
    print(ans)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
c = []

for i in range(n):
    c.append(a[i] - (i + 1))

c.sort()
ave = c[n//2]


ans = 10**9*n

for b in range(ave-100, ave+100):
    t = 0
    for i in range(n):
        t += abs(c[i]-b)
    ans = min(ans, t)

print(ans)

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

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

a.sort()

if n % 2 == 1:
    median = a[n // 2]
else:
    median = (a[n//2 - 1] + a[n//2]) // 2

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

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

max = max(a)
min = max * -1
ans = 10000000
prev = 10000000
t = len(a)
flag = 0
for b in range(min,max):
  sum = 0
  for i in range(t):
    sum += abs(a[i] - (b+i+1))
  if ans > sum:
    ans = sum
  if prev < sum:
    flag += 1
  if flag == 2:
    break
  prev = sum

print(ans)

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

b = []

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

# print(b)
b.sort()
# print(b)

min_b=b[n//2]
# print(min_b)

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

res = 0
x = B[N//2]

for i in range(N):
    res += max(x - B[i], -x + B[i])

print(res)

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

res = 0
x = B[N//2]

for i in range(N):
    res += abs(x - B[i])

print(res)
# Original solution
N = int(eval(input()))
AS = input().split()
for i in AS:
    i = int(i)
result = 0
result_f = 0
result_rf = 0
for j in range (1, N+1):
    result += abs(int(AS[j-1]) - 0 - j)
for j in range (1, N+1):
    result_f += abs(int(AS[j-1]) - 1 - j)
for j in range (1, N+1):
    result_rf += abs(int(AS[j-1]) - ( - 1) - j)
if result < result_f and result < result_rf:
    print(result)
else:
    old_list= [0]
    b = 1
    while(not b in old_list):
        counter = 0
        for j in range (1,N+1):
            counter += abs(int(AS[j-1]) - b - j)
        if counter <= result:
            old_list.append(b)
            b += 1
            result = counter
        else:
            old_list.append(b)
            continue
    result_1 = result
    b = -1
    while(not b in old_list):
        counter = 0
        for j in range (1,N+1):
            counter += abs(int(AS[j-1]) - b - j)
        if counter <= result:
            old_list.append(b)
            b -= 1
            result = counter
        else:
            old_list.append(b)
            continue
    result_2 = result
    print((min(result_1,result_2)))

# Optimized solution
N = int(eval(input()))
AS = input().split()
AS = [int(i) for i in AS]
BS = [int(AS[j-1] - j) for j in range(1,N+1)]
BS_s = BS.sort()
b = BS[N//2]
result_a = 0
result_b = 0
result_c = 0
for j in range (1, N+1):
    result_a += abs(int(AS[j-1]) - b - j)
for j in range (1, N+1):
    result_b += abs(int(AS[j-1]) - b - 1 - j)
for j in range (1, N+1):
    result_c += abs(int(AS[j-1]) - b + 1 - j)
print((int(min(result_a,result_b,result_c))))
# Original solution
N = int(eval(input()))
A = [int(x)-i for x,i in zip(input().split(),list(range(1,N+1)))]
from math import ceil,floor
    
A.sort()


if N%2 == 0:
    b = round((A[floor(N/2)]+A[ceil(N/2)])/2)
else:
    b = A[floor(N/2)]
ans = 0
for a in A:
    ans += abs(a-b)
print(ans)

# Optimized solution
def main():
    N = int(eval(input()))
    A = list(map(int,input().split()))
    B = [A[i-1] - i for i in range(1,N+1)]
    B.sort()
    b = B[N // 2] if N%2 == 1 else round((B[N // 2 - 1] + B[N // 2]) / 2)
    print((sum([abs(bb -b) for bb in B])))
    return

if __name__ == "__main__":
    main()