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:
input = open(0).read

N, *An = map(int, input().split())


def main():
    for i in range(N):
        An[i] = An[i] - i - 1

    ans = 0

    An.sort()

    for i in range(N):
        ans += abs(An[i] - An[N // 2])

    print(ans)
    return


main()

Submission status: Accepted

Solution code:
import statistics
n = int(input())
a = list(map(int, input().split()))
summ = 0
for i in range(n):
    a[i] = a[i] - (i + 1)
b = statistics.median_low(a)
ans = 0
for i in range(n):
    ans += abs(a[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)]
ave = sorted(A)[n//2] 
ans = sum([abs(A[i]-ave) for i in range(n)])
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
A = [a[i] - i - 1  for i in range(n)]
ave = sorted(A)[n//2] 
ans = sum([abs(A[i]-ave) for i in range(n)])
print(ans)

Submission status: Accepted

Solution code:
def solve(string):
    n, *a = map(int, string.split())
    a = sorted([_a - i - 1 for i, _a in enumerate(a)])
    median = a[len(a) // 2]
    return str(sum([abs(_a - median) for _a in a]))


if __name__ == '__main__':
    print(solve("\n".join([input(), input()])))

Submission status: Accepted

Solution code:
from collections import Counter


def solve(string):
    n, *a = map(int, string.split())
    a = sorted([_a - i - 1 for i, _a in enumerate(a)])
    median = a[len(a) // 2]
    return str(sum([abs(_a - median) for _a in a]))


if __name__ == '__main__':
    print(solve("\n".join([input(), input()])))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
lst = np.array(list(map(int, input().split() )))
for i in range(len(lst)):
    lst[i] = lst[i] - (i +1)
#print("lst:",lst)
b = int(np.median(lst) )  
#print("np.mean(lst):",np.mean(lst))
#print("b:",b)
count = 0
for A in lst:
    count += abs(A -b)
print(count)

Submission status: Accepted

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

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

Submission status: Accepted

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

if N//2 == 0:
    b = a_[N//2]
else:
    b = a_[(N-1)//2]

s = [abs(n - b) for i, n in enumerate(a_)]

print(sum(s))

Submission status: Accepted

Solution code:
def linear_approximation(N: int, A: int)->int:
    """悲しさを f(b) = sum|ai - (b + i)| とする。
    これを少し変形して
    f(b) = sum|b - (ai - i)|
    とする。この形の関数は b = (ai - i) の位置で傾きが代わり、
    詳しくは述べないが、ソートして N/2 番目の点で最小値になる。
    """
    new_A = []  # A の各値から i+1 を引いたものを保持しておく
    for i, a in enumerate(A):
        tmp = a - (i+1)
        new_A.append(tmp)

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

    return sum(abs(a-b) for a in new_A)


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = linear_approximation(N, A)
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
A = [A[i] - i - 1 for i in range(N)]
A.sort()
c = int(math.floor(N/2))
answer = sum(list(map(abs,[A[i] - A[c] for i in range(N)])))
print(answer)

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
a=np.array(list(map(int,input().split())))

def calc(b):
    ret=0
    for i in a:
        ret+=abs(i-b)
    return ret

for i in range(N):
    a[i]-=(i+1)
a=np.sort(a)
median=int(np.median(a))

ans1=calc(median)
ans2=calc(median+1)
print(min(ans1,ans2))

Submission status: Accepted

Solution code:
import statistics

N=int(input())
L=list(map(int,input().split()))
for i in range(N):
  L[i]=L[i]-(i+1)
m=statistics.median(L)
ans=0
for i in range(N):
  ans+=abs(L[i]-m) 
print(int(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import statistics as st
n=int(input())
a=list(map(int, input().split()))
a1=[a[i]-(i+1) for i in range(n)]
med=st.median(a1)
ans=0
for ai in a1:
    ans+=abs(ai-med)
print(int(ans))

Submission status: Accepted

Solution code:
# /user/bin/python
# -*- coding: utf-8 -*-
import sys 


n = int(input())
a = list(map(int, sys.stdin.readline().rstrip().split()))
for i in range(n):
  a[i] = a[i]-i-1
a = sorted(a)
m = n // 2

ans1,ans2 = 0,0
for i in range(n):
  ans1 += abs(a[i] - a[m])
  if n > 1:
    ans2 += abs(a[i] - a[m+1])
  else:
    ans2 += abs(a[i] - a[m])

print(min(ans1, ans2))

Submission status: Accepted

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

dif_lst = []
for k, i in enumerate(lst):
    dif_lst.append(i-k-1)
l = len(dif_lst) // 2
a = sorted(dif_lst)[l]

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

Submission status: Accepted

Solution code:

n = int(input())
a = list(map(int, input().split()))
b = []
answer = []

for i in range(n):
	b.append(a[i]-i)
b.sort()
med = b[int(n/2)]

for i in range(n):
	answer.append(abs(a[i]-(med+i)))
	

print(sum(answer))

Submission status: Accepted

Solution code:
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = map(int,input().split())   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import numpy as np
import copy
from collections import defaultdict, Counter
from itertools import product
from bisect import bisect_left, bisect_right
def inpl(): return list(map(int, input().split()))


def res(nA, i):
    for i in range(min_A, max_A+1):
        tmp = sum([ abs(Ai - i) for Ai in nA ])
    if tmp < ans:
        ans = tmp
    return ans

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

nA = sorted([ Ai - (i+1) for i, Ai in enumerate(A)])
ans = 10e9

if len(nA) % 2 != 0:
    print(sum([ abs(Ai - nA[len(nA)//2]) for Ai in nA ]))
else:
    print(min(sum([ abs(Ai - nA[len(nA)//2-1]) for Ai in nA ]), sum([ abs(Ai - nA[len(nA)//2]) for Ai in nA ])))

Submission status: Accepted

Solution code:
import fractions
import statistics
import operator
from functools import reduce
N = int(input())
a_list = list(map(int, input().split(' ')))
median = statistics.median([a - i for i,a in enumerate(a_list)])
print(int(sum([abs(a - (median + i)) for i,a in enumerate(a_list)])))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/2
Solved on 2019/3/
@author: shinjisu
"""


# ABC 102 C Linear Approximation
import statistics


def getInt(): return int(input())


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


def zeros(n): return [0]*n


def getIntLines(n): return [int(input()) for i in range(n)]


def getIntMat(n):
    mat = []
    for i in range(n):
        mat.append(getIntList())
    return mat


def zeros2(n, m): return [zeros(m)]*n


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**12


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def probC_WA_TLE():
    N = getInt()
    A = getIntList()
    dmp((N, A))
    a = [A[i]-i-1 for i in range(N)]
    dmp(a, 'a')
    m = int(statistics.mean(a))
    dmp(m, 'mean')
    s = int(statistics.pstdev(a)) + 2
    dmp(s, 'std dev')
    minSum = sum([abs(a[j]) for j in range(N)])
    dmp(minSum, 'minSum')
    for i in range(1, s):
        aSum = sum([abs(a[j]-m+i) for j in range(N)])
        dmp((aSum, -m+i), 'aSum, -m+i')
        minSum = min(minSum, aSum)
        aSum = sum([abs(a[j]-m-i) for j in range(N)])
        minSum = min(minSum, aSum)
        dmp((aSum, -m-i), 'aSum, -m-i')
        dmp(minSum, 'minSum')
    dmp(minSum, 'minSum')
    return minSum


def probC():
    N = getInt()
    A = getIntList()
    dmp((N, A))
    a = [A[i]-i-1 for i in range(N)]
    dmp(a, 'a')
    m = int(statistics.median(a))
    dmp(m, 'median')
    minSum = sum([abs(a[i]-m) for i in range(N)])
    dmp(minSum, 'minSum')
    return minSum


debug = False  # True False
ans = probC()
print(ans)
#for row in ans:
#    print(row)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
A=[a-i for i,a in enumerate(A,1)]
A.sort()
A_posi=[0 for i in range(N)]
A_posi[0]=A[0]
for i in range(1,N):
    A_posi[i]=A_posi[i-1]+A[i]
value=[0 for i in range(N)]
value[0]=A_posi[N-1]-N*A[0]
for i in range(1,N):
    value[i]=A_posi[N-1]-A_posi[i]-(N-i-1)*A[i]-A_posi[i-1]+(i)*A[i]
print(min(value))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
L = [0] * N
for i in range(N):
    L[i] = A[i] - i - 1
L.sort()
if N % 2 != 0:
    b = L[N // 2]
    ans = 0
    for i in range(N):
        ans += abs(A[i] - (b+i+1))
    print(ans)
else:
    b1 = L[N//2]
    b2 = L[N//2 + 1]
    ans1 = 0
    ans2 = 0
    for i in range(N):
        ans1 += abs(A[i] - (b1+i+1))
    for i in range(N):
        ans2 += abs(A[i] - (b2+i+1))
    print(min(ans1, ans2))

Submission status: Accepted

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

idx = N // 2

if N % 2:
    n = B[idx]
else:
    n = (B[idx] + B[idx-1]) / 2
b = list(map(lambda b: abs(b-n), B))
print(int(sum(b)))

Submission status: Accepted

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

def Linear_Approximation(i,list):
    sum = 0
    for j in range(N):
        sum += abs(list[j]-i)
    return sum

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

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()
center1 = a[N//2]
center2 = a[(N-1)//2]
ans1 = 0
ans2 = 0
for i in range(N):
  ans1 += abs(a[i] - center1)
  ans2 += abs(a[i] - center2)
print(min(ans1, ans2))

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter

def main():
  input = sys.stdin.readline
  N = int(input())
  A = list(map(int, input().split()))
  B = []
  for i in range(N):
    B.append(A[i] - (i+1))
  B = sorted(B)
  b = B[(N-1)//2]
  ans = 0
  for a in B:
    ans += abs(a-b)
  
  print(ans)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from statistics import median
n=int(input())
a=[int(i) for i in input().split()]
b=[a[i]-i for i in range(len(a))]
x=median(b)
c=[abs(i-x) for i in b]
print(int(sum(c)))

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()
ans = 0
b = 0

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

for j in A:
    ans += abs(j-b)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())

X=list(map(int,input().split()))
Y=[]
for i in range(n):
    Y.append(X[i]-(i+1))
Y.sort()
res_1=0

if n%2==1:
    m=Y[int((n-1)/2)]
    for j in range(n):
        res_1+=abs(Y[j]-m)
else:
    m=(Y[int(n/2)-1]+Y[int(n/2)])//2
    for j in range(n):
        res_1+=abs(Y[j]-m)
        

        
print(res_1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import statistics
n = int(input())
a = list(map(int, input().split()))
l = []
m = []
for i in range(n):
    m.append(a[i]-i)
med = int(statistics.median(m))
for i in range(n):
    l.append(abs(a[i]-(med+i)))
print(sum(l))

Submission status: Accepted

Solution code:
class Solver(object):
    def __init__(self):
        self.n = int(input())
        self.a_s = list(map(int, input().split(" ")))
        self._sadness = {}

    def solve(self):
        array = self.a_s.copy()
        for i in range(self.n):
            array[i] -= i + 1
        array.sort()
        b = array[len(array) // 2]
        print(self.sadness(b))
        
    def sadness(self, b):
        if b not in self._sadness:
            self._sadness[b] = sum(abs(self.a_s[i] - (b+i+1)) for i in range(self.n))
        return self._sadness[b]


if __name__ == "__main__":
    s = Solver()
    s.solve()

Submission status: Accepted

Solution code:
import statistics
n=int(input())
L=list(map(int, input().split()))
LL=[L[i]-i-1 for i in range(n)]
m=statistics.median_low(LL)
LLL=[abs(LL[i]-m) for i in range(n)]
print(sum(LLL))

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:
  t = B[N // 2]
else:
  t = (B[N // 2] + B[N // 2 - 1]) // 2

su = sum([abs(i - t) for i in B])
print(su)

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()

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [A[i-1] - i for i in range(1, len(A) + 1)]
B.sort()
def f(x):
    sum = 0
    for b in B:
        sum += abs(b-x)
    return sum
if len(B) % 2 == 0:
    print(f((B[len(B)//2] + B[len(B)//2 - 1])//2))
else:
    print(f(B[int(len(B)/2)]))

Submission status: Accepted

Solution code:
a = int(input())
x = list(map(int, input().split()))
for i in range(a):
    x[i]-=i+1
x.sort()
#print(x)
q = (x[a//2]+x[a//2-1])
if q >=0:
    if a%2==0:
        p=(q//2)
    else:
        p=x[a//2]
else:
    if a%2==0:
        p=-((-1)*q//2)
    else:
        p=x[a//2]
s=0
#print(p)
for i in range(a):
    s+=abs(x[i]-p)
print(s)

Submission status: Accepted

Solution code:
import math


def solve(N, As):
    As = [a - (i + 1) for i, a in enumerate(As)]
    high = 10 ** 10
    low = -10 ** 10
    while True:
        b = (high + low) // 2
        tans1 = sum(abs(a - b) for a in As)
        tans2 = sum(abs(a - b + 1) for a in As)
        if low == b:
            return min(tans1, tans2)

        if tans1 > tans2:
            high = b
        elif tans1 < tans2:
            low = b
        else:
            return min(tans1, tans2)


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

Submission status: Accepted

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

from statistics import median
#b = math.floor(sum(A) / N)
b = median(A)
ans = 0
for i in range(N):
    ans += abs(A[i] - b)
print(int(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n =int(input())
a = list(int(i) for i in input().split())
sa = []
for i in range(n):
  sa.append(a[i]-i-1)
sa.sort()
b = sa[n//2]
su =0
for i in range(n):
  su+= abs(sa[i]-b)
print(su)

Submission status: Accepted

Solution code:
import statistics
n=int(input())
A=list(map(int,input().split()))
B=[0]*n
for i in range(n):
    B[i]=A[i]-(i+1)
b=statistics.median(B)
C=[0]*n
for i in range(n):
    C[i]=abs(B[i]-b)
print(int(sum(C)))

Submission status: Accepted

Solution code:
N = input()

A = map(int,raw_input().split())

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

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

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

print ans

Submission status: Accepted

Solution code:
N = int(input())
A = [int(n) for n in input().split()]

A = sorted([n - i - 1 for i, n in enumerate(A)])

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

diff = [abs(n - b) for n in A]
sad = sum(diff)

print(sad)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from functools import reduce
# ----------------------------------------------------------------
# Use Solve Function

def solve(lines):
    def func(s, i):
        re = s + abs(i - B)
        return re

    N = int(lines.pop(0))
    L = list(map(int, lines.pop(0).split(' ')))
    L = [ x - (i+1) for (i, x) in enumerate(L) ]
    L.sort()
    B = L[int(len(L) / 2)]
    print(reduce(func, L, 0))
    #print(reduce(lambda n, i: n + abs(i - b), L))
    #print(list(map(lambda i:  abs(i - b), L)))

#
# main
#

# 1. use list instead of stdin

# contents = '''\
# 7
# 1 1 1 1 2 3 4\
# '''
# lines = contents.split('\n')

# 2. use stdin

lines = [x.strip() for x in sys.stdin.readlines()]

#
# solve !!
#
solve(lines)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]

import statistics
check = []
for i in range(n):
    check.append(a[i] - (i+1))
b = statistics.median(sorted(check))

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

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int,input().split()))
for i in range(N):
    L[i] = L[i] - (i+1)
L = sorted(L)
#print(L)
ans = 0
n=len(L)
med = int(L[(n+1)//2-1])
#print(med)
for i in range(N):
    ans+=abs(L[i]-med)
print(ans)

Submission status: Accepted

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


main()

Submission status: Accepted

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

A = []
for i,a_ in enumerate(A_):
    A.append(a_-i-1)

d = {}
for a in A:
    if a in d.keys():
        d[a] += 1
    else:
        d[a] = 1

count = 0
for d_ in sorted(d.items()):
    if count >= len(A)/2:
        break
    count += d_[1]
    d_prev = d_[0]

b1 = d_prev
b2 = d_[0]

ans1 = 0
ans2 = 0
for a in A:
    ans1 += abs(a-b1)
    ans2 += abs(a-b2)

print(min(ans1,ans2))

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]

import statistics
check = []
for i in range(n):
    check.append(a[i] - (i+1))
check = sorted(check)
b = statistics.median(check)

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

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

ans = sum(abs(aa - t) for aa in a)
print(ans)

Submission status: Accepted

Solution code:
import statistics


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

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

M = int(statistics.median(A))
R = []

for m in [M-2, M-1, M, M+1, M+2]:
    R.append(sum([abs(a - m) for a in A]))

print(min(R))

Submission status: Accepted

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

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()
b = A[N//2]
A = list(map(lambda x: abs(x-b), A))
print(sum(A))

Submission status: Accepted

Solution code:
import sys
from functools import reduce
input = sys.stdin.readline

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from statistics import median

N = int(input())
A = list(map(int,input().split()))
Asort = sorted([A[i]-i-1 for i in range(N)])
# print(Asort)

b_tmp = int(median(Asort))

submin = [abs(A[i]-b_tmp-i-1) for i in range(N)]
# print(submin)
minA = sum(submin)

print(minA)

Submission status: Accepted

Solution code:
from statistics import median

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

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

ave=int(median(a))
ans=0

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

Submission status: Accepted

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

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

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

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

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

    print(err)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

if N % 2 == 1:
    median = B[N//2]
    print(sum([abs(b - median) for b in B]))
else:
    median1 = B[N//2]
    median2 = B[N//2+1]
    print(min(sum([abs(b - median1) for b in B]), sum([abs(b - median2) for b in B])))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
for i in range(N):
    A[i] -= (i+1)

A.sort()

if N % 2 != 0:
    num = A[N//2]
    A = [abs(i - num) for i in A]
    print(sum(A))
else:
    num1 = A[N//2]
    num2 = num1 -1
    A1 = [abs(i - num1) for i in A]
    A2 = [abs(i - num2) for i in A]
    print(min(sum(A1), sum(A2)))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
B = [A[i]-i-1 for i in range(N)]
B.sort()
b = N//2
ans = sum([abs(B[i]-B[b]) for i in range(N)])
print(ans)

Submission status: Accepted

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

sorted_A = sorted(A)

if len(A) == 1:
    ans = 0
else:
    ans = sum(map(lambda x: abs(x-sorted_A[N//2]),A))

print(ans)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
#ABC102C
N=int(input())
series = list(map(int,input().split()))
seriesSub = [series[i] - (i+1) for i in range(len(series))]

def cry(a):
	ret=0
	for s in seriesSub:
		ret += abs(s-a)
	return ret

def BinarySeach(hi,lo):
	mid = (hi + lo) // 2
	while hi > lo:
		mid = (hi + lo) // 2
		if mid != len(series):
			if cry(mid+1) >= cry(mid):
				hi = mid
		if mid != 0:
			if cry(mid-1) >= cry(mid):
				lo = mid
	else:
		return cry(mid)
h = max(seriesSub)
l = min(seriesSub)
print(BinarySeach(h,l))

Submission status: Accepted

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


import numpy as np

A_N_list = np.array([A_list[i] - (i+1)  for i in range(len(A_list))])


AN_list = sorted(A_N_list)


if len(AN_list) % 2 == 0:
    b = AN_list[int(len(AN_list)/2)-1]
else:
    b = AN_list[int((len(AN_list)+1)/2)-1]

count = 0
for id,i in enumerate(A_list):
    count += abs(i-(b+id+1)) 

print(count)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:

n = int(input())
a_list = list(map(int,input().split(" ")))
a_list = [A-(i+1) for i,A in enumerate(a_list)]

a_list = sorted(a_list)
if n%2 != 0:
    median = a_list[int((n-1)/2)]
else:
    median = int((a_list[int((n+1)/2)]+a_list[int((n-1)/2)])/2)

sad = 0
for a in a_list:
    sad += abs(a - median)
print(sad)

Submission status: Accepted

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

def sadness(a, mid):
    sad = 0
    for i in range(mid):
        sad += a[mid] - a[i]
    for i in range(mid+1,len(a)):
        sad += a[i] - a[mid]
    return sad

if n % 2 != 0:
    print(sadness(A_list, n//2))
else:
    print(min(sadness(A_list, n//2), sadness(A_list, n//2+1)))

Submission status: Accepted

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

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from math import *
N = int(input().strip())
A = list(map(int, input().split()))
B = [A[i] - (i+1) for i in range(0, N)]

if N == 1:
  print(0)
  sys.exit()

def s(b):
    return sum([abs(Bi - b) for Bi in B])

def check():
    left = s(bmin) - s(bmin+1) >= 0
    right = s(bmax-1) - s(bmax) <= 0
    if right and left:
        # 極値ある
        return 0
    if left:
        # 単調減少
        return 1
    # 単調増加
    return 2

bmin = min(B)
bmax = max(B)
stype = check()
if stype == 0:
    bnow = bmin
    for i in range(0, 40):
        if s(bnow) - s(bnow+1) < 0:
            bmax = bnow
            bnext = round((bnow + bmin) / 2)
        else:
            bmin = bnow
            bnext = round((bnow + bmax) / 2)
        if bnext == bnow:
            break
        bnow = bnext
    smin = s(bnow)
elif stype == 1:
    smin = s(bmax)
elif stype == 2:
    smin = s(bmin)

print(smin)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
B = []

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

B.sort()
medianB = B[n // 2]

Sum = 0
for i in range(n):
    Sum += abs(A[i] - (medianB + (i + 1))) 
    
print(Sum)

Submission status: Accepted

Solution code:
def s(aa, b):
    return sum(abs(a - (b + i + 1)) for i, a in enumerate(aa))


def main():
    n = int(input())
    aa = list(map(int, input().split()))
    bb = sorted(a - (i + 1) for i, a in enumerate(aa))
    if len(bb) % 2 != 0:
        b = bb[(len(bb) - 1) // 2]
    else:
        b = (bb[len(bb) // 2] + bb[len(bb) // 2 - 1]) // 2
    print(s(aa, b))


if __name__ == '__main__':
    main()

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)
M = B[int((N - 1)/2)]
ans = 0

for i in range(N):
    t = B[i] - M
    if t < 0:
        t = (-1) * t
    ans += t

print(ans)

Submission status: Accepted

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

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()
ans = 0
if n%2==0:
  c1 = (a[n//2-1]+a[n//2])//2
  c2 = (a[n//2-1]+a[n//2]-1)//2 + 1
  sum1 = 0
  sum2 = 0
  for i in range(n):
    sum1 += abs(a[i]-c1)
    sum2 += abs(a[i]-c2)
  ans = min(sum1, sum2)
else:
  c = a[(n-1)//2]
  for i in range(n):
    ans += abs(a[i]-c)
print(ans)

Submission status: Accepted

Solution code:
a = int(input())
ar = list(map(int,input().split(" ")))
ar = [r - (i+1) for i,r in enumerate(ar)]
br = sorted(ar)
b = br[a//2]
count = 0
for i in range(a):
    count += abs(ar[i] - b)
print(count)

Submission status: Accepted

Solution code:
N = int(input())
a = [int(n) for n in input().split(" ")]
a = [a[n] - n - 1  for n in range(N)]
a = sorted(a)
if(N%2==1):
    median = a[int(N/2)]
else:
    median = (a[int(N/2)-1] + a[int(N/2)] )/ 2
sum = 0
for i in range(N):
    sum += abs(a[i] - median)
print(int(sum))

Submission status: Accepted

Solution code:
n = int(input())
li = list(map(int,input().split()))
ans = 0

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

if n%2 == 1:
        for i in range((n-1)//2):
                ans -= li[i]
        for i in range((n+1)//2, n):
                ans += li[i]
elif n%2 == 0:
        for i in range(n//2):
                ans -= li[i]
        for i in range(n//2,n):
                ans += li[i]

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 = sorted(a)

def calc(mid):
  res = 0
  for i in a:
    res += abs(i-mid)
  return res

if n%2==1:
  res = calc(a[n//2])
else:
  res = float('inf')
  if (a[n//2-1]+a[n//2])%2==0:
    res = calc((a[n//2-1]+a[n//2])//2)
  else:
    mid = (a[n//2-1]+a[n//2]) // 2
    res = min(calc(mid), calc(mid+1))

print(res)