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



Sample input:
5
2 2 3 5 5


Sample output:
2

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# マンハッタン距離の総和を最小化するときは、中央値を使うという典型がある。

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

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

print(ans)

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

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

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# MOD = 998244353


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
A = np.array(A, dtype=int) - np.arange(N, dtype=int)
A.sort()

cum = A.cumsum()

ans = cum[-1] - A[0] * N
# どこで切るか決める
for i in range(1, N):
    # 右側
    r = cum[N - 1] - cum[i - 1] - A[i] * (N - i)
    # 左側
    l = A[i] * i - cum[i - 1]
    ans = min(l + r, ans)
print(ans)

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

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

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def tleft(fn, lo, hi):
    """
    fn の結果が最も小さくなるインデックスを三分探索する
    :param callable fn:
    :param int lo: 最小のインデックス
    :param int hi: 最大のインデックス + 1
    :return: lo <= ret < hi
    """
    left = lo
    right = hi
    while abs(right - left) >= 3:
        r1 = (left * 2 + right) // 3
        r2 = (left + right * 2) // 3
        if fn(r1) <= fn(r2):
            right = r2
        else:
            left = r1
    if left + 1 >= hi or fn(left) <= fn(left + 1):
        return left
    if left + 2 >= hi or fn(left + 1) <= fn(left + 2):
        return left + 1
    return left + 2


def cost(n):
    return np.abs(A + n).sum()


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
A = np.array(A, dtype=int) - np.arange(N, dtype=int)

i = tleft(cost, -1e18, 1e18)
print(int(cost(i)))

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
B=sorted([A[i]-(i+1) for i in range(n)])
if n%2==1:
    b=B[n//2]
else:
    b=(B[n//2-1]+B[n//2])//2
r=0
for i in range(n):
    r+=abs(B[i]-b)
print(r)

Submission status: Accepted

Solution code:
def main():
    N, *A = map(int, open(0).read().split())
    for i in range(N):
        A[i] -= i + 1
    A.sort()
    print(sum(A[N // 2 + N % 2:]) - sum(A[:N // 2]))
    return


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC102 C

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

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

Submission status: Accepted

Solution code:
def main():
    N, *A = map(int, open(0).read().split())
    for i in range(N):
        A[i] -= i + 1
    A.sort()
    b = A[N // 2]
    print(sum([abs(A[i] - b) for i in range(N)]))
    return


main()

Submission status: Accepted

Solution code:
def main():
    N, *A = map(int, open(0).read().split())
    for i in range(N):
        A[i] -= i + 1
    A.sort()
    ans = 0
    b = A[N // 2]
    for i in range(N):
        ans += abs(A[i] - b)
    print(ans)
    return


main()

Submission status: Accepted

Solution code:
N = int(input())
A = sorted([int(c)-i-1 for i, c in enumerate(input().split())])
b = A[N//2]
ans = sum([abs(a-b) for a in A])
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = list(map(int, input().split()))
a = []
ans = 0

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

# 平均値ではなく、中央値を使う
b = int(np.median(a))

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

print(ans)

Submission status: Accepted

Solution code:
def func(li,b) :
    sum = 0
    for i in range(len(li)) :
        sum+= abs(li[i] - b - i - 1)
    return sum
def binary_search(li) :
    left = -1000000001
    right = 1000000001
    while right - left > 1 :
        med = (right + left) // 2
        x = func(li,med)
        mdx = func(li,med-1)
        pdx = func(li,med+1)
        if mdx > x and pdx < x :
            left = med
            continue
        elif mdx < x and pdx > x :
            right = med
            continue
        elif mdx >= x and pdx >= x :
            return x
    else :
        return -1
N = int(input())
A =[int(i) for i in input().split()]
print(binary_search(A))

Submission status: Accepted

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

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

#print(A)

A.sort()

b = A[N//2]

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

print(s)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def func(li,b) :
    sum = 0
    for i in range(len(li)) :
        sum+= abs(li[i] - b - i - 1)
    return sum
def binary_search(li) :
    left = -1000000001
    right = 1000000001
    while right - left > 1 :
        med = (right + left) // 2
        x = func(li,med)
        mdx = func(li,med-1)
        pdx = func(li,med+1)
        if mdx > x and pdx < x :
            left = med
            continue
        elif mdx < x and pdx > x :
            right = med
            continue
        elif mdx >= x and pdx >= x :
            return x
    else :
        return -1
N = int(input())
A =[int(i) for i in input().split()]
print(binary_search(A))

Submission status: Accepted

Solution code:
n = int(input())
lst = list(map(int, input().split()))

lst2 = []
for i, l in enumerate(lst, start= 1):
    lst2.append(l-i)

def median(lst):
    num = len(lst)
    sor = sorted(lst)
    if num%2==0:
        return round((sor[num//2] + sor[num//2-1])/2)
    else:
        return sor[num//2]
b = median(lst2)
ans = sum([abs(val - b) for val in lst2])
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())

a = list(map(int, input().split()))
a = np.array(a)
a -= np.array(range(1,n+1))

b = np.median(a)

ans = int(np.sum(abs(a-b)))

print(ans)

Submission status: Accepted

Solution code:
# ABC102 C - Linear Approximation
N = int(input())
A = list(map(int, input().split()))

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

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

Submission status: Accepted

Solution code:
# ABC102 C - Linear Approximation
N = int(input())
A = list(map(int, input().split()))

bl = []
for i in range(N):
    bl.append(A[i] - (i+1))
bl.sort()
b = bl[N//2]

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  _l=LI()

  l=[]
  for i,x in enumerate(_l):
    l.append(x-(i+1))

  l.sort()
  if n%2==1:
    x=l[n//2]
  else:
    x=(l[n//2]+l[n//2-1])//2

  ans=0
  for y in l:
    ans+=abs(y-x)

  return ans

# main()
print(main())

Submission status: Accepted

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

b_l = []
for i in range(0,len(a)):
    b_l.append(a[i] - (i+1))
b_l.sort()
b = b_l[n//2]
ans = 0
for i in range(0,len(a)):
    ans += abs(a[i] - (i+1+b))
print(ans)

Submission status: Accepted

Solution code:
import sys

n, *a = map(int, sys.stdin.read().split())

def main():
    for i in range(n):
        a[i] -= (i + 1)
    a.sort()
    b = a[n // 2]
    res = 0
    for i in range(n):
        res += abs(a[i] - b)
    
    return res
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
from statistics import mean, median, variance, stdev

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

A2 = [a-(idx+1) for idx, a in enumerate(A)]
# print(A2, sum(A2), median(A2))

center = median(A2)

ans = 0
for a in A2:
    ans += abs(a-center)
print(int(ans))

Submission status: Accepted

Solution code:
n = int(input())
a = [int(item)-i for i,item in enumerate(input().split(),1)]
ans = 0
a.sort()

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

print(ans)

Submission status: Accepted

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

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

median = statistics.median(A)

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

print(int(ans))

Submission status: Accepted

Solution code:
import math
import numpy as np
from fractions import gcd
import fractions
import statistics
import collections

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

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

median = statistics.median(A)

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

print(int(ans))

Submission status: Accepted

Solution code:
import bisect
n = int(input())
lst1 = list(map(int,input().split()))

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



service = bisect.bisect_left(lst1,0)
limit = len(lst1)//2

b = lst1[limit]

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

print(ans)

Submission status: Accepted

Solution code:
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]
ans = 0
for i in A:
    ans += abs(i-b)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    difA = [0]*N

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

    difA.sort()
    if N%2 == 0:
        g1 = difA[N//2]
        g2 = difA[N//2-1]
        a1 = 0
        a2 = 0
        for i in range(N):
            a1 += abs(difA[i]-g1)
            a2 += abs(difA[i]-g2)
        print(min(a1,a2))
            
    else:
        g = difA[N//2]
        a = 0
        for i in range(N):
            a += abs(difA[i]-g)
        print(a)
    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ans=[]
for i in range(n):
    ans.append(abs(a[i]-b1))

print(sum(ans))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n==1:
    print(0)
    exit()
for i in range(n):
    a[i]=a[i]-i-1
a.sort()
b1=a[n//2]
b2=a[n//2+1]
ans1=[]
ans2=[]
for i in range(n):
    ans1.append(abs(a[i]-b1))
for i in range(n):
    ans2.append(abs(a[i]-b2))
print(min(sum(ans1),sum(ans2)))

Submission status: Accepted

Solution code:
import statistics

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

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

med = statistics.median(a)

ans = 0

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

print(int(ans))

Submission status: Accepted

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
B = []
for i in range(N):
    B.append(A[i]-(i+1))
B.sort()
M1, M2 = B[N//2],B[N//2]
if N > 1:
    M2 = B[N//2+1]
C1, C2 = [], []
for i in range(N):
    C1.append(abs(B[i]-M1))
    C2.append(abs(B[i]-M2))
print(min(sum(C1),sum(C2)))

Submission status: Accepted

Solution code:
import math
N = int(input())
A = input()
A = A.split()
B =[]
C = []
ans1 = 0
ans2 = 0
for i in range(N):
    B.append(int(A[i]))
    C.append(int(A[i])-i)
C.sort(reverse=True)

n = math.floor(N/2)
b = C[n]
b1 = C[n-1]

for i in range(N):
    ans1 = ans1 + abs(B[i]-(i+b))
for i in range(N):
    ans2 = ans2 + abs(B[i]-(i+b1))
ans = min(ans1, ans2)
print(ans)

Submission status: Accepted

Solution code:
from statistics import median
N = int(input())
A = list(map(int, input().split()))
B = list()
sad = 0

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

b = median(B)

for i in range(N):
  sad = sad + abs(A[i] - (b+i))

print(int(sad))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = sorted([A[i]-i for i in range(N)])
b = B[(N-1)//2] if N % 2 != 0 else (B[N//2-1]+B[N//2])//2
print(sum(abs(B[i]-b) for i in range(N)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from statistics import median_low

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

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

m = median_low(D)
ans = 0
for d in D:
    ans += abs(d - m)

print(ans)

Submission status: Accepted

Solution code:
import statistics
n = int(input())
A = list(map(int,input().split()))
al = []
for i in range(n):
  al.append(A[i] - i + 1)
b = statistics.median(al)
ans = 0
for a in al:
  ans += abs(a - b)
print(int(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

# bをmとした時の悲しさ値
def check(m):
    sm = 0
    for i, a in enumerate(A):
        sm += abs(a - (m+i+1))
    return sm

# 三分探索
low = -10**9
hi = 10**9
while low+2 < hi:
    m1 = (low*2+hi) // 3
    m2 = (low+hi*2) // 3
    res1 = check(m1)
    res2 = check(m2)
    # 今回は下に凸な関数なので値の小さい方に向かって狭めていく
    if res1 <= res2:
        hi = m2
    else:
        low = m1

print(min(check(m1), check(m2)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int,input().split()))
a = [v - i -1 for i,v in enumerate(a)]
a.sort()
b = a[n//2]

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
N = int(input())
A = [int(x) for x in input().split()]
for i in range(1,N+1):
    A[i-1] -= i
A = np.array(A,np.int64)
flagzero = np.count_nonzero(A == 0)
A_m, A_p = A[(A < 0)], A[(A > 0)]
A_p = np.sort(A_p)
A_m = np.sort(A_m)[::-1]
m, p = len(A_m), len(A_p)
if m == p:
    print(abs(A_p.sum()) + abs(A_m.sum()))
    sys.exit()
elif m > p:
    p += flagzero
    diff = m - p
    if diff <= 0:
        print(abs(A_p.sum()) + abs(A_m.sum()))
        sys.exit()
    else:
        diff = (diff//2) + (diff % 2 != 0)
        change = A_m[diff-1]
elif m < p:
    m += flagzero
    diff = p - m
    if diff <= 0:
        print(abs(A_p.sum()) + abs(A_m.sum()))
        sys.exit()
    else:
        diff = (diff//2) + (diff % 2 != 0)
        change = A_p[diff-1]
A_m -= change
A_p -= change
A_m = abs(A_m)
A_p = abs(A_p)
print(abs(A_p.sum()) + abs(A_m.sum()) + abs(flagzero * change))

Submission status: Accepted

Solution code:
#coding:utf-8
n = int(input())
A = list(map(int,input().split()))
A = [A[i]-i-1 for i in range(n)]
A = sorted(A)
# print (A)
b = A[n//2]
print (sum([abs(a-b) for a in A]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
q=[]
for i,j in enumerate(a):
  q.append(j-(i+1))
#print(q)
q.sort()
#print(q)
if n%2==1:
  b=q[n//2];#print(b)
else:
  b=(q[n//2]+q[n//2-1])/2;#print(b)
r=[]
for k in q:
  r.append(abs(k-b))
print(int(sum(r)))

#TLEの予感

Submission status: Accepted

Solution code:
n=int(input())
import math
a=list(map(int,input().split()))
for i in range(n):
    a[i]-=(i+1)
a=sorted(a)  
if n%2==0:
    x=math.floor((a[int(n/2)]+a[int((n/2)-1)])/2)
else:
    x=a[int(n//2)]    
ans=0
for i in range(n):
    ans+=abs(a[i]-x)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N=input()
A=np.array([int(a)-i-1 for i,a in enumerate(input().split())])
print(sum(abs(A-int(np.median(A)))))

Submission status: Accepted

Solution code:
N = int(input())
l = map(int, input().split())


new_l = map(lambda x, y: (x-y), l, range(1, N+1))

new_l = sorted(new_l)
if (N % 2 == 0):
    b1 = (new_l[N//2] + new_l[N//2-1]) // 2
    b2 = (new_l[N//2] + new_l[N//2-1]) // 2 + 1
    res1 = sum(map(lambda x, y: abs(x-y), new_l, [b1]*N))
    res2 = sum(map(lambda x, y: abs(x-y), new_l, [b2]*N))
    res = min(res1, res2)
else:
    b = new_l[N//2]
    res = sum(map(lambda x, y: abs(x-y), new_l, [b]*N))

print(res)

Submission status: Accepted

Solution code:
import sys

import numpy as np

readline = sys.stdin.buffer.readline


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    B = np.arange(N) + 1
    C = A - B
    m = int(np.median(C))

    B += m
    m0 = np.sum(np.abs(A - B))
    m1 = np.sum(np.abs(A - (B + 1)))
    m2 = np.sum(np.abs(A - (B - 1)))

    print(min(m0, m1, m2))


main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().split()))
B=[A[i]-i-1 for i in range(N)]
B.sort()
if N%2==1:
  print(sum([abs(B[i]-B[N//2]) for i in range(N)]))
else:
  temp=(B[N//2-1]+B[N//2])//2
  ms=[temp+i for i in range(-2, 3, 1)]
  temp=[sum([abs(B[i]-ms[j]) for i in range(N)]) for j in range(5)]
  print(min(temp))

Submission status: Accepted

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

ans = 0
center = b[n//2]

for x in b:
    ans += abs(x-center)
    
print(ans)

Submission status: Accepted

Solution code:
import statistics
N = int(input())
a = list(map(int, input().split()))
for i in range(N):
    a[i] -= i + 1
b = statistics.median(a)
if b > 0 and b % 1 >= 0.5:
    b += 1
elif b < 0 and b % -1 <= -0.5:
    b -= 1
b = int(b)
ans = 0
for i in range(N):
    ans += abs(a[i] - b)
print(ans)

Submission status: Accepted

Solution code:
import sys
import statistics
input = sys.stdin.readline

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 i in range(N):
    ans += abs(A[i] - med)
print(ans)

Submission status: Accepted

Solution code:
#あー統計のやつか、絶対値の和の最小値は平均の値
n=int(input())
s=input().split()
a=sorted([int(s[i])-i-1 for i in range(n)])
#ここまでの発想は流石にわかる
c=0
for i in range(n):
    if i<=n//2:
        c+=(a[n//2]-a[i])
    else:
        c+=(a[i]-a[n//2])
print(c)



'''
if n==1:
    print(0)
else:
    mi=[]
    h=sum(a)
    k=h
    for i in range(n-1):
        c,d=a[i],a[i+1]
        k-=2*a[i]
        m=k
        l=(i+1)-(n-i-1)
        if l>0:
            m+=(l*a[i+1])
        else:
            m+=(l*a[i])
        mi.append(m)
    mi.append(h-a[0]*n)
    mi.append(a[-1]*n-h)
    print(min(mi))
'''

Submission status: Accepted

Solution code:
"""
中央値を求めれば良い.
"""
def get_diff(value, array):
  diff = 0
  for i in array:
    diff += abs(value - i)
  return diff

length = int(input())
inp = input().split(' ')
A = []
for i in range(0, length):
  A.append(int(inp[i]) - i - 1)

A.sort()

# print(A)

# odd numbers
if len(A) % 2 == 1:
  center_number = A[len(A) // 2]
else:
  center_number = int(A[len(A) // 2 ] + A[len(A) // 2]) / 2

# print(center_number)
print(int(get_diff(center_number, A)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect, string, copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7
ans = 0 ; count = 0; pro = 1

n=int(input())
A=list(map(int,input().split()))
for i in range(n):A[i]-=i+1
A.sort()
B=A[n//2]
for ai in A:
    ans+=abs(ai-B)
print(ans)

Submission status: Accepted

Solution code:
import statistics

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

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

if len(A) % 2 == 1:
    b = statistics.median(t)
    ans = 0
    for i in range(N):
        ans += abs(A[i] - i - b)
    print(ans)
else:
    t.sort()
    b1 = t[len(t) // 2]
    b2 = t[(len(t) // 2) - 1]
    ans1 = 0
    ans2 = 0
    for i in range(N):
        ans1 += abs(A[i] - i - b1)
    for i in range(N):
        ans2 += abs(A[i] - i - b2)
    print(min(ans1, ans2))

Submission status: Accepted

Solution code:
# abs(Ai - (b - i )) + ... のmin
N = int(input())
A = list(map(int,input().split()))
B = []
for i in range(len(A)):
    B.append(A[i] - (i + 1))
B.sort()
#print(B)
if N % 2 == 1:
    b = B[N//2]
else:
    b = (B[N // 2] + B[N // 2 - 1]) // 2
#print(b)
sum_val = 0
for i in range(N):
    sum_val += abs(B[i] - b)
print(sum_val)

Submission status: Accepted

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

center = n//2
c1 = b[center]

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

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
A=[int(X) for X in input().split()]
B=[]
for i in range(N):
  B +=[A[i]-1-i]
B = np.array(sorted(B))
x = B[N//2]
answer = np.abs(B-x).sum()
print(answer)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:

def examC():
    N = I()
    A = LI()
    newA = []
    for i in range(N):
        cur = A[i]-i-1
        newA.append(cur)
    newA.sort()
    b = newA[N//2]
    ans = 0
    for i in range(N):
        ans += abs(newA[i]-b)
    print(ans)


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()
mod = 10**9 + 7
inf = float('inf')

examC()

Submission status: Accepted

Solution code:
#from copy import copy
N = int(input())
A = [int(i) for i in input().split()]
for i in range(N):
    A[i] -= i+1
A.sort()
#sum_A = copy(A)
# for i in range(1, N):
#    sum_A[i] += sum_A[i-1]
right = max(abs(max(A)), abs(min(A)))
left = -right
right += 1
ans = 0
while right-left > 2:
    middle = (right+left)//2
    m0 = 0
    m1 = 0
    for a in A:
        m0 += abs(a-middle)
        m1 += abs(a-middle-1)
    if m0 < m1:
        right = middle+1
    elif m0 == m1:
        ans = m0
        break
    else:
        left = middle+1
else:
    s1 = 0
    s2 = 0
    for a in A:
        s1 += abs(a-left)
        s2 += abs(a-left-1)
    ans = min(s1, s2)
print(ans)

Submission status: Accepted

Solution code:
from operator import add
import statistics
n,*a=map(int,open(0).read().split())
b=range(-1,-(n+1),-1)
combined=[a[i]+b[i] for i in range(n)]
x=round(statistics.median(combined))
ans=sum([abs(combined[i]-x) for i in range(n)])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import statistics
n = int(input())
list_a = list(map(int, input().split()))
list_a = [a-i-1 for i, a in enumerate(list_a)]
med = int(statistics.median(list_a))
result = sum([abs(a-med) for a in list_a])
print(result)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
def check(x):
  r = 0
  for i in range(N):
    r += abs(A[i] - (x + i + 1))
  return r
l = -2 * 10 ** 14
r = 2 * 10 ** 14
x1 = 0
x2 = 0
c = 0
while c < 300:
  c += 1
  x1 = (2 * l + r) // 3
  x2 = (l + 2 * r) // 3
  lres = check(x1)
  rres = check(x2)
  if lres > rres:
    l = x1
  else:
    r = x2
#print(x1, x2)
print(min(check(x1), check(x2)))

Submission status: Accepted

Solution code:
import bisect

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

for n in range(N):
    A_n.append(A[n]-(n+1))

A_n = sorted(A_n, reverse=True)

can_f = A_n[N//2]
ans_f = 0
for n in range(N):
    ans_f += abs(A_n[n]-can_f)


if N > 1:
    ans_s = 0
    can_s = A_n[N//2+1]
    for n in range(N):
        ans_s += abs(A_n[n]-can_s)
else:
    ans_s = 10**10

ans = min(ans_f, ans_s)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import math

N = int(input())

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

B = np.arange(1,N+1)

dif = np.median(A-B)

# if dif < 0:
#     dif = int(math.floor(dif))
# else:
#     dif = int(round(dif))


ans = int(np.sum(np.abs(A-B-dif)))

print(ans)

Submission status: Accepted

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

a.sort()

def menseki(b):
  temp=0
  for i in range(n):
    temp+=abs(a[i]-b)
  return temp


middle=n//2
b=a[middle]
ans=min(menseki(b),menseki(b-1),menseki(b+1))

print(ans)

Submission status: Accepted

Solution code:
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(A[i] - (i + 1) - b)

print(ans)

Submission status: Accepted

Solution code:
import statistics
n = int(input())
al = list(map(int,input().split()))

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

median = statistics.median(al)

ans = 0
for a in al:
    ans += abs(median - a)

print(int(ans))

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
al = list(map(int,input().split()))

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

med = np.median(np.array(al))

ans = 0
for a in al:
    ans += abs(a-med)
print(int(ans))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = [a - i - 1 for (a, i) in enumerate(A)]
A.sort()
med = A[N//2]
print(sum(abs(a-med) for a in A))

Submission status: Accepted

Solution code:
import statistics
n = int(input())
a = [0]*n
for i,x in enumerate(map(int, input().split())):
  a[i]=x-i-1

c = int(statistics.median(a))

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from sys import stdin
import statistics

n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))
lin = [i+1 for i in range(n)]
point = 0
ls = []
for i in range(n):
    ls.append(li[i]-lin[i])
ls.sort()
mi = 10**10

k = int(round(statistics.median(ls)))

for i in range(len(ls)):
    ls[i] = abs(ls[i]-k)

print(sum(ls))

Submission status: Accepted

Solution code:
n = int(input())
a_ = list(map(int, input().split( )))

a = [a_[i]-i-1 for i in range(n)]
a.sort()
##b~a[i]で(n-i)-i減る中央値でよい
##偶奇等適当
b1 = a[n//2-1]
b2 = a[n//2]
ans_1 = [abs(a[i]-b1) for i in range(n)]
ans_2 = [abs(a[i]-b2) for i in range(n)]

ans1 = sum(ans_1)
ans2 = sum(ans_2)
print(min(ans1,ans2))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input().strip())
A = [int(x) - (i + 1) for i, x in enumerate(input().strip().split())]
B = sorted(A)
ans = 0
for i in B[len(B)//2-1:len(B)//2+3]:
    if ans == 0:
        ans = sum([abs(a - i) for a in A])
    else:
        ans = min(ans, sum([abs(a - i) for a in A]))

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input().strip())
A = [int(x) - (i + 1) for i, x in enumerate(input().strip().split())]
B = sorted(A)[(len(A)+1)//2-1]

print(sum([abs(a - B) for a in A]))

Submission status: Accepted

Solution code:
from math import floor, ceil
n=int(input())
a=[int(i) for i in input().split()]
for i in range(len(a)):
    a[i]-=(i+1)

a.sort()

n = a[(len(a)+1)//2-1]
a = [abs(i-n) for i in a]

print(sum(a))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())

A = list(map(int, input().split(' ')))
A = [ a - (i + 1) for i, a in enumerate(A)]
A.sort()

# print(A)
n = A[(len(A)+1)//2 - 1]
A = [abs(a - n) for a in A]

# print(A)
print(sum(A))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=[int(x) for x in input().split()]
s=[0 for x in range(n)]
 
for i in range(n):
  a[i] -= i+1
 
a.sort()
 
s = 0
for j in range(n):
  s += abs(a[j]-a[n//2])
print(s)

Submission status: Accepted

Solution code:
import math

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

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

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

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