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
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


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

min_ = 10**20

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

B.sort()

Bplus = sum(B)
Bminus = 0
for n in range(N//2):
    sad = Bplus - Bminus
    sad += (2*n-N)*B[n]
    min_ = min(sad, min_)

    Bplus -= B[n]
    Bminus += B[n]

for n in range(N//2, N):
    sad = Bplus - Bminus
    sad += (2*n-N)*B[n-1]
    min_ = min(sad, min_)

    Bplus -= B[n]
    Bminus += B[n]

print(min_)

Solution (Python):
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]


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



def check(b):
    res = 0
    for i in range(N):
        res += abs(A[i] - (b+(i+1)))
    
    return res

def ternarySearchInt(small, big):
    
    if small == big:
        return small
    elif big - small == 1:
        if check(small) <= check(big):
            return small
        else:
            return big

    def func(small, big):
        midl = (big + small) // 2
        midr = midl + 1
        if big - small == 2:  
            mid = midl
            if check(small) <= check(mid):
                if check(small) <= check(big):
                    return small
                else:
                    return big
            else:
                if check(mid) <= check(big):
                    return mid
                else:
                    return big
        else:
            if check(midl) >= check(midr):
                return func(midl, big)
            else:
                return func(small, midr)
    return func(small, big)

ans = ternarySearchInt(-int(1e9), int(1e9))

print(check(ans))

Solution (Python):

import statistics

N = int(input())
A_suc = [int(a) for a in input().split()]
B_suc = [i + 1 for i in range(len(A_suc))]
C_suc = [i - j for i, j in zip(A_suc, B_suc)]
median = int(statistics.median(C_suc))
D_suc = [abs(i - median) for i in C_suc]
print(sum(D_suc))

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

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

b = sorted(a)[int(n / 2)]
print(sum(map(lambda x: abs(x - b), a)))

Solution (Python):

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

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

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

print(sum([abs(B[i] - b) for i in range(N)]))

Solution (Python):
def f(A, b):
    return sum(abs(a - (b + i + 1)) for i, a in enumerate(A))
N = int(input())
A = [int(x) for x in input().split()]
left, right = -10**9, 10**9
while left + 2 < right:
    diff = (right - left) // 3
    m1 = left + diff
    m2 = m1 + diff
    if f(A, m1) > f(A, m2):
        left = m1
    else:
        right = m2
print(min(f(A, i) for i in range(left, right + 1)))

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

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

print(ans)

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

a = (len(A)+1)//2-1
b = len(A)//2

print(sum(A[b:])-sum(A[:a+1]))

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

Solution (Python):
N = int(input())
a = list(map(int,input().split()))
for i in range(len(a)):
  a[i] = a[i]-i-1
a = sorted(a)
import numpy as np
a = np.array(a)
b = np.median(a)
a = a-b
a = abs(a)
print(int(sum(a)))

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

Solution (Python):
from statistics import median
def inpl(): return map(int, input().split())
N = int(input())
A = [j-i for i, j in enumerate(inpl(), start=1)]
m = median(A)
print(int(sum([abs(a-m) for a in A])))

Solution (Python):
n = int(input())
alst = list(map(int, input().split()))
for i in range(n):
  alst[i] -= (i + 1)
alst.sort()
c1 = alst[n // 2]
c2 = alst[n // 2 - 1]

ans = min(sum([abs(a - c1) for a in alst]), sum([abs(a - c2) for a in alst]))
print(ans)

Solution (Python):

import sys

input=sys.stdin.readline

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

a.sort()
ans=0
median=a[n//2]
for i in range(n):
    ans+=abs(a[i]-median)
print(ans)

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

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

N = read()
A = reads()

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

med = B[N//2]
ans = sum(abs(b - med) for b in B)

print(ans)