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):
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))
check = sorted(check)
b = statistics.median(check)

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

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

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

ans = sum(abs(aa - t) for aa in a)
print(ans)

Solution (Python):
import statistics


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

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

M = int(statistics.median(A))
R = []

for m in [M-2, M-1, M, M+1, M+2]:
    R.append(sum([abs(a - m) for a in A]))

print(min(R))

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

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

Solution (Python):
import sys
from functools import reduce
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
A = [a - i - 1 for i, a in enumerate(A)]
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(1, n + 1):
    B.append(A[i - 1] - i)
    
B.sort()
    
ans = 0
for i in range(1, n + 1):
    ans += abs(A[i - 1] - (B[n // 2] + i))
    
print(ans)

Solution (Python):
from statistics import median

N = int(input())
A = list(map(int,input().split()))
Asort = sorted([A[i]-i-1 for i in range(N)])


b_tmp = int(median(Asort))

submin = [abs(A[i]-b_tmp-i-1) for i in range(N)]

minA = sum(submin)

print(minA)

Solution (Python):
from statistics import median

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

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

ave=int(median(a))
ans=0

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

Solution (Python):

import math

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

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

    B.sort()
    b = B[int(N / 2)]

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

    print(err)


if __name__ == '__main__':
    main()

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

if N % 2 == 1:
    median = B[N//2]
    print(sum([abs(b - median) for b in B]))
else:
    median1 = B[N//2]
    median2 = B[N//2+1]
    print(min(sum([abs(b - median1) for b in B]), sum([abs(b - median2) for b in B])))

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

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

Solution (Python):
N = int(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(map(lambda x: abs(x-sorted_A[N//2]),A))

print(ans)

Solution (Python):
N=int(input())
A=sorted(a-i-1 for i,a in enumerate(map(int,input().split())))
print(sum(abs(a-A[N//2]) 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)

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

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

Solution (Python):

N=int(input())
series = list(map(int,input().split()))
seriesSub = [series[i] - (i+1) for i in range(len(series))]

def cry(a):
	ret=0
	for s in seriesSub:
		ret += abs(s-a)
	return ret

def BinarySeach(hi,lo):
	mid = (hi + lo) // 2
	while hi > lo:
		mid = (hi + lo) // 2
		if mid != len(series):
			if cry(mid+1) >= cry(mid):
				hi = mid
		if mid != 0:
			if cry(mid-1) >= cry(mid):
				lo = mid
	else:
		return cry(mid)
h = max(seriesSub)
l = min(seriesSub)
print(BinarySeach(h,l))

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


import numpy as np

A_N_list = np.array([A_list[i] - (i+1)  for i in range(len(A_list))])


AN_list = sorted(A_N_list)


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

count = 0
for id,i in enumerate(A_list):
    count += abs(i-(b+id+1)) 

print(count)

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

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

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

Solution (Python):

n = int(input())
a_list = list(map(int,input().split(" ")))
a_list = [A-(i+1) for i,A in enumerate(a_list)]

a_list = sorted(a_list)
if n%2 != 0:
    median = a_list[int((n-1)/2)]
else:
    median = int((a_list[int((n+1)/2)]+a_list[int((n-1)/2)])/2)

sad = 0
for a in a_list:
    sad += abs(a - median)
print(sad)

Solution (Python):
n = int(input())
A_list = list(map(int, input().split()))
for i in range(n):
    A_list[i] -= i
A_list.sort()

def sadness(a, mid):
    sad = 0
    for i in range(mid):
        sad += a[mid] - a[i]
    for i in range(mid+1,len(a)):
        sad += a[i] - a[mid]
    return sad

if n % 2 != 0:
    print(sadness(A_list, n//2))
else:
    print(min(sadness(A_list, n//2), sadness(A_list, n//2+1)))

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

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

for i in range(n):
    b = A[i] - ( i + 1)
    B.append(b)
    
B.sort()
ans = 0
for i in range(n):
    ans += abs(A[i] - (B[len(B) // 2] + i + 1))

print(ans)

Solution (Python):
import sys
from math import *
N = int(input().strip())
A = list(map(int, input().split()))
B = [A[i] - (i+1) for i in range(0, N)]

if N == 1:
  print(0)
  sys.exit()

def s(b):
    return sum([abs(Bi - b) for Bi in B])

def check():
    left = s(bmin) - s(bmin+1) >= 0
    right = s(bmax-1) - s(bmax) <= 0
    if right and left:
        
        return 0
    if left:
        
        return 1
    
    return 2

bmin = min(B)
bmax = max(B)
stype = check()
if stype == 0:
    bnow = bmin
    for i in range(0, 40):
        if s(bnow) - s(bnow+1) < 0:
            bmax = bnow
            bnext = round((bnow + bmin) / 2)
        else:
            bmin = bnow
            bnext = round((bnow + bmax) / 2)
        if bnext == bnow:
            break
        bnow = bnext
    smin = s(bnow)
elif stype == 1:
    smin = s(bmax)
elif stype == 2:
    smin = s(bmin)

print(smin)

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
B = []

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

B.sort()
medianB = B[n // 2]

Sum = 0
for i in range(n):
    Sum += abs(A[i] - (medianB + (i + 1))) 
    
print(Sum)

Solution (Python):
def s(aa, b):
    return sum(abs(a - (b + i + 1)) for i, a in enumerate(aa))


def main():
    n = int(input())
    aa = list(map(int, input().split()))
    bb = sorted(a - (i + 1) for i, a in enumerate(aa))
    if len(bb) % 2 != 0:
        b = bb[(len(bb) - 1) // 2]
    else:
        b = (bb[len(bb) // 2] + bb[len(bb) // 2 - 1]) // 2
    print(s(aa, b))


if __name__ == '__main__':
    main()

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

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

B = sorted(B)
M = B[int((N - 1)/2)]
ans = 0

for i in range(N):
    t = B[i] - M
    if t < 0:
        t = (-1) * t
    ans += t

print(ans)

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

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
  a[i] = a[i] - (i+1)
a.sort()
ans = 0
if n%2==0:
  c1 = (a[n//2-1]+a[n//2])//2
  c2 = (a[n//2-1]+a[n//2]-1)//2 + 1
  sum1 = 0
  sum2 = 0
  for i in range(n):
    sum1 += abs(a[i]-c1)
    sum2 += abs(a[i]-c2)
  ans = min(sum1, sum2)
else:
  c = a[(n-1)//2]
  for i in range(n):
    ans += abs(a[i]-c)
print(ans)

Solution (Python):
a = int(input())
ar = list(map(int,input().split(" ")))
ar = [r - (i+1) for i,r in enumerate(ar)]
br = sorted(ar)
b = br[a//2]
count = 0
for i in range(a):
    count += abs(ar[i] - b)
print(count)

Solution (Python):
N = int(input())
a = [int(n) for n in input().split(" ")]
a = [a[n] - n - 1  for n in range(N)]
a = sorted(a)
if(N%2==1):
    median = a[int(N/2)]
else:
    median = (a[int(N/2)-1] + a[int(N/2)] )/ 2
sum = 0
for i in range(N):
    sum += abs(a[i] - median)
print(int(sum))

Solution (Python):
n = int(input())
li = list(map(int,input().split()))
ans = 0

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

if n%2 == 1:
        for i in range((n-1)//2):
                ans -= li[i]
        for i in range((n+1)//2, n):
                ans += li[i]
elif n%2 == 0:
        for i in range(n//2):
                ans -= li[i]
        for i in range(n//2,n):
                ans += li[i]

print(ans)

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

def calc(mid):
  res = 0
  for i in a:
    res += abs(i-mid)
  return res

if n%2==1:
  res = calc(a[n//2])
else:
  res = float('inf')
  if (a[n//2-1]+a[n//2])%2==0:
    res = calc((a[n//2-1]+a[n//2])//2)
  else:
    mid = (a[n//2-1]+a[n//2]) // 2
    res = min(calc(mid), calc(mid+1))

print(res)

Solution (Python):
import numpy as np

N = int,input()
alist = list(map(int,input().strip().split()))

s = np.array([i for i in range(len(alist))])
slist = alist-s
slist.sort()

abs_slist = list(map(lambda x:abs(x-slist[len(slist)//2]), slist))

print(sum(abs_slist))

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

Solution (Python):
from statistics import median_low

n = (int)(input())
A = (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))

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(n):
  x=a[i]-i-1
  b.append(x)
b.sort()
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)
ans=0
for i in range(n):
  ans+=abs(b[i]-med)
print(ans)

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

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

if N % 2 == 0:
	med1 = A[N // 2 - 1]
	med2 = A[N //2]
	ans = min(sum([abs(a - med1) for a in A]), sum([abs(a - med2) for a in A]))

else:
	med = A[N // 2]
	ans = sum([abs(a - med) for a in A])
	
print(ans)

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

X = [a - i - 1 for i, a in enumerate(A)]
X.sort()
if N % 2 != 0:
    med = X[N // 2]
    ans = sum([abs(x - med) for x in X])
else:
    med1 = X[N // 2 - 1]
    med2 = X[N // 2]
    ans = min(sum([abs(x - med1) for x in X]), sum([abs(x - med2) for x in X]))
print(ans)

Solution (Python):
def calc(A, b):
    retval = 0
    for a in A:
        retval += abs(a - b)
    return retval
 
 
def main():
    N = int(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       
        c2 = -(-(left + right + right) // 3)  
        if calc(A, c1) <= calc(A, c2):
            right = c2 - 1
        else:
            left = c1 + 1
    print(calc(A, left))
 
 
if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
array = list(map(int,input().split(" ")))
arra = []
i = 0
while i < N:
  arra.append(array[i]-(i+1))
  i+=1
arra.sort()
if N%2 == 0:
  m = int((0.5)*(arra[int(N/2)-1]+arra[int(N/2)]))
else:
  m = arra[int((N-1)/2)]
j = 0
sum = 0
while j < N:
  sum+=abs(array[j]-(m+j+1))
  j+=1
print(int(sum))

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

a = sorted([aa - (i+1) for i, aa in enumerate(a)])
if n%2 == 0:
    b = (a[n//2-1] + a[n//2])//2
else:
    b = a[n//2]
    
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()))
b = []
for i in range(n):
  b.append(a[i]-i)
b.sort()
ans = 0
for i in range(n):
  ans += abs(b[i]-b[n//2])
print(ans)

Solution (Python):
import statistics
import math

N=int(input())
A_array=list(map(int,input().split()))
B_array=[]
for i in range(len(A_array)):
    i=i+1
    B_array.append(A_array[i-1]-i)
    i=i-1
mid=statistics.median(B_array)

ans=0
for i in  range(len(B_array)):
    ans+=abs(B_array[i]-mid)
print(int(ans))

Solution (Python):
import sys

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

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

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

arr.sort()

if n % 2 == 1:
    num = arr[n // 2]
else:
    num = (arr[n // 2] + arr[n // 2 - 1]) / 2
    
ans = 0

for j in range(n):
    ans += abs(arr[j-1] - num)
    
print(int(ans))

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

Solution (Python):

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


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

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














if __name__ == "__main__":
    main()

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

X = [a-(i+1) for i, a in enumerate(A)]
X.sort()
b = X[(N)//2]
print(sum([abs(x - b) for x in X]))

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

B = []
for k in range(N):
    B.append(A[k]-k-1)
B = sorted(B)

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

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

print(ans)

Solution (Python):
N = int(input())
A = [int(_) for _ in input().split()]
xs = sorted([A[_] - (_ + 1) for _ in range(N)])
print(sum([abs(_ - xs[N // 2]) for _ in xs]))

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

Solution (Python):



def main():
    from statistics import median

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

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

    b = int(median(a))
    ans = 0

    for j in range(n):
        ans += abs(a[j] - b)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


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

Solution (Python):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return 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)]))

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

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

B1=[abs(B[i]-B[N//2]) for i in range(N)]
B2=[abs(B[i]-B[N//2-1]) for i in range(N)]

print(min(sum(B1),sum(B2)))

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

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

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

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

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

Solution (Python):
n=int(input())
l=list(map(int,input().split()))
s=0
for i in range(n):
    l[i]=l[i]-i
l.sort()

if n%2==1:
    a=l[n//2]
    for i in range(n):
        s+=abs(l[i]-a)
else:
    a=(l[n//2]+l[n//2-1])//2
    for i in range(n):
        s+=abs(l[i]-a)
print(s)

Solution (Python):

N=int(input())
A=list(map(int, input().split()))
B=[0]*N
b=0
ans=0
for i in range(N):
    B[i]=A[i]-(i+1)
B_sorted=sorted(B)
if N%2==0:
    b=(B_sorted[int(N/2)]+B_sorted[int(N/2-1)])//2
else:
    b=(B_sorted[N//2])
for i in range(N):
    ans+=abs(A[i]-(b+i+1))
print(int(ans))

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]
 
lst = sorted(a - i - 1 for i, a in enumerate(A)) 

c = lst[len(lst)//2]
ret = 0
for x in lst:
    ret += abs(x - c) 
print(ret)

Solution (Python):
def 解():
    iN = int(input())
    
    aA = sorted(map(lambda x,y:x-y,map(int,input().split()),range(1,iN+1)))
    iL = len(aA)
    if iL % 2 :
        iMed = aA[(iL-1)//2]
    else:
        iMed = aA[iL//2]
    print(sum(abs(a-iMed) for a in aA))

解()

Solution (Python):
def 解():
    iN = int(input())
    aA = map(int,input().split())
    aA = sorted(map(lambda x,y:x-y,aA,range(1,iN+1)))
    iL = len(aA)
    if iL % 2 :
        iMed = aA[(iL-1)//2]
    else:
        iMed = aA[iL//2]
    iMean = sum(aA) // 2
    iBlim= min(iMed,iMean)
    iUlim= min(iMed,iMean+1)

    print(min(sum(abs(a-i) for a in aA) for i in [iMed,iMean,iMean+1]))

解()

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

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

Solution (Python):
import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())))
a2 = np.sort(a - np.arange(1,n+1))

b = int(np.median(a2))
res = sum(abs(a2-b))

print(res)

Solution (Python):
n=int(input())
A=list(map(int,input().split()))
B=[A[i-1] - i for i in range(1,n+1)]
C=sorted(B)
b=C[len(C)//2]

ans=0
for i in B:
    ans+=abs(i-b)
print(ans)

Solution (Python):

n = int(input())

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


a = sorted([a[i] - i for i in range(len(a))])


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


a = [abs(val - b) for val in a]
print(int(sum(a)))

Solution (Python):
import statistics

n = int(input())
a = input().split()
a = [int(m) for m in a]
x = []

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

x.sort()

y1 = []
y2 = []
c = 0

if n % 2 == 0:
    
    for i in range(n):
        if i <= int(n / 2) - 1:
            y1.append(x[i])
        else:
            y2.append(x[i])

    sumy1 = sum(y1)
    sumy2 = sum(y2)
    sumar = sumy2 - sumy1
    print(sumar)

w = []
z1 = []
z2 = []
d = 0

if n % 2 != 0:
    
    
    for h in range(1, n + 1):
        if h != (n + 1) / 2:
            w.append(x[h - 1])
    for i in range(n - 1):
        if i <= int((n - 1) / 2) - 1:
            z1.append(w[i])
        else:
            z2.append(w[i])
    sumz1 = sum(z1)
    sumz2 = sum(z2)
    sumar = sumz2 - sumz1
    print(sumar)

Solution (Python):
def main():
    n = int(input())
    a_list = map(lambda x: int(x), input().split(' '))
    b_list = [x - i for i, x in zip(range(1, n+1), a_list)]
    b_list.sort()
    median = 0
    if n % 2 == 0:
        median = (b_list[n//2-1] + b_list[n//2]) / 2
    else:
        median = b_list[n//2]
    result = int(sum([abs(x - median) for x in b_list]))
    print(result)

if __name__ == "__main__":
    main()

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

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

a.sort()
v = 0
if len(a) % 2 == 0:
    v1 = a[len(a)//2]
    v2 = a[len(a)//2 - 1]
    if abs(v1 + v2) == abs(v1) + abs(v2):
        v = min(v1, v2)
    else:
        v = abs(a[len(a)//2]) - abs(a[len(a)//2 - 1])
else:
    v = a[len(a)//2]
ans = 0
for i in a:
    ans += abs(i - v)
print(ans)

Solution (Python):
from statistics import median 
n = int(input())
a = list(map(int,input().split()))
ls = []
for i in range(n):
    ls.append(a[i] - i - 1)
b = median(ls)
if b % 1 == 0:
    ans = 0
    b = int(b)
    for i in range(n):
        ans += abs(a[i] - (b + i + 1))
    print(ans)
else:
    bigans = smallans = 0
    for i in range(n):
        bigans += abs(a[i] - (int(b) + i + 2))
        smallans += abs(a[i] - (int(b) + i + 1))
    print(min(bigans,smallans))

Solution (Python):
import numpy as np
N = int(input())
a = np.array(list(map(int, input().split())), dtype=int)
b = a - np.arange(1, N + 1)
b.sort()
if N % 2 == 0:
    bb = (b[N // 2 - 1] + b[N // 2]) // 2
else:
    bb = b[N // 2]
print(np.sum(np.abs(b - bb)))

Solution (Python):

from statistics import median
n = int(input())
a = list(map(int, input().split()))
b = []
_sum = 0
for i in range(n):
    b.append(a[i] - i - 1)
med = median(b)
for i in range(n):
    _sum += abs(b[i] - med)
print(int(_sum))

Solution (Python):
from statistics import median
n = int(input())
nums = list(map(int, input().split()))
bs = nums.copy()
tmp = 0

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


med = median(bs)

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

print(int(ans))

Solution (Python):
n=int(input())                    
a=list(map(int,input().split()))  
c=[]                              
ans=0                             
for i in range(n):                
    c.append(a[i]-(i+1))          
c.sort()                          
if n%2==1:                        
    b=c[(n-1)//2]                 
    for i in range(n):            
        ans+=abs(c[i]-b)          
    print(ans)                    
else:                             
    p=c[n//2]                     
    q=c[n//2+1]                   
    P=0                           
    Q=0                           
    for i in range(n):            
        P+=abs(c[i]-p)            
        Q+=abs(c[i]-q)            
    print(min(P,Q))

Solution (Python):
from statistics import median
n = int(input())
nums = list(map(int,input().split()))
bs = nums[:]
tmp =0

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

med = median(bs)

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

print(int(tmp))

Solution (Python):
from collections import Counter

def median_sum(N, A):
    median = -1
    if N%2 == 0:
        median = (A[N//2] + A[N//2 - 1]) // 2
    else:
        median = A[N//2]
    sum = 0
    for a in A:
        sum += abs(a - median)
    print(sum)
def main():
    N = int(input())
    A = [j - (i+1) for i , j in enumerate(map(int, input().split()))]
    A.sort()
    median_sum(N, A)
    
if __name__ == '__main__':
    main()

Solution (Python):


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

def sunuke(An,b):
    ret = 0
    for i,Ai in enumerate(An):
        ret += abs(Ai - (b + i + 1))

    return ret

sAn = []
for i,Ai in enumerate(An):
     sAn.append(Ai - (i+1))

sAn.sort()

if N % 2 == 0:
    
    center_idx1 = N // 2 - 1
    b1 = sAn[center_idx1]
    center_idx2 = center_idx1 + 1
    b2 = sAn[center_idx2]
    
    print(min([sunuke(An,b1),sunuke(An,b2)]))
else:
    
    center_idx = (N+1) // 2 - 1
    b = sAn[center_idx]
    
    print(sunuke(An,b))

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

new_a = [0] * n
for i in range(n):
    new_a[i] = a[i] - (i+1)
sorted_a = sorted(new_a)
b = sorted_a[n//2]
ans = 0
for i in range(n):
    ans += abs(new_a[i] - b)
print(ans)

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

s = 0
for x in a:
  s += abs(x-m)
print(s)

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
u=[]
for i in range(N):
    u.append(A[i]-i)
a=sorted(u)
if len(a)%2==0:
    p=a[len(a)//2]
else:
    p=a[len(a)//2]
ans=0
for j in range(N):
    ans+=abs(a[j]-p)
print(ans)

Solution (Python):
def f(x,i,n):
    sadness = 0
    for j in range(n):
        sadness += abs(x[j]-i)
    return(sadness)
N = int(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))

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

Solution (Python):



def main():
    from statistics import median

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

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

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

X = [abs(a - A[N//2]) for a in A]
print(sum(X))

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

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

cnt_plus = 0
cnt_minus = 0
cnt_zero = 0
for i in range(n):
    a[i] -= i + 1
    if a[i] == 0:
        cnt_zero += 1
    elif a[i] > 0:
        cnt_plus += 1
    else:
        cnt_minus += 1

ans = 0
if cnt_plus <= (cnt_minus + cnt_zero) and cnt_minus <= (cnt_plus + cnt_zero):
    for v in a:
        ans += abs(v)
elif cnt_plus > (cnt_minus + cnt_zero):
    c = [v for v in a if v > 0]
    c.sort()
    b = c[(cnt_plus - (cnt_minus + cnt_zero) - 1) // 2]
    for v in a:
        ans += abs(v - b)
else:
    c = [v for v in a if v < 0]
    c.sort(reverse=True)
    b = c[(cnt_minus - (cnt_plus + cnt_zero) - 1) // 2]
    for v in a:
        ans += abs(v - b)

print(ans)

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

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

def abs_quiz(A):
    B = [a-i-1 for i, a in enumerate(A)]
    B.sort()
    ans = sum([abs(b - B[N//2]) for b in B])
    return ans

ans = abs_quiz(A)
print(ans)

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

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

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
sum_=0
dic = {}
for i,x in enumerate(A):
    if dic.get(x-(i+1),0) == 0:
        dic[x-(i+1)] = 1
    else:
        dic[x-(i+1)] += 1
tup = sorted(dic.items(),key=lambda x:x[0])
num = 0
mid = 0

for i in range(len(tup)):
    num += tup[i][1]
    if num >= (N+1)//2:
        mid = tup[i][0]
        break

ans = 0
for i,x in enumerate(A):
    ans+=abs(x-mid-(i+1))
print(ans)

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

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

a.sort()

if n%2 == 1:
    med = a[int((n-1)/2)]
else:
    med = a[int(n/2)]
ans = 0
for i in range(n):
    ans += abs(a[i]-med)

print(ans)