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 sys

input = sys.stdin.readline

def main():
    N = int(input())
    A = [int(e) for e in input().split()]

    A2 = []
    for i, a in enumerate(A):
        A2.append(a - (i+1))
    A2.sort()
    b = 0
    if N%2 == 1:
        b = A2[int(N/2)]
    else:
        b = int((A2[int(N/2)-1] + A2[int(N/2)]) / 2)
    
    s = 0
    for a in A2:
        s += abs(a - b)
    print(s)

main()

Solution (Python):
import numpy as np
N = int(input())
A = np.array(input().split(), dtype = np.int64)

A -= np.arange(N)
A.sort()

x = A[N//2]
answer = np.abs(A - x).sum()
print(answer)

Solution (Python):
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import string
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

A = np.array(A, dtype=int)
D = A - np.arange(N)
print(int(np.abs(D - np.median(D)).sum()))

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

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

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


a.sort()
med = a[len(a) // 2]

n = 0

for ai in a:
  n += abs(ai - med)

print(n)

Solution (Python):
from statistics import median
 
n = int(input())
xs = [int(x) for x in input().split()]

ys = [x-i for i, x in enumerate(xs,1)]
m = int(median(ys))

print(sum(abs(y-m) for y in ys))

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

A = [A[i] - i - 1 for i in range(N)]
A = sorted(A)
indx = int(len(A) / 2)

b = sum([abs(a - A[indx]) for a in A])

ans = [b]

if N > 1:
    b1 = sum([abs(a - A[indx-1]) for a in A])
    ans.append(b1)

if N > 2:
    b2 = sum([abs(a - A[indx+1]) for a in A])
    ans.append(b2)

print(min(ans))

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]
ans = 0
for i in range(n):
  ans += abs(a[i]-b)
print(ans)

Solution (Python):
n = int(input())
a = [int(x)-i-1 for i,x in enumerate(input().split())]
a.sort()
if len(a)%2==1:
    md = a[len(a)//2]
    ans = 0
    for i in a:
        ans += abs(i-md)
    print(ans)
else:
    md1 = a[len(a)//2]
    md2 = a[len(a)//2-1]
    ans1 = 0
    ans2 = 0
    for i in a:
        ans1 += abs(i-md1)
        ans2 += abs(i-md2)
    print(min(ans1,ans2))

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

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

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

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

ans = sum([abs(i - b) for i in A])
print(ans)

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

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


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


c_s.sort()


med = c_s[n // 2]
d_s = [abs(c - med) for c in c_s]

ans = sum(d_s)
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
b = [0] * n

s1 = 0
s2 = 0

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

b1 = b[n//2]
b2 = b[n//2-1]

for i in range(n):
    s1 += abs(a[i] - b1 - i)

for i in range(n):
    s2 += abs(a[i] - b2 - i)

print(min(s1, s2))

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

ans = [a-i-1 for i,a in enumerate(A) ]
sorted_ans = sorted(ans)

def final_ans(ans_list , b):
    count = [abs(a-i-1-b) for i,a in enumerate(A) ]
    return(sum(count))

    

if len(sorted_ans) %2 == 1:
    mediam_place = len(sorted_ans)//2
    b = sorted_ans[mediam_place]
    print(final_ans(A , b))
else:
    mediam_place = len(sorted_ans)//2
    b = sorted_ans[mediam_place]
    val1 = final_ans(A , b)

    mediam_place = len(sorted_ans)//2 + 1
    b = sorted_ans[mediam_place]
    val2 = final_ans(A , b)
    print(min(val1 , val2))

Solution (Python):
N = int(input())
A = [int(x)-i for x,i in zip(input().split(),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)

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


B.sort()


if len(B) % 2 == 1:
  pt = B[len(B)//2]
  val = sum([abs(pt - i) for i in B])
else:
  ptA = B[len(B)//2]
  valA = sum([abs(ptA - i) for i in B])
  ptB = B[len(B)//2 + 1]
  valB = sum([abs(ptB - i) for i in B])
  if valA < valB:
    val = valA
  else:
    val = valB
print(val)

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

b = Alist[N//2]

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

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

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

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

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

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

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


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

print(ans)

Solution (Python):

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

Solution (Python):
n = int(input())
arr = map(int, input().split())
A = sorted([a-i for i, a in enumerate(arr, 1)])
print(sum(abs(a-A[n//2]) for a in A))

Solution (Python):
memo={}
def calc(A, b):
    score = memo.get(b, None)
    if not score is None:
        return score
    score = sum(abs(a-b) for a in A)
    memo[b] = score
    return score

c = 0
def findmin(A, l, u):
    global c
    c+=1
    d = (u-l)//3
    if d == 0:
        return min(calc(A, i) for i in range(l, u+1))
    left, right = l + d, u - d
    sl = calc(A, left) 
    sr = calc(A, right) 
    if sl > sr:
        return findmin(A, left, u)
    else:
        return findmin(A, l, right)

def solve(A):
    B= [0] * len(A)
    l = A[0]
    u = A[0]
    for i, a in enumerate(A):
        b = a-(i+1)
        l = min(l, b)
        u = max(u, b)
        B[i] = b
    
    return findmin(B, l, u)

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








print(solve(A))

Solution (Python):

import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
import statistics
import math

def main():
	N = int(input())
	A = list(map(int, input().split(" ")))
	
	A_tmp = []
	for i, val in enumerate(A):
		A_tmp.append(val - (i+1))
		
	hey = np.median(A_tmp)
	ans = 0
	for i, val in enumerate(A):
		ans += abs(val-(hey+(i+1)))
		
	
	print(int(ans))
	
if __name__ == "__main__":
	main()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A = [x - i - 1 for i, x in enumerate(A)]
A.sort()
mid = A[N // 2]
res1 = 0
for a in A:
    res1 += abs(a - mid)

mid += 1
res2 = 0
for a in A:
    res2 += abs(a - mid)


print(min(res1, res2))

Solution (Python):
if __name__ == '__main__':
    N= int(input())
    A_list = list(map(int, input().split()))

    B_list = []

    for i in range(len(A_list)):
        B_list.append(A_list[i]-(i+1))

    B_list = sorted(B_list)

    if len(B_list)%2 == 1:
        b = B_list[(len(B_list)-1)//2]
    else:
        b = B_list[len(B_list)//2-1]

    answer = 0
    for Bi in B_list:
        answer += abs(Bi-b)
    print(answer)

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:
    B=A.copy()
    C=A.copy()
    for i in range(n):
        s=A[n//2]
        B[i]=abs(B[i]-s)
    a=sum(B)
    for i in range(n):
        t=A[n//2-1]
        C[i]=abs(C[i]-t)
    b=sum(C)

    print(min(a,b))
else:
    B=A.copy()
    for i in range(n):
        B[i]=abs(B[i]-A[n//2])
    print(sum(B))

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

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

diff = []
for i, x in enumerate(arr, 1):
    diff.append(x - i)

diff.sort()
b = (diff[(n-1)//2] + diff[n//2]) // 2

abs_diff = 0
for i, x in enumerate(arr, 1):
    abs_diff += abs(x - (i + b))
print(abs_diff)

Solution (Python):
import numpy as np

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

ans = 0
b = np.median(A)
for i in A:
    ans += abs(i-b)

print(int(ans))

Solution (Python):
import math

N=int(input())
d=0
A=list(map(int,input().split()))
B=[]
for i in range(N):
	B.append(A[i] - (i+1))
b=sorted(B)[N//2]
f=[abs(i-b) for i in B]
print(sum(f))

Solution (Python):

import math

N = int(input())
d = 0
A = [int(i) for i in input().split()]
B = []
for i in range(N):
    B.append(A[i] - (i+1))
b = sorted(B)[N//2]

f = [abs(i-b) for i in B]
print(sum(f))

Solution (Python):
n=int(input())
a=[x-i for i,x in enumerate(map(int,input().split()))]
a.sort()
S=s=0
a_l=len(a)
a_m=(a_l+1)//2
for j in range(a_l-a_m):
    S+=a[a_m]-a[j]
for j in range(a_m-1):
    S+=a[-j-1]-a[a_m]
print(S)

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

Solution (Python):
N = int(input())
As = list(map(int,input().split()))
As1 = [a-(i+1) for i,a in enumerate(As)]
m = sorted(As1)[len(As)//2]

f = [abs(a-m) for a in As1]
print(sum(f))

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

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

A.sort()

med = A[int(N / 2)]
ans = 0
for i in range(N):
    ans += abs(A[i] - med)
print(ans)

Solution (Python):
N, *a = map(int, open(0).read().split())
x = [a[i] - i - 1 for i in range(N)]
x.sort()
print(sum([abs(v - x[N // 2]) for v in x]))

Solution (Python):

import sys
import statistics

def F(b,A):
    L = [abs(a-(b+i+1)) for i,a in enumerate(A)]
    return sum(L)

def solve(N: int, A: "List[int]"):
    L = [ a-(i+1) for i,a in enumerate(A) ]
    medl = statistics.median_low(L)
    medh = statistics.median_high(L)

    print(min(F(medl,A),F(medh,A)))
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [ int(next(tokens)) for _ in range(N) ]  
    solve(N, A)

if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a=[x-i-1 for i,x in enumerate(a)]
a.sort()
m=a[n//2]
ans=sum(abs(x-m) for x in a)
print(ans)

Solution (Python):
import statistics

def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] -= i + 1

    data.sort()
    mean = statistics.median(data)
    mean = int(round(mean, 0))

    ans = 0

    for i in range(num):
        data[i] -= mean
        ans += abs(data[i])
    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
import bisect as bi

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

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

nega_cnt = bi.bisect_left(A, 0)
posi_cnt = N - bi.bisect_right(A, 0)
zero_cnt = N - nega_cnt - posi_cnt


def calc():
    if nega_cnt + zero_cnt >= posi_cnt and posi_cnt + zero_cnt >= nega_cnt:
        return sum([abs(t) for t in A])

    if posi_cnt > nega_cnt + zero_cnt:
        idx = (posi_cnt-(nega_cnt + zero_cnt)) // 2 + 1
        a = A[-posi_cnt:][idx-1]
        return sum([abs(t-a) for t in A])

    if posi_cnt + zero_cnt < nega_cnt:
        idx = (nega_cnt-(posi_cnt + zero_cnt))//2 + 1
        a = A[:nega_cnt][-idx]
        return sum([abs(t-a) for t in A])


print(calc())

Solution (Python):
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n = f()[0]
    a = f()

    a = [a[i]-(i+1) for i in range(n)]
    a = sorted(a)
    b = a[n//2]

    print(sum([abs(i -b) for i in a]))

solve()

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

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

if n == 1:
    print(0)
elif n % 2 == 0:
    l = n // 2
    s = 0
    for i in range(l):
        s += li[i]
    print(sum(li)- 2 * s)
else:
    l = (n - 1) // 2
    s = 0
    for i in range(l):
        s += li[i]
    print(sum(li) - 2 * s - li[l])

Solution (Python):
from statistics import median
n = int(input())
a = list(map(int, input().split()))

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

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
b = sorted(a - i - 1 for i, a in enumerate(A))
med = b[N // 2]
ans = 0
for e in b:
  ans += abs(e - med)
print(ans)

Solution (Python):

import sys

import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n = readi()
p = readl()
for i in range(1, n + 1):
    p[i - 1] = p[i-1] - i
p.sort()
if n % 2 == 1:
    t = p[n // 2]
else:
    t = (p[n // 2] + p[n // 2 -1]) // 2
count = 0
for i in p:
    count += abs(i - t)
print(count)

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


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

ans = b = 0
if N%2 == 1: b = A[N//2]
else: b = (A[N//2-1]+A[N//2]) // 2
for a in A:
        ans += abs( a-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%2==1:
    ans,j=0,a[n//2]
    for i in a:ans+=abs(i-j)
else:
    ans,ans2,j,k=0,0,a[n//2],a[n//2+1]
    for i in a:
        ans+=abs(i-j)
        ans2+=abs(i-k)
    ans=min(ans,ans2)
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%2==1:
    ans=0
    for i in a:ans+=abs(i-a[n//2])
else:
    ans,ans2=0,0
    for i in a:
        ans+=abs(i-a[n//2])
        ans2+=abs(i-a[n//2+1])
    ans=min(ans,ans2)
print(ans)

Solution (Python):
from sys import stdin

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

for k in range(N):
    A[k] -= k

A.sort()


def get_pity_sum(x):
    pity_sum = 0
    for l in A:
        if A[x] - l >= 0:
            pity_sum += A[x] - l
        else:
            pity_sum += l - A[x]
    return pity_sum


if N % 2 == 1:
    c = get_pity_sum(int((N - 1) / 2))
    if N == 1:
        print(c)
    else:
        print(min(c, get_pity_sum(int((N - 1) / 2 - 1)), c + (A[int((N - 1) / 2) + 1] - A[int((N - 1) / 2)]) * 2, c + (A[int((N - 1) / 2)] - A[int((N - 1) / 2 - 1)]) * 2))
else:
    d = get_pity_sum(int(N / 2))
    print(min(get_pity_sum(int(N / 2)), d + (A[int(N / 2) + 1] - A[int(N / 2)]) * 2))

Solution (Python):

import sys


def solve(N: int, A: "List[int]"):
    for i in range(N):
        A[i] -= i + 1
    A.sort()
    tmp = A[0]
    for i in range(N):
        A[i] -= tmp
    l = -1
    r = N
    cur = sum(A)
    
    while r - l > 1:
        m = (l + r) // 2
        val = A[m]
        tmp = 0
        for a in A:
            tmp += abs(a - val)
        if tmp <= cur:
            l = m
            cur = tmp
        else:
            r = m
    val = A[l]
    ret = 0
    for a in A:
        ret += abs(a - val)

    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [ int(next(tokens)) for _ in range(N) ]  
    solve(N, A)

if __name__ == '__main__':
    main()

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

 
import statistics
median = statistics.median(l)

 
ans = 0
for x in l:
  ans += abs(x - median)
  
print(int(ans))

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

Solution (Python):


from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


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


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance





def main():
    n = intin()
    alist = intina()
    alist = [a - (i + 1) for i, a in enumerate(alist)]

    alist.sort()
    b = alist[n // 2]

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




if __name__ == '__main__':
    main()

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

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

b_index = N // 2
A.sort()

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

ans = regret(A, A[b_index])
if b_index + 1 < N:
    ans = min(ans, regret(A, A[b_index+1]))
print(ans)

Solution (Python):
import numpy as np
import statistics

n = int(input())
inputs = [int(i) for i in input().split()]
a = np.array(inputs)

z = a - np.array(range(1, n + 1))
nums = list(set(inputs))

print(int(sum(abs(z - np.ones(len(a)) * statistics.median(z)))))

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)
m = float('inf')
bs = []


if N//2-1<N:
    bs.append(A[N//2-1])
if N//2<N:
    bs.append(A[N//2])
if N//2+1<N:
    bs.append(A[N//2+1])

for b in bs:
    diff = sum(list(map(lambda x: abs(x-b),A)))
    m = min(m,diff)

print(m)

Solution (Python):
N=int(input())//2
number = 0
result = 0
a_list = []
for i in input().split():
	a_list.append(int(i)-number)
	number+=1
a_list.sort()
for i in a_list:
	result+=abs(i-a_list[N])
print(result)

Solution (Python):
N=int(input())
A=list(map(int,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):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()












B = [x-i-1 for i, x in enumerate(A)]
B.sort()

B = [abs(x-B[len(B)//2]) for x in B]

print(sum(B))

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

list_c = [list[i]-(i+1) for i in range(N)]
list_c.sort()

med = list_c[len(list_c)//2]

ans = 0

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

print(ans)

Solution (Python):

import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, A: "List[int]"):
    A = sorted([a - i for i, a in enumerate(A, 1)])
    b = A[len(A) // 2]
    return sum([abs(a - b) for a in A])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [ int(next(tokens)) for _ in range(N) ]  
    result = solve(N, A)
    print(result)

if __name__ == '__main__':
    main()

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

for i in range(n):
    listb.append(lista[i]-(1*i +1))
    
listb.sort()
med = listb[n//2]
ans = 0
for i in range(n):
    ans += abs(listb[i]-med)

    
print(ans)

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

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

mid = x[len(x)//2]
ans = 0
for i in range(1, N+1):
    ans += abs(A[i-1]-(mid+i))
print(ans)

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

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

Solution (Python):
N = int(input())
src = list(map(int,input().split()))
 
dis = [a-i-1 for i,a in enumerate(src)]
center = sorted(dis)[N//2]
 
ans = 0
for a in dis:
    ans += abs(a - center)
print(ans)

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()
b = B[(n-1)//2]
ans = 0
for i in range(n):
  ans += abs(B[i] - b) 
  
print(ans)

Solution (Python):
import math
N = int(input())
A = [int(v)-(i+1) for i,v in enumerate(input().split())]
A.sort()
num = A[N//2]
ret = 0
for i in A:
    ret += abs(i-num)

print(ret)

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

m = diff[len(diff)//2]
ans = 0

for i,l in enumerate(list):
    ans += abs(list[i]-(i+1+m))

print(ans)

Solution (Python):
def main():
	N = int(input())
	A = list(map(int, 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)


if __name__ == '__main__':
    main()

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


	mid1 = A[N//2]
	mid2 = A[N//2]
	if N >= 2:
		mid2 = A[N//2 + 1]

	ans1 = 0
	ans2 = 0
	for i in range(N):
		ans1 += abs(A[i] - mid1)
		ans2 += abs(A[i] - mid2)

	print(min(ans1, ans2))


if __name__ == '__main__':
    main()

Solution (Python):
from statistics import median

N=int(input())
A=[int(v)-k for k,v in enumerate(input().split())]
b=int(median(A))
print(sum([abs(a-b) for a in A]))

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 = [int(i) for i in input().split()]

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

B.sort()

b = B[N//2]

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

print(count)

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

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

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

Solution (Python):
import statistics


N = int(input())
A = list(map(int, input().split()))
sum_a = 0
B = [0]*len(A)
for i in range(N):
    B[i] = A[i] - i
B.sort()
sum_b = 0
b = statistics.median_low(B)
for i in range(N):
    sum_b += abs(B[i]-b)
print(sum_b)

Solution (Python):
def ans(n):
    tmp=0
    for i in range(N):
        tmp+=abs(a[i]-a[n-1])
    return tmp


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

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



print(ans(N//2) if N%2==0 else ans(N//2+1))

Solution (Python):
def ans(n):
    tmp=0
    for i in range(N):
        tmp+=abs(a[i]-a[n-1])
    return tmp


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

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

print(ans(N//2) if N%2==0 else ans(N//2+1))

Solution (Python):

import sys
import math
import itertools
INF = float("inf")


def solve(N: int, A: "List[int]"):
    A = [a-i-1 for i, a in enumerate(A)]
    A.sort()
    s = sum(A)-N*A[0]
    for i in range(len(A)):
        if i == 0:
            continue
        buf = (2*i+1-N-1)*(A[i]-A[i-1])
        if buf <= 0:
            s += buf
        else:
            break
    print(s)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, A)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]
for i in range(N):
    A[i] -= i + 1
A.sort()
sunuke = A[N // 2]
ans = 0
for a in A:
    ans += abs(a-sunuke)
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 % 2 == 0:
	center_num = A[int(N / 2)]
else:
	center_num = A[int((N - 1) / 2)]
ans = 0
for j in A:
	ans += abs(j - center_num)

print(ans)

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

minus = 0
plus = 0
for c in b:
    if c <0:
        minus +=1
    elif c >0:
        plus +=1

m1 = b[N//2]
m2 = b[0] if N==1 else b[N//2+1]
out = min(sum([abs(c-m1) for c in b]),sum([abs(c-m2) for c in b]))
print(out)

Solution (Python):
N = int(input())
a_list = [int(i) for i in input().split()]
b_list = [0 for i in range(N)]
for i in range(N):
    b_list[i] = a_list[i] - (i + 1)
b_list.sort()
b1,b2 = b_list[N//2-1], b_list[N//2]
c1,c2 = 0,0
for i in range(N):
    c1 += abs(a_list[i] - (b1 + i + 1))
for i in range(N):
    c2 += abs(a_list[i] - (b2 + i + 1))
print(min(c1,c2))

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

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

import statistics
b = int(statistics.median(a))
ans = sum([abs(i-b) for i in a])
print(ans)

Solution (Python):
import math
import statistics


N = int(input())
A = [int(i) for i in input().split()]
b = math.ceil(statistics.median([a-n for a,n in zip(A,range(1,N+1))]))
ans = [abs(a - b - n) for a,n in zip(A,range(1, N+1))]
print(sum(ans))

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

b = int(0.5 * (A_[len(A_)//2] + A_[len(A_)//2 - (len(A_)+1)%2]))

print(sum([abs(a-b) for a in A_]))

Solution (Python):
from numpy import median

N = int(input())
A = list(map(int, input().split()))
A = [a - i - 1 for i, a in enumerate(A)]
b = int(median(A))
print(sum([abs(i - b) for i in A]))

Solution (Python):
from numpy import median

N = int(input())
A = list(map(int, input().split()))
A = [a - i - 1 for i, a in enumerate(A)]
A = sorted(A)
b = int(median(A))
print(sum([abs(i - b) for i in A]))

Solution (Python):
import numpy as np


def f(_b, _a):
    return sum([abs(i - _b) for i in _a])


N = int(input())
A = list(map(int, input().split()))
A = [a - i - 1 for i, a in enumerate(A)]
A = sorted(A)
b = 0
half = len(A) // 2
if len(A) % 2:
    b = A[half]
else:
    b = int((A[half] + A[half - 1])/2)
print(f(b, A))