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 = [int(i) for i in input().split()]

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

A.sort()

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

s =  [ i-(n+1) for n, i in enumerate(s)]

s.sort()

if n%2==0 :
  m = (s[n//2 - 1] + s[n//2]) // 2
else :
  m = s[n//2]

ans = 0
for i in s:
  ans+= abs(i -m)
  
print(ans)

Submission status: Accepted

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

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

A.sort()
if N%2 == 1 :
    med = A[N//2]
else :
    med = (A[N//2 - 1] + A[N//2]) // 2

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

print(int(ans))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
c=[a[i]-i-1 for i in range(n)]
cum_c=[0]*n
c.sort()
cum_c[0]=c[0]
for i in range(1,n):
  cum_c[i]=cum_c[i-1]+c[i]
ans=min(cum_c[n-1]-n*c[0],n*c[n-1]-cum_c[n-1])
for i in range(1,n):
  ans=min(ans,cum_c[n-1]-2*cum_c[i-1]+(2*i-n)*c[i-1])
  ans=min(ans,cum_c[n-1]-2*cum_c[i-1]+(2*i-n)*c[i])
print(ans)

Submission status: Accepted

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

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

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

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

print(res)

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

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

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

print(res)

Submission status: Accepted

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

N=int(readline())
A=list(map(int,readline().split()))
B=[0]*N
sumB=0
for i in range(N):
  B[i]=A[i]-(i+1)
  
B=sorted(B)
mid=0
if len(B)&1:
  mid=B[N//2]
else:
  mid=(B[N//2-1]+B[N//2])//2
  
ans=0
for i in range(N):
  ans+=abs(B[i]-mid)

print(ans)

Submission status: Accepted

Solution code:
import statistics
N = int(input())
A = list(map(int,input().split()))
s = 0
X = []

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

b = statistics.median(A)

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

print(s)

Submission status: Accepted

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

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

median=median(B)
ans=0
for i in range(n):
    ans +=abs(A[i]-(median+i+1))
print(int(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()
idx = n//2
print( sum( [ abs(b-B[idx]) for b in B ] ) )

Submission status: Accepted

Solution code:
import sys
import math
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
n=int(input())
A=list(map(int,input().split()))
SA=[0 for i in range(n)]
for i in range(n):
    SA[i]=A[i]-i-1
SA.sort()

if n%2==0:
    geta=(SA[n//2]+SA[n//2-1])//2
else:
    geta=SA[n//2]
ans=0
for i in range(n):
    ans+= abs(A[i]-(geta+i+1))
print(ans)

Submission status: Accepted

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

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

from statistics import median
z=int(median(l))

x=0
for j in range(n):
    x+=abs(l[j]-z)

print(x)

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)

from statistics import mean, median,variance,stdev
z=int(median(l))

x=0
for j in range(n):
    x+=abs(l[j]-z)

print(x)

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()
b = B[N//2]
print(sum([abs(A[i]-i-b-1) for i in range(N)]))

Submission status: Accepted

Solution code:
"""
102 C
"""

import math

def read_input():
    n = int(input())
    alist = list(map(int, input().split()))

    return n, alist


def sum_abs(alist, b):
    return sum([abs(a - b) for a in alist])


def submit():
    n, alist = read_input()

    alist = [a - (i + 1) for i, a in enumerate(alist)]
    alist.sort()

    if n % 2 == 0:
        b_min, b_max = alist[n // 2], alist[n // 2 + 1]
        print(min(sum_abs(alist, b_min), sum_abs(alist, b_max)))
    else:
        print(sum_abs(alist, alist[n // 2]))


if __name__ == "__main__":
    submit()

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()
b = B[N//2]
print(sum([abs(A[i]-b-i-1) for i in range(N)]))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))

    A_tmp = []
    for i in range(n):
        A_tmp.append(A[i] - (i+1))
    A_tmp_sorted = sorted(A_tmp)
    sum1 = 0
    sum2 = 0
    if n%2 == 0:
        for i in range(n):
            sum1 += abs(A_tmp_sorted[n//2]-A_tmp[i])
            sum2 += abs(A_tmp_sorted[n//2-1]-A_tmp[i])
        print(min(sum1,sum2))
    else:
        for i in range(n):
            sum1 += abs(A_tmp_sorted[n//2]-A_tmp[i])
        print(sum1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

b = sorted_num[n//2]
print(sum([abs(b-i) for i in sorted_num]))

Submission status: Accepted

Solution code:

N = int(input())

ARR = [int(s) for s in input().split(" ")]

import numpy as np
def calculate(n,arr):
    srr = np.array([arr - index - 1 for index,arr in enumerate(arr)])

    srr = sorted(srr)

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



    return sum(np.fabs(srr - b))

result = int(calculate(N,ARR))

print(result)

Submission status: Accepted

Solution code:
n=int(input())

t = list(map(int,input().split()))

memo = []

for i in range(n):
    memo.append(t[i]-i-1)
memo.sort()

if n%2 == 0:
  p = n//2-1
else:
  p = (n-1)//2

ans = 0

for j in range(n):
  ans += abs(memo[j] - memo[p])

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import statistics

n = int(input())
a = list(map(int,input().split()))
s = [a[i] - i - 1 for i in range(n)]
ans = 0
b = statistics.median(s)

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

Submission status: Accepted

Solution code:
import bisect

a=[]
s=[]
def asff(a,b,s,n):
    m=bisect.bisect(a,b)
    if m<=0:
        asf=-n*b+s[n-1]
    elif m<n:
        asf=(2*m-n)*b+s[n-1]-2*s[m-1]
    elif n<=m:
        asf=n*b-s[n-1]
    return asf

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

#n=5
#stra="2 2 3 5 5"
#ans=2

#n=9
#stra="1 2 3 4 5 6 7 8 9"
#ans=0

#n=6
#stra="6 5 4 3 2 1"
#ans=18

#n=7
#stra="1 1 1 1 2 3 4"
#ans=6

#a=list(map(int,stra.split()))

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

s=[a[0]]
for i in range(1,n):
    s.append(s[i-1]+a[i])
    
bmin=min(a)-n
bmax=max(a)+n

b1=bmin
b5=bmax+1
b2=b1+int((b5-b1)/4)
b3=b1+int((b5-b1)/2)
b4=b1+int((b5-b1)/4*3)
#b2=b1+(b5-b1)//4
#b3=b1+(b5-b1)//4*2
#b4=b1+(b5-b1)//4*3
#print("b1",b1,"b5",b5)
    
asmin=bmax*n
#m0=0
m1=bisect.bisect(a,bmin)


while b1+1<b5:
    c=[]
    c.append([asff(a,b1,s,n),b1])
    c.append([asff(a,b2,s,n),b2])
    c.append([asff(a,b3,s,n),b3])
    c.append([asff(a,b4,s,n),b4])
    c.append([asff(a,b5,s,n),b5])
    c.sort()
    asf=c[0][0]
    d=[]
    d.append(c[0][1])
    d.append(c[1][1])
    d.append(c[2][1])
    d.sort()
    b1=d[0]
    b5=d[2]
    b2=b1+int((b5-b1)/4)
    b3=b1+int((b5-b1)/2)
    b4=b1+int((b5-b1)/4*3)
    
#    print("b1",b1,"b5",b5,"d0",d[0],"asf",asf)
    if asf<asmin:
        asmin=asf

print(asmin)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
B = [A[i] - i for i in range(n)]
B.sort()
if n % 2 == 0:
    m = [B[n //2 -1], B[n // 2 + 1]]
    ans1 = [abs(B[i] - m[0]) for i in range(n)]
    ans2 = [abs(B[i] - m[1]) for i in range(n)]
    print(min(sum(ans1), sum(ans2)))
else:
    m = B[n // 2]
    ans = [abs(B[i] - m) for i in range(n)]
    print(sum(ans))

Submission status: Accepted

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

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

Submission status: Accepted

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

b = [x-(i+1) for i,x in enumerate(a)]
b.sort()

x = b[n//2]

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

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc102/tasks/arc100_a
# Aの数列を前処理で加工し、順番に依存しない数列Bに加工する
# abs(Bi-x)の和を最小化するxはBの中央値である。(立式しxで微分したのちKについて増減表を書いてみよ)
# それを答えとすれば良い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


N = read_a_int()
A = read_ints()
B = [a - i for a, i in zip(A, range(1, N + 1))]
B.sort()

x = B[N // 2]
ans = 0
for b in B:
    ans += abs(x - b)


print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc102/tasks/arc100_a
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


class cumsum1d:
    def __init__(self, ls: list):
        '''
        1次元リストを受け取る
        '''
        from itertools import accumulate
        self.ls_accum = [0] + list(accumulate(ls))

    def total(self, i, j):
        # もとの配列lsにおける[i,j)の中合計
        return self.ls_accum[j] - self.ls_accum[i]


N = read_a_int()
A = read_ints()
if N == 1:
    print(0)
    exit()
B = [a - i for a, i in zip(A, range(1, N + 1))]
B.sort()

# 絶対値を区切る境目はどこがよいか？
B_cum = cumsum1d(B)
ans = 10**15
for k in range(1, N):
    tmp_sum = -B_cum.total(0, k) + B_cum.total(k, N)
    add = min((2 * k - N) * B[k - 1], (2 * k - N) * B[k])
    ans = min(ans, tmp_sum + add)


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

#中央値
med = b[n//2]

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

Submission status: Accepted

Solution code:
def binsearch(l, r, fn):
    while r - l > 1:
        m = (l + r) // 2
        if fn(m):
            l = m
        else:
            r = m
    return l

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A = sorted(a - i for i, a in enumerate(A, 1))
    def h(t):
        return sum(abs(a - t) for a in A)
    l = A[0]
    r = A[-1]
    while r - l > 1:
        m = (l + r) // 2
        t = h(m + 1) - h(m)
        if t == 0:
            return h(m)
        if t < 0:
            l = m + 1
        else:
            r = m
    return min(h(l), h(r))

print(main())

Submission status: Accepted

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

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

A.sort()

b = A[len(A) // 2]
c = A[len(A) // 2 - 1]

tmp1, tmp2 = 0, 0

for a in A:
    tmp1 += abs(a - b)
    tmp2 += abs(a - c)

print(min(tmp1, tmp2))

Submission status: Accepted

Solution code:
n = int(input())

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


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

a.sort()

x=a[int(int(len(a))/2)]

ans = 0
for i in range(len(a)):
    ans =ans+ abs(a[i]-x)

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

median = a[len(a) // 2]
cnt = 0
for i in range(len(a)):
    cnt += abs(a[i] - median)

print(cnt)

Submission status: Accepted

Solution code:
import statistics

def main():
    n = int(input())
    A = [int(e) for e in input().split()]

    B = [a - ai - 1 for ai, a in enumerate(A)]
    m = int(statistics.median(B))
    ans = sum([abs(b - m) for b in B])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

if N % 2 != 0:
    b = B[(N+1)//2 - 1]
    ans = 0
    for i in range(len(B)):
        ans += abs(B[i] - b)
else:
    b1 = B[N//2 - 1]
    ans1 = 0
    for i in range(len(B)):
        ans1 += abs(B[i] - b1)
    b2 = B[N//2]
    ans2 = 0
    for i in range(len(B)):
        ans2 += abs(B[i] - b2)
    ans = min(ans1, ans2)
print(ans)

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

Submission status: Accepted

Solution code:
# 数直線上のxとA1-1, A2-2, ...との距離と言い換えられる
n = int(input())
A = list(map(int, input().split()))
A = sorted([a - (i+1) for i, a in enumerate(A)])
x = A[n//2]
print(sum(map(lambda a: abs(a-x), A)))

Submission status: Accepted

Solution code:
N = int(input())
A_list = [int(item)-(index+1) for index, item in enumerate(input().split())]

A_list.sort()
b = A_list[len(A_list)//2]

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

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
N, *A = map(int, open(0).read().split())
for i in range(N):
  A[i] -= i+1

A.sort()
L = bisect_left(A,0)
R = bisect_right(A,0)
ans = 0
if L>N-L:
  l = 2*L-N
  n = l//2+1 if l%2!=0 else l//2
  c = A[L-n]
  for i in range(N):
    ans += abs(A[i]-c)
elif R<N-R:
  r = N-2*R
  n = r//2+1 if r%2!=0 else r//2
  c = A[R+n-1]
  for i in range(N):
    ans += abs(A[i]-c)
else:
  for i in range(N):
    ans += abs(A[i])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A_list = [int(item)-(index+1) for index, item in enumerate(input().split())]

tmp_list = sorted(A_list)
b = tmp_list[N//2]

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

print(answer)

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()
b = A[N//2]
sad = 0
for i in range(N):
    sad += abs(A[i]-b)

print(sad)

Submission status: Accepted

Solution code:
#102_C
def Mid(A):
    A=sorted(A)
    N=len(A)
    return A[N//2]
def Sad(A,b):
    return sum([abs(A[i]-b) for i in range(len(A))])
N=int(input())
A=list(map(int,input().split()))
Ai=[A[i]-(i+1) for i in range(N)]
print(Sad(Ai,Mid(Ai)))

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()
if N%2==0:
  b=(B[N//2]+B[N//2-1])//2
else:
  b=B[N//2]
sad=0
for j in range(N):
  sad=sad+abs(B[j]-b)
print(sad)

Submission status: Accepted

Solution code:
import collections
n=int(input())
a=list(map(int,input().split() ))
absa=[]
za=[]
for i in range(n):
    za.append(a[i]-(i+1))
#print(za)
#print(sum(za))
za.sort()
z=sum(za)
#print(z)
if n%2==1:
    b=za[n//2]
else:
    b=(za[n//2-1]+za[n//2])//2

#print(b)
for i in range(n):
    absa.append(abs(a[i]-(b+(i+1))))
#print(absa)
print(sum(absa))

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
    
B.sort()
X=B[int(N/2)]

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
tmp = []
#b- (a-1)

for i in range(1, n+1):
    tmp.append(a[i-1] - i)
tmp.sort()
#print(tmp)
b = tmp[n//2]
ans = 0
for i in range(1, n+1):
    ans += abs(a[i-1] - (b+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.sort()
x=a[n//2]
ans=0
for i in a:
  ans+=abs(i-x)
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.sort()
m = b[n // 2]
ans = 0
for i in b:
    ans += abs(i - m)
print(ans)

Submission status: Accepted

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

ls = [0]*n
sum = 0
for i in range(n):
  ls[i] = l[i] - (i+1)

ls.sort()
med = ls[n//2]

for i in ls:
  sum += abs(i - med)
print(sum)

Submission status: Accepted

Solution code:
def main():
    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()
    answer = 0
    if N % 2:
        median = B[(N - 1) // 2]
        for b in B:
            answer += abs(b - median)
    else:
        median = [B[N // 2], B[N // 2 - 1]]
        for b in B:
            answer += abs(b - median[0])
        tmp = 0
        for b in B:
            tmp += abs(b - median[1])
        answer = min(answer, tmp)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
i = np.array([j for j in range(1, n+1)])
b = a - i
ans = sorted(b)
if n % 2 == 1:
    index = n//2
    print(np.sum(abs(b - ans[index])))
else:
    index = n//2 - 1
    x1 = np.sum(abs(b-ans[index]))
    x2 = np.sum(abs(b - ans[index+1]))
    print(min(x1, x2))

Submission status: Accepted

Solution code:
from math import floor

def solve(n, A):
    B = sorted([a - (i + 1) for i, a in enumerate(A)])
    b = B[n // 2]
    ret = sum(abs(a - (b + i + 1)) for i, a in enumerate(A))
    if n % 2 == 0:
        b = B[n // 2 + 1]
        tmp = sum(abs(a - (b + i + 1)) for i, a in enumerate(A))
        if tmp < ret:
            ret = tmp
    return ret

_n = int(input())
_A = list(map(int, input().split()))
print(solve(_n, _A))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
A2=[0]*N

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

if N%2==1:
    med=A2[N//2]
else:
    med=(A2[N//2]+A2[N//2-1])//2


ans=10**20
for dx in [-1,0,1]:
    temp=0
    for i in range(N):
        temp+=abs(A[i]-(med+dx+i+1))
    ans=min(ans,temp)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

A.sort()

if len(A)%2!=0:
  b=A[len(A)//2]
else:
  b=(A[len(A)//2]+A[len(A)//2-1])//2
  
ans=0
for i in range(N):
  ans+=abs(A[i]-b)
print(ans)

Submission status: Accepted

Solution code:
num = int(input())
list_i = list(map(int, input().split())) 
#b=min(i)-num
#b=max(i)-1
for j in range(num):
  list_i[j]=list_i[j]-j-1
list_i.sort()
b=list_i[int(num/2)]
sum=0
for i in range(num):
  sum +=abs(list_i[i]-b)
print(sum)

Submission status: Accepted

Solution code:

import numpy as np
import sys
sys.setrecursionlimit(100000)



def acinput():
    return list(map(int, input().split(" ")))



directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

N=int(input())
A=np.array(acinput())
s=A-range(1,N+1)

s=sorted(s)
m=round(np.median(s))

res=0
for i in range(N):
    res+=np.abs(A[i]-m-(i+1))

print(int(res))

Submission status: Accepted

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

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

b1, b2 = A[N // 2], A[N // 2 - 1]
tmp1, tmp2 = 0, 0

for a in A:
  tmp1 += abs(a - b1)
  tmp2 += abs(a - b2)
  
print(min(tmp1, tmp2))

Submission status: Accepted

Solution code:
import math

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

lis = []
for index, i in enumerate(li):
  lis.append(i - (index + 1))

lis.sort()
x = lis[math.floor(N/2)]

ans = 0
for i in lis:
  ans += max(x - i, -x + i)

print(ans)

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

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

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

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

ans1 = 0
ans2 = 0
for a in A:
    ans1 += abs(a-b)
    ans2 += abs(a-(b+1))

print(min(ans1, ans2))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
def cal(A,b):
    a = 0
    for i in range(len(A)):
        a += abs(A[i] - b)
    return a
#cal(A,b)の値の最小値
A_2 = A
for i in range(N):
    A_2[i] = A[i] - (i+1)
A_2.sort()

if N%2 == 0:
    cnum = N//2 - 1
    chu = A_2[cnum]
else:
    cnum = (N-1)//2
    chu = A_2[cnum]
ans = cal(A_2,chu)
print(ans)

Submission status: Accepted

Solution code:
import sys
n=int(input())
A=list(map(int,input().split()))
for i in range(n):
    A[i]=A[i]-(i+1)
if n==1:
    print(0)
    sys.exit(0)
A2=sorted(A)
ans=0
center=A2[(n-1)//2]
for i in range(n):
    ans+=abs(A2[i]-center)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A_sum = [a-i for i,a in enumerate(A)]
middle = sorted(A_sum)[len(A)//2]

f = [abs(a-middle) for a in A_sum]
print(sum(f))

Submission status: Accepted

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

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))
C = sorted(B)
ans = 0
bns = 0

if N % 2 == 1:
  a = C[(N-1)//2]
  for i in range(N):
    ans += abs(A[i]-(a+i+1))
  print(ans)
else:
  a = C[N//2]
  b = C[N//2-1]
  for i in range(N):
    ans += abs(A[i]-(a+i+1))
    bns += abs(A[i]-(b+i+1))
  print(min(ans, bns))

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()
if n%2==1:
    median=a[(n-n%2)//2]
    ans=0
    for i in range(n):
        ans+=abs(a[i]-median)
else:
    median1=a[n//2-1]
    median2=a[n//2]
    ans1,ans2=0,0
    for i in range(n):
        ans1+=abs(a[i]-median1)
        ans2+=abs(a[i]-median2)
        ans=min(ans1,ans2)
print(ans)

Submission status: Accepted

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

#Bi = Ai - iなる数列Bを作成し、ソートした数列の変化点となる値をｘとする。これが、悲しさを最小値とする’ｂ’となる。
B = []
for i in range(N):
    b = A[i] -(i + 1)
    B.append(b)

B = sorted(B,reverse = False)
x = B[N//2]
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
from statistics import median_low, median_high

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


b1 = median_low(a)


b2 = median_high(a)
ans1 = 0
ans2 = 0

for aa in a:
    ans1 += abs(aa-b1)
    ans2 += abs(aa-b2)
print(min(ans1, ans2))

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int,input().split()))
sa = []
for i in range(n):
    sa.append(l[i]-(i+1))
sa.sort()
ans= 0
center = sa[n//2]
for i in range(n):
    ans += abs(sa[i]-center)
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))
C=sorted(B)
ans=0
bns=0
if N%2==1:
  a=C[(N-1)//2]
  for i in range(N):
    ans+=abs(A[i]-(a+i+1))
  print(ans)
else:
  a=C[N//2]
  b=C[N//2-1]
  for i in range(N):
    ans+=abs(A[i]-(a+i+1))
    bns+=abs(A[i]-(b+i+1))
  print(min(ans,bns))

Submission status: Accepted

Solution code:
def calc_sadness(b):
    ans = 0
    for a in A:
        ans += abs(a - b)
    return ans


N = int(input())
A = []
for idx, a in enumerate(map(int, input().split())):
    A.append(a - idx - 1)
A.sort()

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

print(min(map(calc_sadness, b)))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

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

sorted_num = sorted([a[i] - i for i in range(len(a))])

b = sorted_num[len(sorted_num)//2]
print(sum([abs(b-i) for i in sorted_num]))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
nums = [int(i) for i in input().split()]

new_nums = np.array(sorted([nums[i-1] - i for i in range(1, N+1)]))
b = int(np.median(new_nums))

s = 0
for i in range(1, N+1):
    s += abs(nums[i-1] - (b + i))
print(s)

Submission status: Accepted

Solution code:
import sys
import collections

input = sys.stdin.readline


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

    B = []

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

    for i, v in enumerate(A):
        x = v - (i + 1)
        B.append(x)

    B.sort()

    if N & 1:
        b = B[N // 2]
        ans = 0
        for v in B:
            ans += abs(v - b)
        print(ans)
    else:
        b = (B[N // 2] + B[(N // 2) - 1]) // 2
        ans = 0
        for v in B:
            ans += abs(v - b)
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from statistics import median_high

N = int(input())
A = list(map(int, input().split()))
A = [A[i] - (i + 1) for i in range(N)]
b = median_high(A)
print(sum(abs(x - b) for x in A))

Submission status: Accepted

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

a.sort()
m = n // 2
b = a[m] if n % 2 == 1 else (a[m - 1] + a[m]) // 2

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

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
hikumono = n * (n-1)//2
A = np.array(list(map(int, input().split())))
B = np.array([i+1 for i in range(n)])
C=A-B
heikin1 = int(np.median(C))
heikin2 = heikin1 + 1
heikin3 = heikin1 - 1
ans1 = abs(C-heikin1).sum()
ans2 = abs(C-heikin2).sum()
ans3 = abs(C-heikin3).sum()
print(min(ans1, ans2, ans3))