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


def solve():
    N = int(input())
    A = list(map(int, input().split()))
    A_i = [A[i] - i - 1 for i in range(N)]
    b = statistics.median_high(A_i)
    print(sum(abs(a - b) for a in A_i))



if __name__ == "__main__":
    solve()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= i + 1
us, vs = 0, sum(a)
uc, vc = 0, n
a.sort()
ans = vs - a[0] * n
for i in range(n):
    us += a[i]
    uc += 1
    vs -= a[i]
    vc -= 1
    b = a[i]
    ans = min(ans, uc * b - us + vs - vc * b)
print(ans)

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

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



A_median=A_[int(len(A_)/2)-10:int(len(A_)/2)+10]

def cul_ans(i):
    A_abs_=[]
    for a in A_:
        A_abs_.append(abs(a-i))
    return A_abs_

ans=10**20
for i in A_median:
    if ans>sum(cul_ans(i)):
        ans=sum(cul_ans(i))
print(ans)

Solution (Python):


N = int(input())
A = list(int(a) for a in input().split())


A_diff = []
b = 0
for i, a in enumerate(A, 1):
    tmp = a - i
    A_diff.append(tmp)

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

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

print(ans)

Solution (Python):
import numpy as np
 
N = int(input())
A = np.array(list(map(int, input().split())))
i = np.arange(1, N + 1)
 
b = int(np.median(sorted(A - i)))
 
print(np.sum(np.abs(A - (i + b))))

Solution (Python):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def solve(N, A):

    def sad(x):
        s = 0
        for i in range(N):
            s += abs(A[i] - (x + i + 1))
        return s

    min_n = np.min(A) - 10**9
    max_n = np.max(A) + 10**9

    while max_n - min_n != 1:
        tn = (min_n + max_n) // 2
        if sad(tn) < sad(tn + 1):
            max_n = tn
        else:
            min_n = tn

    return sad(max_n)


def main():

    N = in_n()
    A = np.array(readline().split(), np.int64)

    print(solve(N, A))


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', '(i8,i8[:],)')(solve)
    cc.compile()


if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    from my_module import solve
    main()

Solution (Python):
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


@njit('(i8,i8[:],i8,)', cache=True)
def sad(N, A, x):
    s = 0
    for i in range(N):
        s += abs(A[i] - (x + i + 1))
    return s


@njit('(i8,i8[:],)', cache=True)
def solve(N, A):

    min_n = np.min(A) - 10**9
    max_n = np.max(A) + 10**9

    while max_n - min_n != 1:
        tn = (min_n + max_n) // 2
        if sad(N, A, tn) < sad(N, A, tn + 1):
            max_n = tn
        else:
            min_n = tn

    return max_n


def main():

    N = in_n()
    A = np.array(readline().split(), np.int64)

    b = solve(N, A)
    print(sad(N, A, b))


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():

    N = in_n()
    A = in_nl()

    def sad(x):
        s = 0
        for i in range(N):
            s += abs(A[i] - (x + i + 1))
        return s

    def binary_search(min_n, max_n):

        while max_n - min_n != 1:
            tn = (min_n + max_n) // 2
            if sad(tn) < sad(tn + 1):
                max_n = tn
            else:
                min_n = tn

        return max_n

    b = binary_search(min(A) - 10**9, max(A) + 10**9)
    print(sad(b))


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():

    N = in_n()
    A = in_nl()

    def sad(x):
        s = 0
        for i in range(N):
            s += abs(A[i] - (x + i + 1))
        return s

    def binary_search(min_n, max_n):

        while max_n - min_n != 1:
            tn = (min_n + max_n) // 2
            if sad(tn) < sad(tn + 1):
                max_n = tn
            else:
                min_n = tn

        return max_n

    b = binary_search(min(A) - 10**9, max(A) + 10**9)
    print(sad(b))


if __name__ == '__main__':
    main()

Solution (Python):

def solve():
    B = [0]*N
    for i in range(N):
        B[i] = a[i] - (i+1)
    B.sort()
    b = B[N//2]

    scr = 0
    for l in range(N):
        scr += abs(B[l] - b)
    print(scr)

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

Solution (Python):
N=int(input())
A=list(map(int,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):
n = int(input())
a = list(map(int, input().split()))
b = [a[i] - i - 1 for i in range(n)]
median = sorted(b)[n//2]

res = 0
for v in b:
    res += abs(v - median)
print(res)

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)[N//2])

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

Solution (Python):
import sys
import math

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def main():
    N = ii()
    A = list(mi())
    for i in range(N):
        A[i] -= i+1
    median = sorted(A)[N//2]
    print(sum(abs(A[i]-median) for i in range(N)))


if __name__ == '__main__':
    main()

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

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

b = sorted(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()))
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):
n = int(input())
a_list = list(map(int,input().split()))
ans_list = []
for i in range(len(a_list)):
    ans_list.append(a_list[i] - i - 1)
import numpy as np
if len(ans_list)% 2 == 0:
    ans_list1 = sorted(ans_list)
    number1 = ans_list1[n//2]
    number2 = ans_list1[n//2 + 1]
    
    ans1 = 0
    ans2 = 0
    for i in ans_list:
        ans1 += abs(i - number1)
        ans2 += abs(i - number2)
    print(min(ans1 , ans2))
else:
    cary = ans_list
    number = int(np.median(cary))
    ans = 0
    for i in ans_list:
        ans += abs(i - number)
    print(ans)

Solution (Python):
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split(' '))))
i = np.arange(1, N + 1)

b = int(np.median(sorted(A - i)))

print(np.sum(np.abs(A - (i + b))))

Solution (Python):
from functools import lru_cache
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split(' '))))
i = np.arange(1, N + 1)

right = 10 ** 10
left = -1 * right


@lru_cache(maxsize=None)
def cost(b):
    return np.sum(np.abs(A - (i + b)))


while True:
    mid = (left + right) // 2
    c_left = cost(left)
    c_right = cost(right)
    if left == mid or right == mid:
        print(min(c_left, c_right))
        break
    elif c_left < c_right:
        right = mid
    else:
        left = mid

Solution (Python):
from functools import lru_cache
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split(' '))))
i = np.arange(1, N + 1)

left = -(10 ** 10)
right = (10 ** 10)


@lru_cache(maxsize=None)
def cost(b):
    return np.sum(np.abs(A - (i + b)))


while True:
    mid = (left + right) // 2
    c_left = cost(left)
    c_right = cost(right)
    if left == mid or right == mid:
        print(min(c_left, c_right))
        break
    elif c_left < c_right:
        right = mid
    else:
        left = mid

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

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

a.sort()
b = a[0 - -n//2 - 1]

for i in a:
    ans += abs(i - b)

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):
import statistics
N = int(input())
A = [int(a)-i-1 for i,a in enumerate(input().split(),1)]
b = statistics.median_low(A)
c = statistics.median_high(A)
d = sum(map(lambda x:abs(x-b),A))
e = sum(map(lambda x:abs(x-c),A))
print(min(d,e))

Solution (Python):

import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


def zz():
    return list(map(int, input().split()))


def z():
    return int(input())


def S():
    return input()


def C(line):
    return [input() for _ in range(line)]


N = z()
A = zz()


def get_sadness(A, b):
    sad = 0
    for i, a in enumerate(A):
        sad += abs(a - (b))
    return sad


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

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


print(get_sadness(A, b))

Solution (Python):
import sys
from itertools import combinations
def input(): return sys.stdin.readline().strip()


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


if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
l=list(map(int,input().split()))
m=sorted([a-i for i,a in enumerate(l, start=1)])
b1,b2=m[n//2],m[n//2-1]
print(min(sum([abs(a-b1) for a in m]),sum([abs(a-b2) for a in m])))

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

tmp = sorted([v-i for i, v in enumerate(nums, 1)])

b = tmp[len(tmp)//2]

ans = sum([abs(v-(b+i)) for i, v in enumerate(nums, 1)])
print(ans)

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


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


difl=[al[i-1]-i for i in range(1,n+1)]

def sadness(b):
    res=0
    for dif in difl:
        res+=abs(dif-b)
    return res
difsort=sorted(difl)
if n%2==0:
    ind1=n//2
    ind2=n//2-1
    ans=min(sadness(difsort[ind1]),sadness(difsort[ind2]))
else:
    ind=n//2
    ans=sadness(difsort[ind])
print(ans)

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

blist = []

for i in range(N):
    blist.append(alist[i]-i-1)

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

print(sum([abs(b-mid) for b in blist]))

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

blist = []
for i in range(N):
    blist.append(alist[i]-i-1)

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

ans = 0

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

print(ans)

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

Bs = []

for i in range(N):
    Bs.append(As[i]-i-1)

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

ans = 0

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

print(ans)

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

new_al = []
for i,a in enumerate(al):
    new_al.append(a-i-1)

new_al.sort()
if n%2 == 0:
    med = (new_al[n//2] + new_al[n//2-1])/2
else:
    med = new_al[n//2]

ans = 0
for a in new_al:
    ans += abs(a-med)

print(int(ans))

Solution (Python):
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split()))) - np.arange(1, n+1)
b = int(np.median(a))
print(int(np.sum(np.abs(a - b))))

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

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

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

Solution (Python):
def main():
    n = int(input())
    A = list(map(int, input().split()))
    A = sorted([a - (i + 1) for i, a in enumerate(A)])
    b = A[n // 2]
    print(sum([abs(a - b) for a in A]))
if __name__ == '__main__':
    main()

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

Solution (Python):
import statistics
n = int(input())
a = list(map(int,input().split()))
A = [0]*n
sad = 0
for i in range(1,n+1):
    A[i-1] = a[i-1]-i

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

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):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
A = LIST()

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

print(sum([abs(x - A[len(A)//2]) for x in A]))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
A = LIST()

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

b = a[len(a)//2]

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

Solution (Python):
import numpy as np

n = int(input())
a = np.array([int(i) for i in input().split()])
b = np.arange(1,n+1, dtype=int)
a -= b 
a -= int(np.median(a))
print(sum(np.abs(a)))

Solution (Python):
import numpy
s = list(map(int, input().split()))
n=s[0]
s = list(map(int, input().split()))
for i in range(n):
    s[i]=s[i]-i-1
s=numpy.array(s)
i=numpy.median(s)
a=numpy.sum(numpy.abs(s-i))
print(int(a))

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

b = B[len(B) // 2]
ans = 0
for i, a in enumerate(A):
    ans += abs(a - (b + (i+1)))
print(ans)

Solution (Python):
n = int(input())
g = map(int, input().split())
a = [v-(i+1) for i,v in enumerate(g)]
a.sort()
b = a[len(a)//2]
print(sum(map(lambda x:abs(x-b), a)))

Solution (Python):
import numpy as np
n = int(input())
lst = [(a-e-1) for e,a in enumerate(list(map(int,input().split())))]
b = int(np.median(lst))
ans = 0
for a in lst:
    ans += abs(a-b)
print(ans)

Solution (Python):
n=int(input())
l=list(map(int,input().split()))
for i in range(n):
  l[i]=l[i]-(i+1)
l.sort()
if n%2==0:
  b=(l[n//2-1]+l[n//2])//2
else:
  b=l[n//2]
ans=0
for i in range(n):
  ans+=abs(l[i]-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()
c = a[n//2]
if n % 2 == 0:
    c = int((a[n//2] + a[n//2-1]) // 2 + 0.5)
ans = 0
for i in range(n):
    ans += abs(a[i] - c)
print(ans)

Solution (Python):
import math

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


def calc(b):
    total = 0
    for i in range(1, N+1):
        ai = A[i-1]
        total += abs(ai - i - b)
    return total


B = list(sorted([A[i-1]-i for i in range(1, N+1)]))
if N % 2 == 0:
    
    median = (B[(N-1)//2] + B[N//2]) / 2
    b1 = math.floor(median)
    b2 = math.ceil(median)
    print(min(calc(b1), calc(b2)))
else:
    b = B[N//2]
    print(calc(b))

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

if N == 1:
  print(0)
  exit()
B = sorted(B, reverse=True)
cs = B[:]
for i in range(N-1):
  cs[i+1] += cs[i]

ans = float('inf')
tmp = 0
for b in B:
  tmp += abs(b)
ans = min(ans, tmp)

for i in range(1, N):
  b = B[i]
  left = b*(i)-cs[i-1]
  right = -1*(b*(N-i-1)-(cs[-1]-cs[i]))
  ans = min(ans, abs(left)+abs(right))
print(ans)

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

Solution (Python):
import math

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
  a[i] -= i+1
a = sorted(a)
b1 = math.floor(sum(a)/n)
b2 = math.ceil(sum(a)/n)
b3 = b1-1
b4 = b2+1
b5 = a[n//2]
b6 = a[n//2-1]

ans1 = 0
ans2 = 0
ans3 = 0
ans4 = 0
ans5 = 0
ans6 = 0
for i in range(n):
  ans1 += abs(a[i]-b1)
  ans2 += abs(a[i]-b2)
  ans3 += abs(a[i]-b3)
  ans4 += abs(a[i]-b4)
  ans5 += abs(a[i]-b5)
  ans6 += abs(a[i]-b6)
print(min(ans5, ans6))

Solution (Python):
import math

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
  a[i] -= i+1
a = sorted(a)
b1 = math.floor(sum(a)/n)
b2 = math.ceil(sum(a)/n)
b3 = b1-1
b4 = b2+1
b5 = a[n//2]
b6 = a[n//2-1]

ans1 = 0
ans2 = 0
ans3 = 0
ans4 = 0
ans5 = 0
ans6 = 0
for i in range(n):
  ans1 += abs(a[i]-b1)
  ans2 += abs(a[i]-b2)
  ans3 += abs(a[i]-b3)
  ans4 += abs(a[i]-b4)
  ans5 += abs(a[i]-b5)
  ans6 += abs(a[i]-b6)
print(min(int(ans1), int(ans2), int(ans3), int(ans4), ans5, ans6))

Solution (Python):
n = int(input())
B = list(a-i-1 for i,a in zip(range(n), map(int,input().split())))
B.sort()
ans = sum(B[n//2 + (n%2) :]) - sum(B[: n//2]) 
print(ans)

Solution (Python):
n = int(input())
B = list(a-i for i,a in zip(range(1,n+1), map(int,input().split())))
B.sort()
l = r = B[n//2] 
if n%2 == 0: l -= 1 
ans_l, ans_r = 0, 0
for bi in B:
    ans_l += abs(bi-l)
    ans_r += abs(bi-r)
print(min([ans_l, ans_r]))

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()
r = B[n//2] 
l = B[n//2] if n%2 else B[n//2-1] 



ans_l = 0
ans_r = 0
for bi in B:
    ans_l += abs(bi-l)
    ans_r += abs(bi-r)
print(min([ans_l, ans_r]))

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 = list(map(int, input().split()))
b = [x[1] - x[0] for x in enumerate(A,1)]
b.sort()
if N % 2 == 1:
    median = b[N//2]
else:
    median = (b[(N//2)-1]+b[N//2]) // 2
c = [abs(x-median) for x in b]
print(sum(c))

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

Solution (Python):
from statistics import median

n = int(input())
a = list(map(int,input().split()))
b = [a[i]-(i+1) for i in range(n)]
m = median(b)
c = [abs(b[i] - m) for i in range(n)]
print(int(sum(c)))

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

b.sort()


bi = b[n//2]
s = 0
for i in range(n):
    s += abs(a[i] - (i + 1 + bi))


print(s)

"""
for j in range(3):
    bi = b[(n//2+j)%n]
    s = 0
    for i in range(n):
        s += abs(a[i] - (bi + i + 1))
    
    ans = min(ans, s)
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()
idx= n//2
bi = b[idx]
ans = 0
for i in range(n):
    ans += abs(a[i] - (i + 1 + bi))
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,now=sum(a)-2*a[0]+2*a[0]-a[0]*n,sum(a)-2*a[0]+2*a[0]-a[0]*n
for i in range(1,n):
    now=now-(2*(i)*a[i-1]-n*a[i-1])+(-2*a[i]+2*(i+1)*a[i]-n*a[i])
    m=min(now,m)
    
print(m)

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

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

idx = n//2

b = box[idx]

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

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
na = [0]*n
for i in range(n):
    na[i] = a[i]-(i+1)
na.sort()
med = n//2-1
med1 = med+1
ans = 0
ans1 = 0
for i in range(n):
    ans += abs(na[i]-na[med])
    ans1 += abs(na[i]-na[med1])
print(min(ans, ans1))

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N = I()
A = IL()

AA = [A[i]-i for i in range(N)]
if N%2 == 0:
  AA.sort()
  ANS1 = [abs(AA[i]-AA[N//2-1])  for i in range(N)]
  ANS2 = [abs(AA[i]-AA[N//2])  for i in range(N)]
  print(min(sum(ANS1),sum(ANS2)))
else:
  AA.sort()
  ANS = [abs(AA[i]-AA[N//2])  for i in range(N)]
  print(sum(ANS))

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

b=[x-i-1 for i,x in enumerate(a)]
"""
b=[]
for///:
    y.append///
"""
m=int(median(b))
print(sum(abs(y-m) for y in b))

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=sorted(b)
mid=b[n//2]
ans=0
for i in range(n):
    ans+=abs(b[i]-mid)
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()
if N%2==1:
    W = B[N//2]
    out = 0
    for i in range(N):
        out += abs(B[i]-W)
else:
    X = B[N//2-1]
    Y = B[N//2]
    Z = X+Y
    if Z%2==0:
        W = Z//2
        out = 0
        for i in range(N):
            out += abs(B[i]-W)
    else:
        W1 = Z//2
        out1 = 0
        for i in range(N):
            out1 += abs(B[i]-W1)
        W2 = Z//2
        out2 = 0
        for i in range(N):
            out2 += abs(B[i]-W2)
        out = min(out1,out2)
print(out)

Solution (Python):

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array(lr(), dtype=np.int32)
A -= np.arange(1, N+1)
answer = np.abs(A - int(np.median(A))).sum()
print(answer)

Solution (Python):

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array(lr())
A -= np.arange(1, N+1)
A.sort()

def check(i):
    ret = np.abs(A - A[i]).sum()
    return ret

answer = min(check(0), check(-1))
left = 0; right = N-1
l_mid = (left*2 + right) // 3
r_mid = (left + right*2) // 3
while abs(right-left) > 2:
    l_mid = (left*2 + right) // 3
    r_mid = (left + right*2) // 3
    if check(l_mid) < check(r_mid):
        right = r_mid
    else:
        left = l_mid

cand = min(check(l_mid), check(r_mid))
answer = min(answer, cand)
print(answer)

Solution (Python):
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
b = [0]*n
for i in range(n):
    sa = a[i] - (i+1)
    b[i] = sa
b.sort()
idx = int(n/2) 

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

Solution (Python):
import statistics
def resolve():
	n = int(input())
	a = list(map(int, input().split()))
	seq = []
	for i in range(1, n+1):
		seq.append(i-a[i-1])
	seq = sorted(seq)
	m = int(statistics.median(seq))
	ans = 0
	for i in seq:
		ans += abs(i-m)
	print(ans)
resolve()

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

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

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

ans = 0
for i in range(n):
    ans += abs(ami[i] - ami[n // 2])
print(ans)

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

ans = 0
if n % 2 == 1:
    for i in range(n):
        ans += abs(ami[i]-ami[n//2])
else:
    cnt1 = 0
    cnt2 = 0
    for i in range(n):
        cnt1 += abs(ami[i]-ami[n//2])
        cnt2 += abs(ami[i]-ami[n//2-1])
    ans = min(cnt1,cnt2)
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18


n = I()
A = LI()
B = [A[i]-i-1 for i in range(n)]
B.sort()
mid = B[n//2]
mid2 = B[(n-1)//2]
def sad(b, n):
    ret = 0
    for i in range(n):
        ret += abs(B[i]-b)
    return ret

ans = min(sad(mid, n), sad(mid2, n))
print(ans)

Solution (Python):

import math

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A = [A[i] - i - 1 for i in range(N)]
    A.sort()
    diff = A[(N-1)//2]
    print(sum([abs(a-diff) for a in A]))


if __name__ == "__main__":
    main()