Problem:
 Score : 300 points    Problem Statement Snuke has an integer sequence A of length N .  He will freely choose an integer b .
Here, he will get sad if A_i and b+i are far from each other.
More specifically, the sadness of Snuke is calculated as follows:   abs(A_1 - (b+1)) + abs(A_2 - (b+2)) + ... + abs(A_N - (b+N))   Here, abs(x) is a function that returns the absolute value of x .  Find the minimum possible sadness of Snuke.      Constraints  1 \leq N \leq 2 \times 10^5  1 \leq A_i \leq 10^9  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  A_1  A_2  ...  A_N       Output Print the minimum possible sadness of Snuke.        Sample Input 1 5
2 2 3 5 5      Sample Output 1 2  If we choose b=0 , the sadness of Snuke would be abs(2-(0+1))+abs(2-(0+2))+abs(3-(0+3))+abs(5-(0+4))+abs(5-(0+5))=2 .
Any choice of b does not make the sadness of Snuke less than 2 , so the answer is 2 .       Sample Input 2 9
1 2 3 4 5 6 7 8 9      Sample Output 2 0       Sample Input 3 6
6 5 4 3 2 1      Sample Output 3 18       Sample Input 4 7
1 1 1 1 2 3 4      Sample Output 4 6

Solution (Python):


import statistics

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

b = []

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

bf = int(statistics.median(b))

ans = 0

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

print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
B = [A[i]-i-1 for i in range(N)]
B.sort()
res = 0
b = B[N//2]
for i in B:
    res = res + abs(i-b)
print(res)

Solution (Python):
from collections import Counter
from functools import reduce
import fractions
import math
import sys
import statistics
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]  
def LF(): return [float(x) for x in sys.stdin.readline().split()]  
def LS(): return sys.stdin.readline().split()  
def MI(): return map(int, sys.stdin.readline().split())  
def II(): return int(sys.stdin.readline())  
def IS(): return input()  
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):  
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):  
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))


N = II()
a = LI()
ai = [a[i-1] - i for i in range(1, N+1)]
b = round(statistics.median(ai))
print(sum([abs(b - ai[i]) for i in range(len(ai))]))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
	a[i] -= i + 1
a = sorted(a)

res = 10 ** 100
if n % 2 == 0:
	p = n // 2 - 1
	q = n // 2
	for cand in [p, q]:
		tmp = 0
		for i in a:
			tmp += abs(i - a[cand])
		res = min(res, tmp)
else:
	tmp = 0
	for i in a:
		tmp += abs(i - a[n // 2])
	res = min(res, tmp)
	
print(res)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))

A = sorted([A[i]-(i+1) for i in range(N)])
mid = A[N//2]
print(sum([abs(a-mid) for a in A]))

Solution (Python):


 
import statistics
 
N = int(input())
A = list(map(int, input().rstrip().split(' ')))
 
A_dash = sorted([x - i - 1 for i, x in enumerate(A)])
med = int(statistics.median(A_dash))

print(sum([abs(x - med) for x in A_dash]))

Solution (Python):
N = int(input())
A = list(map(int,input().split()))

B = [A[i]-(i+1) for i in range(N)]
b = sorted(B)[N//2]
ans = 0
for i in range(N): ans += abs(A[i]-(b+i+1))

print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


inf = float('inf')



N = 0
A = []
X = []


def set_inputs():
    global N, A
    N = get_int()
    A = get_li()
    return


def f(n):
    return sum(abs(x-n) for x in X)


def main():
    global X
    setrecursionlimit(100000)
    set_inputs()
    X = [a - (i + 1) for i, a in enumerate(A)]
    X.sort()
    b = X[0]
    i = 1
    passed = 0
    same = 1
    coming = N - 1
    ans = f(b)
    tmp = ans
    while i < N:
        if X[i] == b:
            same += 1
            coming -= 1
            i += 1
            continue
        diff = X[i] - b
        tmp = tmp + (passed + same - coming) * diff
        ans = min(ans, tmp)
        b = X[i]
        passed += same
        same = 1
        coming -= 1
        i += 1
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A = [A[i] - i for i in range(N)]
A.sort()
b = A[N // 2]
c = 0
for i in range(N):
    c += abs(A[i] - b)
print(c)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A = [A[i] - i - 1 for i in range(N)]
A.sort()
c = 0
b = A[N//2]
for i in range(N):
         c += abs(A[i] - b)
print(c)

Solution (Python):
N = int(input())
a = list(map(int, input().split()))
b = [0] * N
for i in range(N):
    b[i] = a[i] - (i + 1)
b.sort()
if N % 2 == 0:
    m = (b[N // 2 - 1] + b[N // 2]) // 2
else:
    m = b[N // 2]
ans = 0
for i in range(N):
    ans += abs(b[i] - m)
print(ans)

Solution (Python):
n=int(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]))

Solution (Python):
n=int(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]))

Solution (Python):
n=int(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)

Solution (Python):
n=int(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)

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]
for i in range(N):
    A[i] = A[i]-(i+1)
A.sort()
b = A[N//2]
ans = 0
for i in range(N):
    ans += abs(A[i]-b)
print(ans)

Solution (Python):
def main():
    n = int(input())
    a = [int(s) for s in input().split()]
    print(solve(a))

def solve(a):
    n = len(a)
    b = [a[i] - i for i in range(n)]
    b.sort()

    c = b[n // 2]

    return sum(abs(bi - c) for bi in b)

main()

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
sum = 0
for i in range(n):
   a[i] = a[i] -(i+1)
a.sort()
if n % 2 ==1:
    b = a[(n//2)]
else:
    b = (a[n//2]+a[n//2-1]) //2
for i in range(n):
    sum += abs(a[i]-b)
print(sum)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
B = [A[i] - (i+1) for i in range(N)]

B.sort()

print(sum([abs(x - B[N//2]) for x in B]))

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]-=i+1
a=sorted(a)
x=a[(-(-n//2))-1]
ans=0
for k in range(n):
    ans+=abs(a[k]-x)
print(ans)

Solution (Python):
N=int(input())
A=[int(x) for x in input().split()]
for i in range(N):
  A[i]=A[i]-1-i
A.sort()
if N==1:
  print(0)
else:
  b=A[N//2]
  c=A[(N//2)+1]
  ans1,ans2=0,0
  for i in range(N):
    ans1+=abs(A[i]-b)
    ans2+=abs(A[i]-c)
  print(min(ans1,ans2))

Solution (Python):
N = int(input())
a = [ int(x) for x in input().split() ]
b = [ a[i] - (i+1) for i in range(N) ]
b.sort()

print( sum([abs(x-b[N//2]) for x in b] ) )

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a=[-(i+1)+j for i,j in enumerate(a)]
a.sort()
if len(a)%2==0:
    tmp=len(a)//2
    b=(a[tmp]+a[tmp-1])//2
else:
    tmp=len(a)//2
    b=a[tmp]
print(sum(map(lambda x:abs(x-b),a)))

Solution (Python):
n = int(input())
a = [int(item) for item in input().split()]

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

a = sorted(a)
med = a[n//2]

b1, b2, b3 = 0, 0, 0
for i in range(n):
  b1 += abs(a[i] - med - 1)
  b2 += abs(a[i] - med)
  b3 += abs(a[i] - med + 1)
  
print(min([b1, b2, b3]))

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
B=[A[i]-i-1 for i in range(N)]
B.sort()
C=[abs(B[i]-B[int((N-1)/2)]) for i in range(N)]
print(sum(C))

Solution (Python):
N=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)

Solution (Python):
import statistics
n = int(input())
x = [int(i) for i in input().split()]
x = [x_ - i for i, x_ in enumerate(x)]
median = statistics.median(x)
x = [abs(x_ - median) for x_ in x]
ans = int(sum(x))
print(ans)

Solution (Python):
from statistics import median as m;n=input();d=[i-h-1 for h,i in enumerate(list(map(int,input().split())))];k=int(m(d));print(sum([abs(i-k) for i in d]))

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
for i in range(n):
  a[i] -= i
a.sort()
b = a[n//2]
ans = 0
for i in a:
  ans += abs(i-b)
print(ans)

Solution (Python):
n = int(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)

Solution (Python):
n = int(input())
a = [int(i) for i in input().split(" ")]
a = [a[i] - (i + 1) for i in range(0, n)]
a = sorted(a)

if n % 2 == 0:
    print(-1 * sum(a[0:n//2]) + sum(a[n//2:]))
else:
    print(-1 * sum(a[0:n//2]) + sum(a[n//2 + 1:]))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
for i in range(len(a)):
    a[i] -= i + 1
a.sort()
res = 10 ** 30
if n % 2 == 0:
    il = [n//2-1, n//2]
else:
    il = [n//2]
for i in il:
    total = 0
    for j in range(len(a)):
        total += abs(a[i] - a[j])
    res = min(res, total)
print(res)

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

test = False
if test:
    N = 2*10**5
    A = [i*2 for i in range(N)]
else:
    N = I()
    A = LI()

for idx in range(0, N):
    A[idx] -= idx + 1

import statistics
b = statistics.median(A)

result = 0
for a in A:
    result += abs(a-b)
print(int(result))

Solution (Python):
N=int(input())
A=list(map(int,input().split()))

B=[A[i]-i-1 for i in range(N)]
C=sorted(B)
s=0

for i in range(N):
    s=s+abs(C[i]-C[(N-1)//2])

print(s)

Solution (Python):

import math
N=int(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)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A = [A[i] - i-1 for i in range(N)]
A.sort()
b = A[N//2]
print(sum([abs(A[i]-b) for i in range(N)]))

Solution (Python):
N = int(input())
Ai = list(map(int, input().split()))

Bi = []
for i in range(N):
    Bi.append(Ai[i] - (i + 1))
Bi.sort()
b = Bi[len(Bi) // 2]
ans = 0
for i in range(N):
    ans += abs(Ai[i] - (b + i + 1))
print(ans)

Solution (Python):
import statistics
n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in range(n):
    b[i]=a[i]-(i+1)
b.sort()
if n%2==1:
    m=statistics.median(b)
    b=list(map(lambda x:abs(x-m),b))
    ans=0
    for i in range(n):
        ans+=b[i]
else:
    m1=b[n//2]
    m2=b[n//2+1]
    k=list(map(lambda x:abs(x-m1),b))
    l=list(map(lambda x:abs(x-m2),b))
    ans1=0
    ans2=0
    for i in range(n):
        ans1+=k[i]
        ans2+=l[i]
    ans=min(ans1,ans2)
print(ans)

Solution (Python):
N=int(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//2]
else:
    b=(B[N//2-1]+B[N//2])//2
ans=sum([abs(a-b) for a in B])
print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    a[i] -= i+1
a.sort()
if n == 1:
    print(0)
    exit()
p = a[n//2]
q = a[n//2 - 1]
res = 0
for e in a:
    res += abs(e-p)
ans = 0
for e in a:
    ans += abs(e-q)
print(min(res,ans))

Solution (Python):

N = int(input())
A = [int(i) for i in input().split()]
for i in range(len(A)):
    A[i] -= i+1
A.sort()
b = A[N // 2]
print(sum([abs(a-b) for a in A]))

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]

b = []

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

b = sorted(b)

x = b[n//2] if n%2==1 else (b[n//2] + b[(n//2)-1]) // 2

sum_num = 0
for b_ in b:
    sum_num += abs(b_-x)

print(sum_num)

Solution (Python):
N = int(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//2]
else:
    b = (B[N//2-1] + B[N//2]) // 2

ans = sum([abs(BB-b) for BB in B])
print(ans)

Solution (Python):
n = int(input())

l = list(map(int,input().split()))

l = [l[i]-(i+1) for i in range(len(l))]

l.sort()

b = l[len(l)//2]
res = 0

for c in l:
    res += abs(c-b)
print(res)

Solution (Python):
input = open(0).read

N, *An = map(int, input().split())


def main():
    for i in range(N):
        An[i] = An[i] - i - 1

    ans = 0

    An.sort()

    for i in range(N):
        ans += abs(An[i] - An[N // 2])

    print(ans)
    return


main()

Solution (Python):
import statistics
n = int(input())
a = list(map(int, input().split()))
summ = 0
for i in range(n):
    a[i] = a[i] - (i + 1)
b = statistics.median_low(a)
ans = 0
for i in range(n):
    ans += abs(a[i] - b)
print(ans)

Solution (Python):
n = int(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)

Solution (Python):
import sys
input = sys.stdin.readline
n = int(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)

Solution (Python):
def solve(string):
    n, *a = map(int, string.split())
    a = sorted([_a - i - 1 for i, _a in enumerate(a)])
    median = a[len(a) // 2]
    return str(sum([abs(_a - median) for _a in a]))


if __name__ == '__main__':
    print(solve("\n".join([input(), input()])))

Solution (Python):
from collections import Counter


def solve(string):
    n, *a = map(int, string.split())
    a = sorted([_a - i - 1 for i, _a in enumerate(a)])
    median = a[len(a) // 2]
    return str(sum([abs(_a - median) for _a in a]))


if __name__ == '__main__':
    print(solve("\n".join([input(), input()])))

Solution (Python):
import numpy as np
N = int(input())
lst = np.array(list(map(int, input().split() )))
for i in range(len(lst)):
    lst[i] = lst[i] - (i +1)

b = int(np.median(lst) )  


count = 0
for A in lst:
    count += abs(A -b)
print(count)

Solution (Python):
import statistics
N = int(input())
A = list(map(int, input().split()))

B = [A[i] - (i + 1) for i in range(N)]
B.sort()
b = int(statistics.median(B))
print(sum([abs(B[i] - b) for i in range(N)]))

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
tmp = sorted([A[i-1]-i for i in range(1,N+1)])
B = tmp[N//2]
print(sum([abs(t-B) for t in tmp]))

Solution (Python):
N = int(input())
a = list(map(int, input().split()))
a_ = sorted([n - (i+1) for i, n in enumerate(a) ])

if N//2 == 0:
    b = a_[N//2]
else:
    b = a_[(N-1)//2]

s = [abs(n - b) for i, n in enumerate(a_)]

print(sum(s))

Solution (Python):
def linear_approximation(N: int, A: int)->int:
    """悲しさを f(b) = sum|ai - (b + i)| とする。
    これを少し変形して
    f(b) = sum|b - (ai - i)|
    とする。この形の関数は b = (ai - i) の位置で傾きが代わり、
    詳しくは述べないが、ソートして N/2 番目の点で最小値になる。
    """
    new_A = []  
    for i, a in enumerate(A):
        tmp = a - (i+1)
        new_A.append(tmp)

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

    return sum(abs(a-b) for a in new_A)


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = linear_approximation(N, A)
    print(ans)

Solution (Python):
import statistics
N = int(input())
A = list(map(int, input().split()))
A = [A[i]-(i+1) for i in range(N)]
b = int(statistics.median(A))
print(sum([abs(A[i]-b) for i in range(N)]))

Solution (Python):
import math
N = int(input())
A = list(map(int, input().split()))
A = [A[i] - i - 1 for i in range(N)]
A.sort()
c = int(math.floor(N/2))
answer = sum(list(map(abs,[A[i] - A[c] for i in range(N)])))
print(answer)

Solution (Python):
import numpy as np
N=int(input())
a=np.array(list(map(int,input().split())))

def calc(b):
    ret=0
    for i in a:
        ret+=abs(i-b)
    return ret

for i in range(N):
    a[i]-=(i+1)
a=np.sort(a)
median=int(np.median(a))

ans1=calc(median)
ans2=calc(median+1)
print(min(ans1,ans2))

Solution (Python):
import statistics

N=int(input())
L=list(map(int,input().split()))
for i in range(N):
  L[i]=L[i]-(i+1)
m=statistics.median(L)
ans=0
for i in range(N):
  ans+=abs(L[i]-m) 
print(int(ans))

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
tmp = sorted([A[i-1]-i for i in range(1,N+1)])
mid = tmp[N//2]
print(sum([abs(t-mid) for t in tmp]))

Solution (Python):
import statistics as st
n=int(input())
a=list(map(int, input().split()))
a1=[a[i]-(i+1) for i in range(n)]
med=st.median(a1)
ans=0
for ai in a1:
    ans+=abs(ai-med)
print(int(ans))

Solution (Python):


import sys 


n = int(input())
a = list(map(int, sys.stdin.readline().rstrip().split()))
for i in range(n):
  a[i] = a[i]-i-1
a = sorted(a)
m = n // 2

ans1,ans2 = 0,0
for i in range(n):
  ans1 += abs(a[i] - a[m])
  if n > 1:
    ans2 += abs(a[i] - a[m+1])
  else:
    ans2 += abs(a[i] - a[m])

print(min(ans1, ans2))

Solution (Python):
n = int(input())
lst = list(map(int, (input().split())))

dif_lst = []
for k, i in enumerate(lst):
    dif_lst.append(i-k-1)
l = len(dif_lst) // 2
a = sorted(dif_lst)[l]

ans = 0
for i in dif_lst:
    ans += abs((i-a))
print(ans)

Solution (Python):

n = int(input())
a = list(map(int, input().split()))
b = []
answer = []

for i in range(n):
	b.append(a[i]-i)
b.sort()
med = b[int(n/2)]

for i in range(n):
	answer.append(abs(a[i]-(med+i)))
	

print(sum(answer))

Solution (Python):


















import math
import numpy as np
import copy
from collections import defaultdict, Counter
from itertools import product
from bisect import bisect_left, bisect_right
def inpl(): return list(map(int, input().split()))


def res(nA, i):
    for i in range(min_A, max_A+1):
        tmp = sum([ abs(Ai - i) for Ai in nA ])
    if tmp < ans:
        ans = tmp
    return ans

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

nA = sorted([ Ai - (i+1) for i, Ai in enumerate(A)])
ans = 10e9

if len(nA) % 2 != 0:
    print(sum([ abs(Ai - nA[len(nA)//2]) for Ai in nA ]))
else:
    print(min(sum([ abs(Ai - nA[len(nA)//2-1]) for Ai in nA ]), sum([ abs(Ai - nA[len(nA)//2]) for Ai in nA ])))

Solution (Python):
import fractions
import statistics
import operator
from functools import reduce
N = int(input())
a_list = list(map(int, input().split(' ')))
median = statistics.median([a - i for i,a in enumerate(a_list)])
print(int(sum([abs(a - (median + i)) for i,a in enumerate(a_list)])))

Solution (Python):


"""
Created on 2019/3/2
Solved on 2019/3/
@author: shinjisu
"""



import statistics


def getInt(): return int(input())


def getIntList(): return [int(x) for x in input().split()]


def zeros(n): return [0]*n


def getIntLines(n): return [int(input()) for i in range(n)]


def getIntMat(n):
    mat = []
    for i in range(n):
        mat.append(getIntList())
    return mat


def zeros2(n, m): return [zeros(m)]*n


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**12


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def probC_WA_TLE():
    N = getInt()
    A = getIntList()
    dmp((N, A))
    a = [A[i]-i-1 for i in range(N)]
    dmp(a, 'a')
    m = int(statistics.mean(a))
    dmp(m, 'mean')
    s = int(statistics.pstdev(a)) + 2
    dmp(s, 'std dev')
    minSum = sum([abs(a[j]) for j in range(N)])
    dmp(minSum, 'minSum')
    for i in range(1, s):
        aSum = sum([abs(a[j]-m+i) for j in range(N)])
        dmp((aSum, -m+i), 'aSum, -m+i')
        minSum = min(minSum, aSum)
        aSum = sum([abs(a[j]-m-i) for j in range(N)])
        minSum = min(minSum, aSum)
        dmp((aSum, -m-i), 'aSum, -m-i')
        dmp(minSum, 'minSum')
    dmp(minSum, 'minSum')
    return minSum


def probC():
    N = getInt()
    A = getIntList()
    dmp((N, A))
    a = [A[i]-i-1 for i in range(N)]
    dmp(a, 'a')
    m = int(statistics.median(a))
    dmp(m, 'median')
    minSum = sum([abs(a[i]-m) for i in range(N)])
    dmp(minSum, 'minSum')
    return minSum


debug = False  
ans = probC()
print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
tmp = sorted([A[i-1] - i for i in range(1, N+1)])
mid = tmp[int(N/2)]
print(sum([abs(t - mid) for t in tmp]))

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
A=[a-i for i,a in enumerate(A,1)]
A.sort()
b=A[len(A)//2]
A=[abs(a-b) for a in A]
print(sum(A))

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
A=[a-i for i,a in enumerate(A,1)]
A.sort()
A_posi=[0 for i in range(N)]
A_posi[0]=A[0]
for i in range(1,N):
    A_posi[i]=A_posi[i-1]+A[i]
value=[0 for i in range(N)]
value[0]=A_posi[N-1]-N*A[0]
for i in range(1,N):
    value[i]=A_posi[N-1]-A_posi[i]-(N-i-1)*A[i]-A_posi[i-1]+(i)*A[i]
print(min(value))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
L = [0] * N
for i in range(N):
    L[i] = A[i] - i - 1
L.sort()
if N % 2 != 0:
    b = L[N // 2]
    ans = 0
    for i in range(N):
        ans += abs(A[i] - (b+i+1))
    print(ans)
else:
    b1 = L[N//2]
    b2 = L[N//2 + 1]
    ans1 = 0
    ans2 = 0
    for i in range(N):
        ans1 += abs(A[i] - (b1+i+1))
    for i in range(N):
        ans2 += abs(A[i] - (b2+i+1))
    print(min(ans1, ans2))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
x = [i+1 for i in range(N)]
B = list(map(lambda a, x: a-x, A, x))
B.sort()

idx = N // 2

if N % 2:
    n = B[idx]
else:
    n = (B[idx] + B[idx-1]) / 2
b = list(map(lambda b: abs(b-n), B))
print(int(sum(b)))

Solution (Python):
N = int(input())
A = list(map(int,input().split()))

def Linear_Approximation(i,list):
    sum = 0
    for j in range(N):
        sum += abs(list[j]-i)
    return sum

for i in range(N):
    A[i] = A[i] - (i+1)
A.sort()
if N % 2 == 0:
    print(Linear_Approximation(A[(N-1)//2],A))
else:
    print(Linear_Approximation(A[(N-1)//2],A))

Solution (Python):
N = int(input())
a = list(map(int, input().split()))
for i in range(N):
  a[i] -= i + 1
a.sort()
center1 = a[N//2]
center2 = a[(N-1)//2]
ans1 = 0
ans2 = 0
for i in range(N):
  ans1 += abs(a[i] - center1)
  ans2 += abs(a[i] - center2)
print(min(ans1, ans2))

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    a[i] = a[i]-i-1
a = sorted(a)
b = a[len(a)//2]
ans = 0
for i in range(n):
    ans += abs(a[i]-b)
print(ans)

Solution (Python):
import sys
from collections import Counter

def main():
  input = sys.stdin.readline
  N = int(input())
  A = list(map(int, input().split()))
  B = []
  for i in range(N):
    B.append(A[i] - (i+1))
  B = sorted(B)
  b = B[(N-1)//2]
  ans = 0
  for a in B:
    ans += abs(a-b)
  
  print(ans)


if __name__ == '__main__':
  main()

Solution (Python):
from statistics import median
n=int(input())
a=[int(i) for i in input().split()]
b=[a[i]-i for i in range(len(a))]
x=median(b)
c=[abs(i-x) for i in b]
print(int(sum(c)))

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
A = [x - i - 1 for i,x in enumerate(A)]
A .sort()
ans = 0
b = 0

if len(A) % 2 == 0:
    b = A[int(len(A)/2)]
else:
    b = A[int((len(A) -1)/2)]

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

print(ans)

Solution (Python):
n=int(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)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
B = A.copy()
for i in range(N):
    B[i] -= i+1
B.sort()
if N%2==0:
    n = N//2
    b = (B[n-1]+B[n]) // 2
else:
    b = B[(N-1)//2]
ans = 0
for i,a in enumerate(A):
    ans += abs(a - (b+i+1))
print(ans)

Solution (Python):
import statistics
n = int(input())
a = list(map(int, input().split()))
l = []
m = []
for i in range(n):
    m.append(a[i]-i)
med = int(statistics.median(m))
for i in range(n):
    l.append(abs(a[i]-(med+i)))
print(sum(l))

Solution (Python):
class Solver(object):
    def __init__(self):
        self.n = int(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()

Solution (Python):
import statistics
n=int(input())
L=list(map(int, input().split()))
LL=[L[i]-i-1 for i in range(n)]
m=statistics.median_low(LL)
LLL=[abs(LL[i]-m) for i in range(n)]
print(sum(LLL))

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
tmp = sorted([A[i-1] - i for i in range(1, N+1)])
mid = tmp[int(N/2)]
print(sum([abs(t - mid) for t in tmp]))

Solution (Python):
N = int(input())

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

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

B.sort()


if N % 2 == 1:
  t = B[N // 2]
else:
  t = (B[N // 2] + B[N // 2 - 1]) // 2

su = sum([abs(i - t) for i in B])
print(su)

Solution (Python):
n = int(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)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
B = [A[i-1] - i for i in range(1, len(A) + 1)]
B.sort()
def f(x):
    sum = 0
    for b in B:
        sum += abs(b-x)
    return sum
if len(B) % 2 == 0:
    print(f((B[len(B)//2] + B[len(B)//2 - 1])//2))
else:
    print(f(B[int(len(B)/2)]))

Solution (Python):
a = int(input())
x = list(map(int, input().split()))
for i in range(a):
    x[i]-=i+1
x.sort()

q = (x[a//2]+x[a//2-1])
if q >=0:
    if a%2==0:
        p=(q//2)
    else:
        p=x[a//2]
else:
    if a%2==0:
        p=-((-1)*q//2)
    else:
        p=x[a//2]
s=0

for i in range(a):
    s+=abs(x[i]-p)
print(s)

Solution (Python):
import math


def solve(N, As):
    As = [a - (i + 1) for i, a in enumerate(As)]
    high = 10 ** 10
    low = -10 ** 10
    while True:
        b = (high + low) // 2
        tans1 = sum(abs(a - b) for a in As)
        tans2 = sum(abs(a - b + 1) for a in As)
        if low == b:
            return min(tans1, tans2)

        if tans1 > tans2:
            high = b
        elif tans1 < tans2:
            low = b
        else:
            return min(tans1, tans2)


if __name__ == "__main__":
    N = int(input())
    As = list(map(int, input().split(" ")))
    print(solve(N, As))

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

from statistics import median

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

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
tmp = []
for i in range(N):
  tmp.append(A[i] - (i+1))
tmp.sort()
mid = tmp[int(N/2)]
ans = 0
for i in range(N):
  ans += abs(tmp[i] - mid)
print(ans)

Solution (Python):
n =int(input())
a = list(int(i) for i in input().split())
sa = []
for i in range(n):
  sa.append(a[i]-i-1)
sa.sort()
b = sa[n//2]
su =0
for i in range(n):
  su+= abs(sa[i]-b)
print(su)

Solution (Python):
import statistics
n=int(input())
A=list(map(int,input().split()))
B=[0]*n
for i in range(n):
    B[i]=A[i]-(i+1)
b=statistics.median(B)
C=[0]*n
for i in range(n):
    C[i]=abs(B[i]-b)
print(int(sum(C)))

Solution (Python):
N = input()

A = map(int,raw_input().split())

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

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

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

print ans

Solution (Python):
N = int(input())
A = [int(n) for n in input().split()]

A = sorted([n - i - 1 for i, n in enumerate(A)])

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

diff = [abs(n - b) for n in A]
sad = sum(diff)

print(sad)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
total=0
for i in range(N):
    A[i]=A[i]-(i+1)
A.sort()
tmp=0
if N%2==1:
    tmp=A[N//2]
else:
    tmp=A[N//2-1]
ans=0
for i in range(N):
    ans+=abs(A[i]-tmp)
print(ans)

Solution (Python):

import sys
from functools import reduce



def solve(lines):
    def func(s, i):
        re = s + abs(i - B)
        return re

    N = int(lines.pop(0))
    L = list(map(int, lines.pop(0).split(' ')))
    L = [ x - (i+1) for (i, x) in enumerate(L) ]
    L.sort()
    B = L[int(len(L) / 2)]
    print(reduce(func, L, 0))
    
    















lines = [x.strip() for x in sys.stdin.readlines()]




solve(lines)

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]

import statistics
check = []
for i in range(n):
    check.append(a[i] - (i+1))
b = statistics.median(sorted(check))

ans = 0
for i in range(n):
    ans += abs(check[i] - b)
print(int(ans))

Solution (Python):
N = int(input())
L = list(map(int,input().split()))
for i in range(N):
    L[i] = L[i] - (i+1)
L = sorted(L)

ans = 0
n=len(L)
med = int(L[(n+1)//2-1])

for i in range(N):
    ans+=abs(L[i]-med)
print(ans)

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [a - i for i, a in enumerate(A)]
    B.sort()
    ans = 0
    for i in range(N):
        ans += abs(A[i] - (B[N // 2] + i))
    print(ans)


main()

Solution (Python):
N = int(input())
A_ = list(map(int,input().split()))

A = []
for i,a_ in enumerate(A_):
    A.append(a_-i-1)

d = {}
for a in A:
    if a in d.keys():
        d[a] += 1
    else:
        d[a] = 1

count = 0
for d_ in sorted(d.items()):
    if count >= len(A)/2:
        break
    count += d_[1]
    d_prev = d_[0]

b1 = d_prev
b2 = d_[0]

ans1 = 0
ans2 = 0
for a in A:
    ans1 += abs(a-b1)
    ans2 += abs(a-b2)

print(min(ans1,ans2))