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
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

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

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    
    N = Scanner.int()
    A = Scanner.map_int()
    A = [a - (i + 1) for i, a in enumerate(A)]
    A.sort()
    if N % 2 == 1:
        m = A[N // 2]
        print(sum([abs(a - m) for a in A]))
    else:
        m = A[N // 2 - 1]
        ans = sum([abs(a - m) for a in A])
        m = A[N // 2]
        ans = min(ans, sum([abs(a - m) for a in A]))
        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+1)

A.sort()

med = [A[n//2]]
if n % 2 == 0:
    med.append(A[n//2 - 1])

ans = 1000000000000000000
for m in med:
    cnt = 0
    for a in A:
        cnt += abs(a-m)
    ans = min(ans, cnt)

print(ans)

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

b = A[(N - 1)//2]
ans = sum([abs(a-b) for a 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, 1)]

b = statistics.median(A)
ans = int(sum([abs(a-b) for a 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()
dis = A[-(-N // 2) - 1]
ans = 0
for i in range(N):
    ans += abs(A[i] - dis)
print(ans)

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

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

Bn = sorted([An[i] - (i + 1) for i in range(N)])

if N % 2 ==1:
  median = Bn[N//2]
  error = 0
  for n in range(N):
    error += abs(Bn[n] - median)
  print(error)
else:
  median1 = (Bn[N//2] + Bn[N//2-1])//2
  median2 = (Bn[N//2] + Bn[N//2-1] + 1) //2
  error1 = 0
  error2 = 0
  for n in range(N):
    error1 += abs(Bn[n] - median1)
    error2 += abs(Bn[n] - median2)
  print(min(error1, error2))

Solution (Python):



from math import floor

def main():
  n = int(input())
  la = list(map(int, input().split()))
  la = [a-i for i, a in enumerate(la, 1)]
  la.sort()
  if len(la) == 1:
    print(0)
  else:
    ix = (len(la)-1) // 2
    print(min([sum(map(lambda x: abs(x-la[ix+i]), la)) for i in range(2)]))

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.sort()
if (N % 2 == 1):
    b = B[N//2]
else:
    b = round((B[N//2]+B[N//2-1])/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()))
B = [0]*N
for i in range(N):
    B[i] = A[i] - i
B.sort()

res = 0
x = B[N//2]

for i in range(N):
    res += max(x - B[i], -x + B[i])

print(res)

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

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

Solution (Python):


n = int(input().rstrip())

numbers = list(map(int, input().rstrip().split(" ")))

tmp = list(sorted([ [numbers[i] - i, i] for i in range(n)]))


ans = 1000000000 * n

target = tmp[int(n/2)][0]
if n % 2 == 0:
    target = int((tmp[int(n/2)][0]+tmp[int(n/2)-1][0])/2)

ans = [abs(numbers[i] - (target + i)) for i in range(n)]
print(sum(ans))

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

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

if N % 2 == 1:
    ans = 0
    for i in A:
        ans += abs(i - A[N//2])
else:
    ans = 0
    ansk = 0
    for i in A:
        ans += abs(i - A[N//2])
        ansk += abs(i - A[N//2-1])
    ans = min(ans, ansk)

print(ans)

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

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

if N % 2 == 1:
    ans = 0
    for i in A:
        ans += abs(i - A[N//2])
else:
    ans = 0
    ansk = 0
    a = (A[N//2] + A[N//2-1]) // 2
    for i in A:
        ans += abs(i - a)
        ansk += abs(i - a-1)
    ans = min(ans, ansk)

print(ans)

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

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

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

Solution (Python):
import statistics

def solve():
    N = int(input())
    A = list(map(int,input().split()))
    B = list(A[i]-(i+1) for i in range(N))
    B.sort()
    b = int(statistics.median(B))
    
    ans = 0
    for i in range(1,N+1):
        ans += abs(A[i-1]-(b+i))
    print(ans)
    
    

if __name__ == "__main__":
    solve()

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

A = sorted([A[i] - i - 1 for i in range(N)])
ans = sum(abs(A[i] - A[N // 2]) for i in range(N))

print(ans)

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

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

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

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

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

def geta(b):
    un=0
    for i in range(n):
        un+=abs(sub[i]-b)
    return un

med = sub[n//2]
ans=10**20
for i in range(med-1,med+1):
    num = geta(i)
    if ans > num:
        ans=num
print(ans)

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

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

def geta(b):
    un=0
    for i in range(n):
        un+=abs(sub[i]-b)
    return un

med = sub[n//2]
ans=geta(med)
print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

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

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


if __name__ == '__main__':
    main()

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

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

A.sort()

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

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

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


def sadness(b):
  sad = 0
  for i, e in enumerate(a):
    i += 1
    sad += abs(e - (b + i))
  return sad


d = []
for i, e in enumerate(a):
  i += 1
  d.append(e - i)

d.sort()

if len(d) % 2 == 1:
  print(sadness(d[len(d) // 2]))
else:
  print(min(sadness(d[len(d) // 2]), sadness(d[len(d) // 2 + 1])))

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


def sadness(b):
  sad = 0
  for i, e in enumerate(a):
    i += 1
    sad += abs(e - (b + i))
  return sad


left, right = -10**9, 10**9 + 1
while right - left > 1:
  mid = (left + right) // 2

  if sadness(mid) > sadness(mid + 1):
    left = mid
  else:
    right = mid




print(min(sadness(left), sadness(right)))

Solution (Python):
from statistics import median
n=int(input())
a=list(map(int,input().split()))
mid=0
l=[]
for i in range(n):
    l+=[a[i]-i-1]

mid=median(l) if n%2!=0 else sorted(l)[n//2]
ans=0
for i in range(n):
    ans+=abs(a[i]-(mid+i+1))

print(int(ans))

Solution (Python):
from statistics import median
n=int(input())
a=list(map(int,input().split()))
mid=0
l=[]
for i in range(n):
    l+=[a[i]-i-1]

mid=median(l)
ans=0
for i in range(n):
    ans+=abs(a[i]-(mid+i+1))

print(int(ans))

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

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

a_sum=[a[0]]
a_minus_sum=[-a[0]]

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

ans=min(a_sum[-1]-a[0]*n,a_minus_sum[-1]+a[-1]*n)

for g in range(1,n-1):
    ans=min(a[g]*(-n+2*g+1)+a_sum[-1]-a_sum[g]+a_minus_sum[g-1],ans)

print(ans)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7


def main():
    
    N = Scanner.int()
    A = Scanner.map_int()
    B = [0] * N
    for i in range(N):
        B[i] = A[i] - (i+1)
    B.sort()

    a, b = B[N//2-1], B[N//2]
    ans = 0
    tmp = 0
    for i in range(N):
        ans += abs(A[i] - (a + i + 1))
        tmp += abs(A[i] - (b + i + 1))
    ans = min(ans, tmp)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import collections 

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

c = N // 2
a = A[c]
ans = sum([abs(i - a) for i in A])

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

Solution (Python):
def solve():
    N, *A = map(int, open(0).read().split())

    B = [0] * N
    for i, a in enumerate(A):
        B[i] = a - (i + 1)
    B.sort()

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

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


if __name__ == '__main__':
    solve()

Solution (Python):
def solve():
    N, *A = map(int, open(0).read().split())

    B = [0] * N
    for i, a in enumerate(A):
        B[i] = a - (i + 1)
    B.sort()

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

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


if __name__ == '__main__':
    solve()

Solution (Python):
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = list(map(int, readline().split()))
    for i in range(n):
        a[i] -= i + 1
    a.sort()
    t = 0
    for v in a:
        t += abs(a[n // 2] - v)
    print(t)


if __name__ == '__main__':
    solve()

Solution (Python):
import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())))
a = [v - i - 1 for i, v in enumerate(a)]
b = sorted(a)[n // 2]
print(np.sum([abs(a - b)]))

Solution (Python):
import statistics
N = int(input())
A = list(map(int,input().split()))
A2 = sorted([A[i]-i-1 for i in range(N)])
med = int(statistics.median(A2))
med2 = med+1
sum1 = 0
sum2 = 0
for i in range(N):
    sum1 += abs(A2[i]-med)
    sum2 += abs(A2[i]-med2)
print(min(sum1,sum2))

Solution (Python):
def examC():
    N = I()
    A = LI()
    Ad = [0]*N
    for i in range(N):
        Ad[i] = A[i]-(i+1)
    Ad.sort()

    b = Ad[N//2]
    ans = 0
    for a in Ad:
        ans +=abs(a-b)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = 10**18

if __name__ == '__main__':
    examC()

Solution (Python):
n=int(input())
al=list(map(int,input().split()))
t=[]
for i in range(n):
    t.append(al[i]-(i+1))
t=sorted(t)
if n%2==0:
    v=(t[n//2-1]+t[n//2])//2
else:
    v=t[n//2]
ans=0
for i in t:
    ans+=abs(i-v)
print(ans)

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

Solution (Python):
n=int(input())
al=list(map(int,input().split()))
t=[]
for i in range(n):
    t.append(al[i]-(i+1))
t=sorted(t)
if n%2==0:
    v=(t[n//2-1]+t[n//2])//2
else:
    v=t[n//2]
ans=0
for i in t:
    ans+=abs(i-v)
print(ans)

Solution (Python):
import numpy as np
from statistics import median

N = int(input())
A = list(map(int, input().split()))
list_n = list(range(1, (N+1), 1))
A_tmp = np.array(A)
list_n_tmp = np.array(list_n)
list_diff = A_tmp - list_n_tmp
b = median(list_diff)
Xtmp = 0

for n in range(0, N, 1):
    Xtmp += abs(A[n] - (b + n + 1))

print(int(Xtmp))

Solution (Python):
import numpy as np
import math

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

base = np.arange(N, dtype=int) + 1
tmp = A - base
b = math.floor(np.median(tmp))
ans = np.abs(tmp - b).sum()
print(ans)

Solution (Python):
import numpy as np
from statistics import median

N = int(input())
A = list(map(int, input().split()))
list_n = list(range(1, (N+1), 1))
A_tmp = np.array(A)
list_n_tmp = np.array(list_n)
list_diff = A_tmp - list_n_tmp
b = median(list_diff)
Xtmp = 0

for n in range(0, N, 1):
    Xtmp += abs(A[n] - (b + n + 1))

print(int(Xtmp))

Solution (Python):
import sys
import statistics                                                                                                                       
readInt = lambda f=sys.stdin: [int(i) for i in f.readline().split()];
n = readInt()[0]
A = readInt()
C = [a - i for i, a in enumerate(A)]
b = int(statistics.median(C))
ans = sum([abs(c - b) for c in C])

print(ans)

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

print(s)

Solution (Python):
import math

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)
cnt=B[(N//2)]

s=0
for i in range(N):
    s+=abs(B[i]-cnt)

print(s)

Solution (Python):
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    for i in range(n):
        a[i] -= i + 1
    a.sort()
    t = a[n // 2]
    mt = 0
    for v in a:
        mt += abs(t - v)
    print(mt)


if __name__ == '__main__':
    solve()

Solution (Python):
import numpy as np
import math

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

tmp = A - base
b = math.floor(np.median(tmp))
ans = tmp - b
print(np.abs(ans).sum())

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

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

def sadness(b):
    global A
    s = 0
    for i, a in enumerate(A):
        s += abs(a-b)
    return s

print(sadness(sA[len(A)//2]))

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

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

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

print(ans)

Solution (Python):
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = list(map(int, readline().split()))
    for i in range(n):
        a[i] -= i + 1
    a.sort()
    t1 = 0
    t2 = 0
    for i in range(n):
        t1 += abs(a[i] - a[n//2])
        t2 += abs(a[i] - a[n//2 - 1])
    print(min(t1, t2))


if __name__ == '__main__':
    solve()

Solution (Python):
import numpy as np
N=int(input())
A=[int(i) for i in input().split()]
A=[A[i]-i for i in range(N)]

b=np.median(A)
K=[abs(A[i]-b) for i in range(N)]
print(int(sum(K)))

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=[]
if N%2==1:
    b.append(B[(N+1)//2-1])
elif N%2==0:
    b.append(B[N//2-1])
    b.append(B[N//2])

ans=[]
for i in b:
    sum=0
    for j in range(N):
        sum+=abs(B[j]-i)
    ans.append(sum)

print(min(ans))

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

sum_A = [0, 0]
for i in range(N):
    sum_A[0] += abs(A[i] - A[N // 2])
sum_2 = 0
for i in range(N):
    sum_A[1] += abs(A[i] - A[N // 2 + 1])
print(min(sum_A))

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

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

Solution (Python):
n=int(input())
a1=list(map(int,input().split()))
a2=sorted([a1[i-1]-i for i in range(1,n+1)])
if len(a2)%2==0:
    m1=a2[len(a2)//2]
    m2=a2[len(a2)//2-1]
else:
    m1=a2[len(a2)//2]
    m2=m1
ans1,ans2=0,0
for i in a2:
    ans1+=abs(i-m1)
    ans2+=abs(i-m2)
print(min(ans1,ans2))

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


aaa=sorted(aa)
if len(aaa)%2==0:
    m1=aaa[len(aaa)//2]
    m2=aaa[len(aaa)//2-1]
else:
    m1=aaa[len(aaa)//2]
    m2=m1
ans1,ans2=0,0
for i in aa:
    ans1+=abs(i-m1)
    ans2+=abs(i-m2)
print(min(ans1,ans2))

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:
    b = a[(n-1)//2]
else:
    b = a[n//2]

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

Solution (Python):
import math
import copy
import sys
import bisect
input = sys.stdin.readline

def main():
    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()
    if n%2==1:
        mid=b[(n-1)//2]
        ans=0
        for i in range(n):
            ans+=abs(b[i]-mid)
        print(ans)
    else:
        mid = (b[(n//2)-1]+b[(n//2)])//2
        ans=float('inf')
        for i in range(mid,mid+2):
            ans1=0
            for j in range(n):
                ans1+=abs(b[j]-i)
            ans=min(ans1,ans)
        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+1)

A.sort()

temp1=A[N//2]
temp2=A[N//2-1]

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

ans2=0
for i in range(N):
    ans2+=abs((A[i])-temp2)
    
print(min(ans1,ans2))

Solution (Python):
def total(inlist,k):
    print(sum([ abs(i-k) for i in inlist ]))
    return
n = int(input())
a_list = [ int(v) for v in input().split() ]
a_list = [ v-i for i, v in enumerate(a_list,1) ]
a_list.sort()

total(a_list,a_list[n//2])

Solution (Python):


n = int(input())
a = map(int, input().split())
a = tuple(sorted(x - i for i, x in enumerate(a, 1)))


b = a[n // 2]  

ans = sum(abs(x - b) for x in a)
print(ans)

Solution (Python):

import sys

def calc(A, b):
    c = 0
    for i, x in enumerate(A):
        c += abs(x - (b + (i+1)))
    return c

def solve(N, A):
    B = []
    for i, a in enumerate(A):
        B.append(a - (i+1))
    return calc(A, sorted(B)[N // 2])

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)]  
    print(solve(N, A))

if __name__ == '__main__':
    main()

Solution (Python):
import copy
N=int(input())
lst=list(map(int,input().split()))
lst2=copy.copy(lst)
for i in range(1,N+1):
  lst2[i-1]-=i
lst2=sorted(lst2)
b=lst2[N//2]
ans=0
for i in range(N):
  ans+=abs(lst[i]-(b+i+1))
print(ans)

Solution (Python):
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
sub = np.array(list(range(n)))
b = sorted(a - sub)[n // 2]
print(sum(abs(a - (b + sub))))

Solution (Python):
import sys
n = int(input())
a_ls = [int(i) for i in sys.stdin.readline().split()]
a_ls = [i - j - 1 for j, i in enumerate(a_ls)]
base = sorted(a_ls)[n // 2]
print(sum([abs(a - base) for a in a_ls]))

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

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

sum = 0
for j in range(len(A)):
    sum += abs(A[j]-(b+j+1))

print(sum)

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

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

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

A.sort()
if N%2==1:
  ma=A[N//2]
  print(sum([abs(i-ma) for i in A]))
else:
  ma=[A[N//2]-1,A[N//2]]
  a=[]
  for m in ma:
    a.append(sum([abs(i-m) for i in A]))
  print(min(a))

Solution (Python):
from statistics import median
N = int(input())
A = list(map(int, input().split()))
B = [a-i for i, a in enumerate(A)]
m = int(median(B))
print(sum(abs(b-m) for b in B))

Solution (Python):
n=int(input())
a=sorted([x-i for i,x in enumerate(list(map(int,input().split())))])
if n%2==1:
  print(sum([abs(x-a[n//2]) for x in a]))
else:
  print(min(sum([abs(x-a[n//2]) for x in a]),sum([abs(x-a[n//2+1]) for x in a])))

Solution (Python):
n = int(input())
an = sorted([int(j)-(i+1) for i,j in enumerate(input().split())])
print(sum(abs(i - an[len(an)//2]) for i in an))

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

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

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

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

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

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

med = A[N//2]

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

Solution (Python):
import numpy as np

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

A_rot = np.array(list(enumerate(A, 1))).T.astype(np.float128)
theta = np.pi / 4
R = np.array([[np.cos(theta), np.sin(theta)], [-np.sin(theta), np.cos(theta)]], dtype=np.float128)
A_rot = np.dot(R, A_rot).T
loss = np.abs(A_rot[:, 1] - np.median(A_rot[:, 1])).sum()
print(int(np.round(np.sqrt(2) * loss)))

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


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

if N % 2 == 1:
  print(calc(A[N//2]))
else:
  print(min(calc(A[N//2]),calc(A[(N-1)//2])))

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

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

m=A[(N-N%2)//2]


A=list(map(lambda x: abs(x-m),A))
print(sum(A))

Solution (Python):
n = int(input())
a = [int(x) - i for i, x in enumerate(input().split())]
a.sort()
mid = a[n//2]
print(sum([abs(mid - a[i]) for i in range(n)]))

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

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

if N%2==0:
  ans = B[N//2]
  ans2= B[N//2 -1]
  temp=0
  for j in range(N):
    temp+= abs(B[j] - ans)
  temp2=0
  for j in range(N):
    temp2+= abs(B[j] - ans2)
  ans= min(temp,temp2)
else:
  ans = B[N//2]
  temp=0
  for j in range(N):
    temp+= abs(B[j] - ans )
  ans=temp
print(ans)

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

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

if N%2==0:
  ans = B[N//2]
  ans2= B[N//2 -1]
  temp=0
  for j in range(N):
    temp+= abs(B[j] - ans)
  temp2=0
  for j in range(N):
    temp2+= abs(B[j] - ans2)
  ans= min(temp,temp2)
else:
  ans = B[N//2]
  temp=0
  for j in range(N):
    temp+= abs(B[j] - ans )
  ans=temp
print(ans)

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
a = [int(i) for i in readline().split()]
a = [c-(i+1) for i,c in enumerate(a)]

a.sort()
m = a[n//2]

print(sum(abs(i-m) for i in a))

Solution (Python):



import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
b = [a[i] - (i+1) for i in range(n)]
b.sort()
if n % 2:
    c = b[n//2]
else:
    c = (b[n//2]+b[n//2-1])//2
ans = 0
for i in range(n):
    ans += abs(a[i] -(c + i+1))
print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A = [A[n]-n for n in range(N)]
A.sort()
if N % 2 == 1:
  A = [abs(a - A[N//2]) for a in A]
  ans = sum(A)
else:
  temp = A
  A = [abs(a - A[N//2]) for a in A]
  ans = sum(A)
  A = [abs(a - temp[N//2-1]) for a in temp]
  ans = min(ans, sum(A))

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