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
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

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

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


if __name__ == '__main__':
    main()

Solution (Python):
n, *a = map(int, open(0).read().split())
s = [a - i - 1 for i, a in enumerate(a)]
b = sorted(s)[n // 2]
print(sum(abs(s - b) for s in 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()

b = a[n // 2]

ret = 0

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

print(ret)

Solution (Python):
import sys
import numpy as np


def main():
  readline = sys.stdin.readline
  
  n = int(readline().rstrip())
  a = np.array(
    tuple(int(a_i) for a_i in readline().rstrip().split())
  )
  
  b = int(np.median(a - np.arange(1, n + 1)))
  
  print(np.sum(np.abs(a - np.arange(1, n + 1) - b)))
  

if __name__ == "__main__":
  main()

Solution (Python):
import statistics
n = int(input())
A = [int(i) for i in input().split()]
A_list = []
ans_l,ans_h = 0,0
Min = 10**9

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

b_lowkey = statistics.median_low(A_list)
b_highkey = statistics.median_high(A_list)

for i in range(n):
    ans_l += abs(A_list[i]-b_lowkey)
    ans_h += abs(A_list[i]-b_highkey)
print(min(ans_l,ans_h))

Solution (Python):
n=int(input())
A=list(map(int,input().split()))
B=[A[i]-(i+1) for i in range(n)]
C=sorted(B)
b=C[n//2]
import functools
x=functools.reduce(lambda x,y:abs(x)+abs(y),[C[i]-b for i in range(n)])
print(x)

Solution (Python):
import numpy as np
N = int(input())
A = np.array(tuple(map(int, input().split())), dtype=np.int64) - np.arange(N) - 1
median = np.median(A)
print(int(min(np.abs(A - median + 0.5).sum(), np.abs(A - median - 0.5).sum())) if int(median * 2) & 1 else int(np.abs(A - median).sum()))

Solution (Python):
import numpy as np
N = int(input())
A = np.array(tuple(map(int, input().split())), dtype=np.int64) - np.arange(N) - 1
median = np.median(A)
if int(median * 2) & 1:
    print(int(min(np.abs(A - median + 0.5).sum(), np.abs(A - median - 0.5).sum())))
else:
    print(int(np.abs(A - median).sum()))

Solution (Python):
from math import ceil, floor

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

temp_list = sorted([a - i for a, i in zip(a_list, range(1, n + 1))])

def calc(num):
    return sum([abs(temp - num) for temp in temp_list])

i = n // 2
if n % 2 == 0:
    med = (temp_list[i - 1] + temp_list[i]) / 2
    print(min(calc(floor(med)), calc(ceil(med))))
else:
    med = temp_list[i]
    print(calc(med))

Solution (Python):


import numpy as np
N = int(input())
A = list(map(int, input().split()))

A_diff = np.array([a - i for i, a in enumerate(A, 1)])
my_median = np.median(A_diff)

print(int(np.sum(np.abs(A_diff * -1 + my_median))))

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

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

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

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

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

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

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

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

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

print(ans)

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

plus = min(alta)
for i in range(N):
    alta[i] -= plus

def f(x):
    sum = 0
    for i in alta:
        sum += abs(x - i)
    return sum


left, right = 0, max(alta)

while abs(right - left) > 3:
    mid1 = (right * 2 + left) // 3 + 1
    mid2 = (right + left * 2) // 3
    if f(mid1) >= f(mid2):
        
        right = mid1
    else:
        
        left = mid2
ans = float('inf')
for i in range(left, right + 1):
    ans = min(ans, f(i))
print(ans)

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

def f(x):
    sum = 0
    for i in alta:
        sum += abs(x - i)
    return sum

left, right = 0, max(alta)
while abs(right - left) > 3:
    mid1 = (right * 2 + left) // 3 + 1
    mid2 = (right + left * 2) // 3
    if f(mid1) >= f(mid2):
        
        right = mid1
    else:
        
        left = mid2
ans = float('inf')
for i in range(left, right + 1):
    ans = min(ans, f(i))
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()

tmp = sum(A) - n * A[0]
m = tmp

for i in range(n-1):
    tmp += (A[i+1]-A[i]) * (2*i+2-n)
    m = min(m, tmp)

print(m)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]




N = ii()
A = li()

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

A = sorted(A)

if not N % 2:
    num = int((A[N//2] + A[N//2-1]) // 2)
else:
    num = A[N//2]
ans = 0
for i in range(N):
    ans += abs(num - A[i])

print(ans)

Solution (Python):
import numpy as np
import collections

N = int(input())
A = list(map(int, input().split()))
ans = 0
dists_A2i = []

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

dists_A2i = np.array(dists_A2i)
dists_median = np.median(dists_A2i)
dists_A2i = abs(dists_A2i - dists_median)
ans = sum(dists_A2i)
print(int(ans))

Solution (Python):
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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




def warshall_floyd(d, n):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d



def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


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 lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)






def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret



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

a2 = sorted([a[i] - i for i in range(n)])
median = a2[n // 2]
ans = sum([abs(a2[i] - median) for i in range(n)])
print(ans)

Solution (Python):
class SplayNode:
    """Splay木のノードを定義
    メンバ変数: 値、サイズ、親へのポインタ、左右の子へのポインタ
    """
    def __init__(self, val):
        self.val = val
        self.size = 1
        self.parent, self.right, self.left = None, None, None


class SplayTree:
    """Splay木を定義"""
    def __init__(self):
        self.root = None

    def __getitem__(self, ind: int):  
        return self.get_ptr(ind, self.root).val
        
    def __setitem__(self, ind: int, val):  
        ptr = self.get_ptr(ind, self.root)
        ptr.val = val

    def __len__(self):  
        return self.root.size if self.root is not None else 0

    def update(self, ptr):
        """部分木の情報を更新する"""
        ptr.size = 1
        if ptr.left is not None:
            ptr.size += ptr.left.size
        if ptr.right is not None:
            ptr.size += ptr.right.size

    def state(self, ptr):
        """スプレー操作を行うときの状況判定
        親が存在しない: 0
        左の兄弟が存在する: 1
        右の兄弟が存在する: -1
        """
        if ptr.parent is None:
            return 0
        if ptr.parent.left == ptr:
            return 1
        if ptr.parent.right == ptr:
            return -1

    def splay(self, ptr):
        """ptrが根になるようにスプレー操作を行う"""
        while self.state(ptr) != 0:
            if self.state(ptr.parent) == 0:
                
                self.rotate(ptr)
            elif self.state(ptr) == self.state(ptr.parent):
                
                self.rotate(ptr.parent)
                self.rotate(ptr)
            else:
                
                self.rotate(ptr)
                self.rotate(ptr)
        self.root = ptr

    def rotate(self, ptr):
        """木の回転を行う"""
        p = ptr.parent
        pp = p.parent
        if p.left == ptr:
            c = ptr.right
            ptr.right = p
            p.left = c
        else:
            c = ptr.left
            ptr.left = p
            p.right = c
        if pp is not None and pp.left == p: pp.left = ptr
        if pp is not None and pp.right == p: pp.right = ptr
        ptr.parent = pp
        p.parent = ptr
        if c is not None:
            c.parent = p
        self.update(p)
        self.update(ptr)

    def get_ptr(self, ind, root):
        """ind番目のポインタを取得する"""
        ptr = root
        while True:
            if ptr.left is None:
                l_size = 0
            else:
                l_size = ptr.left.size
            if ind < l_size:
                ptr = ptr.left
            if ind == l_size:
                self.splay(ptr)
                return ptr
            if ind > l_size:
                ptr = ptr.right
                ind = ind - l_size - 1

    def merge(self, lroot, rroot):
        if lroot is None:
            self.root = rroot
            return rroot
        if rroot is None:
            self.root = lroot
            return lroot
        lroot = self.get_ptr(lroot.size - 1, lroot)
        lroot.right = rroot
        rroot.parent = lroot
        self.update(lroot)
        return lroot
      
    def split(self, left_cnt, root):
        if left_cnt == 0:
            return None, root
        if left_cnt == root.size:
            return root, None
        root = self.get_ptr(left_cnt, root)
        lroot = root.left
        rroot = root
        rroot.left = None
        lroot.parent = None
        self.update(rroot)
        return lroot, rroot
      
    def insert(self, ind, val):
        """ind番目の値valの要素を挿入する"""
        lroot, rroot = self.split(ind, self.root)
        new_ptr = SplayNode(val)
        self.merge(self.merge(lroot, new_ptr), rroot)
    
    def delete(self, ind):
        """indの要素を削除する"""
        root = self.get_ptr(ind, self.root)
        lroot = root.left
        rroot = root.right
        if lroot is not None:
            lroot.parent = None
        if rroot is not None:
            rroot.parent = None
        root.relf = None
        root.left = None
        self.update(root)
        return self.merge(lroot, rroot), root

    def add(self, val):
        if self.root is None:
            self.insert(0, val)
            return
        ptr = self.root 
        ind = 0
        while True:
            if val < ptr.val:
                if ptr.left is None:
                    self.insert(ind, val)
                    return
                ptr = ptr.left
            else:
                ind += 1
                if ptr.left is not None:
                    ind += ptr.left.size
                if ptr.right is None:
                    self.insert(ind, val)
                    return
                ptr = ptr.right


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

sp = SplayTree()
for i in range(n)[::-1]:
    sp.insert(0, a[i])
for i in range(n):
    sp[i] = sp[i] - (i + 1)

ave = sorted([sp[i] for i in range(n)])[n // 2]
ans = 0

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

Solution (Python):
class SplayNode:
    """Splay木のノードを定義
    メンバ変数: 値、サイズ、親へのポインタ、左右の子へのポインタ
    """
    def __init__(self, val):
        self.val = val
        self.size = 1
        self.parent, self.right, self.left = None, None, None


class SplayTree:
    """Splay木を定義"""
    def __init__(self):
        self.root = None

    def __getitem__(self, ind: int):  
        return self.get_ptr(ind, self.root).val
        
    def __setitem__(self, ind: int, val):  
        ptr = self.get_ptr(ind, self.root)
        ptr.val = val

    def __len__(self):  
        return self.root.size if self.root is not None else 0

    def update(self, ptr):
        """部分木の情報を更新する"""
        ptr.size = 1
        if ptr.left is not None:
            ptr.size += ptr.left.size
        if ptr.right is not None:
            ptr.size += ptr.right.size

    def state(self, ptr):
        """スプレー操作を行うときの状況判定
        親が存在しない: 0
        左の兄弟が存在する: 1
        右の兄弟が存在する: -1
        """
        if ptr.parent is None:
            return 0
        if ptr.parent.left == ptr:
            return 1
        if ptr.parent.right == ptr:
            return -1

    def splay(self, ptr):
        """ptrが根になるようにスプレー操作を行う"""
        while self.state(ptr) != 0:
            if self.state(ptr.parent) == 0:
                
                self.rotate(ptr)
            elif self.state(ptr) == self.state(ptr.parent):
                
                self.rotate(ptr.parent)
                self.rotate(ptr)
            else:
                
                self.rotate(ptr)
                self.rotate(ptr)
        self.root = ptr

    def rotate(self, ptr):
        """木の回転を行う"""
        p = ptr.parent
        pp = p.parent
        if p.left == ptr:
            c = ptr.right
            ptr.right = p
            p.left = c
        else:
            c = ptr.left
            ptr.left = p
            p.right = c
        if pp is not None and pp.left == p: pp.left = ptr
        if pp is not None and pp.right == p: pp.right = ptr
        ptr.parent = pp
        p.parent = ptr
        if c is not None:
            c.parent = p
        self.update(p)
        self.update(ptr)

    def get_ptr(self, ind, root):
        """ind番目のポインタを取得する"""
        ptr = root
        while True:
            if ptr.left is None:
                l_size = 0
            else:
                l_size = ptr.left.size
            if ind < l_size:
                ptr = ptr.left
            if ind == l_size:
                self.splay(ptr)
                return ptr
            if ind > l_size:
                ptr = ptr.right
                ind = ind - l_size - 1

    def merge(self, lroot, rroot):
        if lroot is None:
            self.root = rroot
            return rroot
        if rroot is None:
            self.root = lroot
            return lroot
        lroot = self.get_ptr(lroot.size - 1, lroot)
        lroot.right = rroot
        rroot.parent = lroot
        self.update(lroot)
        return lroot
      
    def split(self, left_cnt, root):
        if left_cnt == 0:
            return None, root
        if left_cnt == root.size:
            return root, None
        root = self.get_ptr(left_cnt, root)
        lroot = root.left
        rroot = root
        rroot.left = None
        lroot.parent = None
        self.update(rroot)
        return lroot, rroot
      
    def insert(self, ind, val):
        """ind番目の値valの要素を挿入する"""
        lroot, rroot = self.split(ind, self.root)
        new_ptr = SplayNode(val)
        self.merge(self.merge(lroot, new_ptr), rroot)
    
    def delete(self, ind):
        """indの要素を削除する"""
        root = self.get_ptr(ind, self.root)
        lroot = root.left
        rroot = root.right
        if lroot is not None:
            lroot.parent = None
        if rroot is not None:
            rroot.parent = None
        root.relf = None
        root.left = None
        self.update(root)
        return self.merge(lroot, rroot), root

    def add(self, val):
        if self.root is None:
            self.insert(0, val)
            return
        ptr = self.root 
        ind = 0
        while True:
            if val < ptr.val:
                if ptr.left is None:
                    self.insert(ind, val)
                    return
                ptr = ptr.left
            else:
                ind += 1
                if ptr.left is not None:
                    ind += ptr.left.size
                if ptr.right is None:
                    self.insert(ind, val)
                    return
                ptr = ptr.right


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

sp = SplayTree()
for i in range(n):
    sp.insert(i, a[i])
for i in range(n):
    sp[i] = sp[i] - (i + 1)

ave = sorted([sp[i] for i in range(n)])[n // 2]
ans = 0

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

Solution (Python):
def main():
    n, *a, = map(int, open(0).read().split())
    a = [x - i for i, x in enumerate(a, 1)]
    a.sort()
    if n % 2 == 0:
        ans = sum(a[n // 2:]) - sum(a[:n // 2])
    else:
        ans = sum(a[n // 2 + 1:]) - sum(a[:n // 2])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from statistics import median

    n, *a, = map(int, open(0).read().split())
    a = [x - i for i, x in enumerate(a, 1)]
    a.sort()
    m = int(median(a))

    ans = sum([abs(x - m) for x in a])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

def abc102_c():
    N = int(readline())
    A = np.array(read().split(), dtype=np.int64)

    
    B = A - np.arange(1, N+1)
    
    B.sort()
    x = B[N//2]
    
    ans = np.abs(B - x).sum()
    print(ans)

abc102_c()

Solution (Python):


import sys
import math





















def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n = ii()
    L = lmi()
    L_dec = [elm - (i + 1) for i, elm in enumerate(L)]
    
    left = min(L_dec) - 1
    right = max(L_dec) + 1
    while right - left > 2:
        m_l = (2 * left + right) // 3
        m_r = (left + 2 * right) // 3
        tmp_l = sum([abs(m_l - elm) for elm in L_dec])
        tmp_r = sum([abs(m_r - elm) for elm in L_dec])
        
        if tmp_l >= tmp_r:
            left = m_l
        else:
            right = m_r
    
    
    print(min([sum([abs(j - elm) for elm in L_dec]) for j in range(left, right + 1)]))


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
a.sort()

b = a[(N - 1) // 2]

for i in range(N):
    a[i] = abs(a[i] - b)

print(sum(a))

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

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

Solution (Python):
import math
from statistics import median

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

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

b = round((median(ai)))
result = sum([abs(ai[i] - b) for i in range(n)])
print(result)

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

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

tmp = int(statistics.median(A))

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

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]
ans=0
for a in A:
    ans+=abs(a-c)
print(ans)

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

c = [a[i]-i-1 for i in range(n)]
ans = 0
c.sort()

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

Solution (Python):






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

    B = sorted([A[i]-i for i in range(N)])
    
    b = B[N//2]

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


print(main())

Solution (Python):
from sys import stdin
def main():
    
    readline=stdin.readline
    N=int(readline())
    A=list(map(int,readline().split()))

    B=[0]*N
    for i in range(N):
        B[i]=A[i]-i
    B.sort()
    if N%2==1:
        b=B[N//2]
    else:
        b=(B[N//2-1]+B[N//2])//2
    
    res=0
    for i in range(N):
        res+=abs(B[i]-b)

    print(res)
if __name__=="__main__":
    main()

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

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

if len(arr)%2==0:
  tmp=[arr[len(arr)//2-1],arr[len(arr)//2]]
else:
  tmp=[arr[len(arr)//2]]

ans=10**20
for b in tmp:
  ans=min(ans,sum([abs(a[i]-b-i-1) for i in range(n)]))
print(ans)

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

b_low=-1*(10**10)
b_high=10**10
b_low_d=sum([abs(a[i]-(b_low+2+i)) for i in range(n)])-sum([abs(a[i]-(b_low+1+i)) for i in range(n)])
b_high_d=sum([abs(a[i]-(b_high+2+i)) for i in range(n)])-sum([abs(a[i]-(b_high+1+i)) for i in range(n)])

while b_high-b_low>10:
  b_tmp=(b_low+b_high)//2
  b_tmp_d=sum([abs(a[i]-(b_tmp+2+i)) for i in range(n)])-sum([abs(a[i]-(b_tmp+1+i)) for i in range(n)])
  if b_tmp_d>0:
    b_high=b_tmp
  else:
    b_low=b_tmp

ans=10**20
for j in range(b_low,b_high):
  ans=min(ans,sum([abs(a[i]-(j+2+i)) for i in range(n)]))

print(ans)

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

b_low=-1*(10**12)
b_high=10**12
b_low_d=sum([abs(a[i]-(b_low+2+i)) for i in range(n)])-sum([abs(a[i]-(b_low+1+i)) for i in range(n)])
b_high_d=sum([abs(a[i]-(b_high+2+i)) for i in range(n)])-sum([abs(a[i]-(b_high+1+i)) for i in range(n)])

while b_high-b_low>10:
  b_tmp=(b_low+b_high)//2
  b_tmp_d=sum([abs(a[i]-(b_tmp+2+i)) for i in range(n)])-sum([abs(a[i]-(b_tmp+1+i)) for i in range(n)])
  if b_tmp_d>0:
    b_high=b_tmp
  else:
    b_low=b_tmp

ans=10**20
for j in range(b_low,b_high):
  ans=min(ans,sum([abs(a[i]-(j+2+i)) for i in range(n)]))

print(ans)

Solution (Python):
N = int(input())
*A, = 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 = ans + abs(A[i]-b)

print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
B=[]
for i,ai in enumerate(a,start=1):
  B.append(ai-i)
c=sorted(B)
b=c[len(c)//2]

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

Solution (Python):
import numpy as np

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

a2 = [a[i] - i - 1 for i in range(n)]
mean = sum(a2) / len(a2)
median = np.median(np.array(a2))
b = np.floor(median)
a3 = sum([abs(a2[i] - b) for i in range(n)])
b = np.ceil(median)
a4 = sum([abs(a2[i] - b) for i in range(n)])
print(int(min(a3, a4)))

Solution (Python):
import numpy as np
N = int(input())
list_ai = list(map(int,input().split()))
a1 = np.array(list_ai)-np.arange(1,N+1)
median1 = int(np.floor(np.median(a1)))
ans = np.sum(np.abs(a1-median1))
print(ans)

Solution (Python):
import numpy as np
N = int(input())
list_ai = list(map(int,input().split()))
list1 = [x-(i+1) for i,x in enumerate(list_ai)]
a1 = np.array(list1)
median1 = int(np.floor(np.median(a1)))
ans = np.sum(np.abs(a1-median1))
print(ans)

Solution (Python):
import numpy as np
N = int(input())
list_ai = list(map(int,input().split()))
list1 = [x-(i+1) for i,x in enumerate(list_ai)]
a1 = np.array(list1)
median1 = int(np.floor(np.median(a1)))
ans = sum(abs(x-median1) for x in list1)
print(ans)

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

Solution (Python):
n = int(input())
idx = [i for i in range(1, n+1)]
a = [int(inp) - i for inp, i in zip(input().split(), idx)]
a.sort()
if n % 2 == 0:
    med = (a[(n-2)//2] + a[(n-2)//2+1])//2
else:
    med = a[(n-1)//2]
ans = 0
for ai in a:
    ans += max(ai-med, -ai+med)
print(ans)

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



def f(x):
    v = 0
    for i in range(len(B)):
        v += abs(B[i] - x)
    return v


if len(B) % 2 == 0:
    b1 = B[len(B) // 2 - 1]
    b2 = B[len(B) // 2]
    ans = min(f(b1), f(b2))
else:
    b = B[len(B) // 2]
    ans = f(b)
print(ans)

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


def f(x):
    v = 0
    for i in range(len(A)):
        v += abs(A[i] - (x + i + 1))
    return v


left = -(10**9 + 2 * 10**5)
right = 10**9 + 2 * 10**5
v = 10**18
while left + 1 < right:
    x = (left + right) // 2
    
    a = f(x)
    v = min(v, a)
    if a <= f(x + 1):
        right = x
    elif f(x - 1) >= a:
        left = x



print(v)

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

b = sorted(a)
if n % 2 != 0:
    b = b[n // 2]
else:
    b = (b[n // 2] + b[n // 2 - 1]) // 2

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

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

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

a.sort()

mid = statistics.median_low(a)
mid1 = statistics.median_high(a)
ans = [0,0]

for i, aa in enumerate(a):
    ans[0] += abs(aa - mid)
    ans[1] += abs(aa - mid1)
print(min(ans))

Solution (Python):
import numpy as np
n = int(input())
a_ls = list(map(int, input().split()))
diff_ls = [a - i for i, a in enumerate(a_ls,1)]
diff_ls.sort()
med = int(np.median(diff_ls))
ans = 0
for diff in diff_ls:
    ans += abs(diff - med)
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()

b2=b[n//2]

bsum=0
for i in range(n):
    bsum+=abs(b[i]-b2)
    
bsum2=0
for i in range(n):
    bsum2+=abs(b[i]-b2-1)

print(min(bsum,bsum2))

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