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:
import numpy as np

N = int,input()
alist = list(map(int,input().strip().split()))

s = np.array([i for i in range(len(alist))])
slist = alist-s
slist.sort()

abs_slist = list(map(lambda x:abs(x-slist[len(slist)//2]), slist))

print(sum(abs_slist))

Submission status: Accepted

Solution code:
def median_low(A):
    A.sort()
    b=A
    n = len(A)
    if n%2==1:
        med =b[n//2]
    else:
        x=b[n//2-1]
        y=b[n//2]
        med=(x+y)/2
        if med!=int(med):
            med=x
        else:
            med=int(med)
    return med


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

A = [v-i-1 for i,v in enumerate(A)]
x = median_low(A)

print(sum(abs(v - x) for v in A))

Submission status: Accepted

Solution code:
from statistics import median_low

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

A = [v-i-1 for i,v in enumerate(A)]
x = median_low(A)

print(sum(abs(v - x) for v in A))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(n):
  x=a[i]-i-1
  b.append(x)
b.sort()
if n%2==1:
  med=b[n//2]
else:
  x=b[(n//2)-1]
  y=b[(n//2)]
  med=(x+y)/2
  if med!=int(med):
    med=x
  else:
    med=int(med)
ans=0
for i in range(n):
  ans+=abs(b[i]-med)
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] = A[i] - (i+1)
A.sort()

if N % 2 == 0:
	med1 = A[N // 2 - 1]
	med2 = A[N //2]
	ans = min(sum([abs(a - med1) for a in A]), sum([abs(a - med2) for a in A]))

else:
	med = A[N // 2]
	ans = sum([abs(a - med) for a in A])
	
print(ans)

Submission status: Accepted

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

X = [a - i - 1 for i, a in enumerate(A)]
X.sort()
if N % 2 != 0:
    med = X[N // 2]
    ans = sum([abs(x - med) for x in X])
else:
    med1 = X[N // 2 - 1]
    med2 = X[N // 2]
    ans = min(sum([abs(x - med1) for x in X]), sum([abs(x - med2) for x in X]))
print(ans)

Submission status: Accepted

Solution code:
def calc(A, b):
    retval = 0
    for a in A:
        retval += abs(a - b)
    return retval
 
 
def main():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(N):
        A[i] -= (i + 1)
 
    left = min(A)
    right = max(A)
 
    while left < right:
        c1 = (left + left + right) // 3       # floor
        c2 = -(-(left + right + right) // 3)  # ceil
        if calc(A, c1) <= calc(A, c2):
            right = c2 - 1
        else:
            left = c1 + 1
    print(calc(A, left))
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
array = list(map(int,input().split(" ")))
arra = []
i = 0
while i < N:
  arra.append(array[i]-(i+1))
  i+=1
arra.sort()
if N%2 == 0:
  m = int((0.5)*(arra[int(N/2)-1]+arra[int(N/2)]))
else:
  m = arra[int((N-1)/2)]
j = 0
sum = 0
while j < N:
  sum+=abs(array[j]-(m+j+1))
  j+=1
print(int(sum))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import statistics
import math

N=int(input())
A_array=list(map(int,input().split()))
B_array=[]
for i in range(len(A_array)):
    i=i+1
    B_array.append(A_array[i-1]-i)
    i=i-1
mid=statistics.median(B_array)

ans=0
for i in  range(len(B_array)):
    ans+=abs(B_array[i]-mid)
print(int(ans))

Submission status: Accepted

Solution code:
import sys

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

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

if n % 2 == 1:
    num = arr[n // 2]
else:
    num = (arr[n // 2] + arr[n // 2 - 1]) / 2
    
ans = 0

for j in range(n):
    ans += abs(arr[j-1] - num)
    
print(int(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:

def calc(A, b):
    retval = 0
    for a in A:
        retval += abs(a - b)
    return retval


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

    print(calc(A, sorted(A)[(N)//2]))

#    left = min(A)
#    right = max(A)
#
#    while left < right:
#        c1 = (left + left + right) // 3       # floor
#        c2 = -(-(left + right + right) // 3)  # ceil
#        if calc(A, c1) <= calc(A, c2):
#            right = c2 - 1
#        else:
#            left = c1 + 1
#    print(calc(A, left))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

X = [a-(i+1) for i, a in enumerate(A)]
X.sort()
b = X[(N)//2]
print(sum([abs(x - b) for x in X]))

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]
xs = sorted([A[_] - (_ + 1) for _ in range(N)])
print(sum([abs(_ - xs[N // 2]) for _ in xs]))

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

if n % 2 == 1:
    median = a[n // 2]
else:
    median = (a[n//2 - 1] + a[n//2]) // 2

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

print(ans)

Submission status: Accepted

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


def main():
    from statistics import median

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

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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
a = list(li())

amini = [ai-(i+1) for i,ai in enumerate(a)]
amini.sort()
b = amini[n//2]

print(sum([abs(ai-(b+i+1)) for i, ai in enumerate(a)]))

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

B1=[abs(B[i]-B[N//2]) for i in range(N)]
B2=[abs(B[i]-B[N//2-1]) for i in range(N)]

print(min(sum(B1),sum(B2)))

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=[int(i)-p for p,i in enumerate(input().split())]
a.sort()
ans=0
for i in a:
    ans+=abs(i-a[n//2])
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i)-p-1 for p,i in enumerate(input().split())]
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=[int(i)-p for p,i in enumerate(input().split())]
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()))
a2 = []
mi = 0
for i in range(n):
    a2.append(a[i]-i-1)
a3 = sorted(a2)
if n % 2 == 0:
    b = (a3[n//2-1]+a3[n//2])//2
else:
    b = a3[n//2]
s = 0
for i in a3:
    s += abs(i-b)
print(s)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
 
lst = sorted(a - i - 1 for i, a in enumerate(A)) 

c = lst[len(lst)//2]
ret = 0
for x in lst:
    ret += abs(x - c) 
print(ret)

Submission status: Accepted

Solution code:
def 解():
    iN = int(input())
    #aA = map(int,input().split())
    aA = sorted(map(lambda x,y:x-y,map(int,input().split()),range(1,iN+1)))
    iL = len(aA)
    if iL % 2 :
        iMed = aA[(iL-1)//2]
    else:
        iMed = aA[iL//2]
    print(sum(abs(a-iMed) for a in aA))

解()

Submission status: Accepted

Solution code:
def 解():
    iN = int(input())
    aA = map(int,input().split())
    aA = sorted(map(lambda x,y:x-y,aA,range(1,iN+1)))
    iL = len(aA)
    if iL % 2 :
        iMed = aA[(iL-1)//2]
    else:
        iMed = aA[iL//2]
    iMean = sum(aA) // 2
    iBlim= min(iMed,iMean)
    iUlim= min(iMed,iMean+1)

    print(min(sum(abs(a-i) for a in aA) for i in [iMed,iMean,iMean+1]))

解()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A = [A[_] - (_ + 1) for _ in range(N)]
AA = sorted(A)
ans = 0
ans1 = 0
center = N // 2
num = AA[center]

if N % 2 != 0:
    for i in range(N):
        ans += abs(AA[i] - num)
    print(ans)
else:
    center = len(AA) // 2
    for i in range(N):
        ans += abs(AA[i]- num)
        ans1 += abs(AA[i]-(AA[center-1]))
    print(min(ans, ans1))

Submission status: Accepted

Solution code:
import numpy as np

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

b = int(np.median(a2))
res = sum(abs(a2-b))

print(res)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#数列数を入力
n = int(input())
#数列を入力
a = list(map(int, input().split()))

#a_i - iをソートした数列を新たな数列とする
a = sorted([a[i] - i for i in range(len(a))])

#aの中央値を計算
m = n // 2
b = a[m] if n % 2 == 1 else (a[m -1] + a[m]) / 2

#出力
a = [abs(val - b) for val in a]
print(int(sum(a)))

Submission status: Accepted

Solution code:
import statistics

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

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

x.sort()

y1 = []
y2 = []
c = 0

if n % 2 == 0:
    #statistics.median()
    for i in range(n):
        if i <= int(n / 2) - 1:
            y1.append(x[i])
        else:
            y2.append(x[i])

    sumy1 = sum(y1)
    sumy2 = sum(y2)
    sumar = sumy2 - sumy1
    print(sumar)

w = []
z1 = []
z2 = []
d = 0

if n % 2 != 0:
    #med = x[int((n + 1) / 2)]
    #statistics.median()
    for h in range(1, n + 1):#中央値を排除
        if h != (n + 1) / 2:
            w.append(x[h - 1])
    for i in range(n - 1):#中央値の分をひく
        if i <= int((n - 1) / 2) - 1:#長さをリストのインデックス番号に変換するために１をひく
            z1.append(w[i])
        else:
            z2.append(w[i])
    sumz1 = sum(z1)
    sumz2 = sum(z2)
    sumar = sumz2 - sumz1
    print(sumar)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a_list = map(lambda x: int(x), input().split(' '))
    b_list = [x - i for i, x in zip(range(1, n+1), a_list)]
    b_list.sort()
    median = 0
    if n % 2 == 0:
        median = (b_list[n//2-1] + b_list[n//2]) / 2
    else:
        median = b_list[n//2]
    result = int(sum([abs(x - median) for x in b_list]))
    print(result)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

a.sort()
v = 0
if len(a) % 2 == 0:
    v1 = a[len(a)//2]
    v2 = a[len(a)//2 - 1]
    if abs(v1 + v2) == abs(v1) + abs(v2):
        v = min(v1, v2)
    else:
        v = abs(a[len(a)//2]) - abs(a[len(a)//2 - 1])
else:
    v = a[len(a)//2]
ans = 0
for i in a:
    ans += abs(i - v)
print(ans)

Submission status: Accepted

Solution code:
from statistics import median 
n = int(input())
a = list(map(int,input().split()))
ls = []
for i in range(n):
    ls.append(a[i] - i - 1)
b = median(ls)
if b % 1 == 0:
    ans = 0
    b = int(b)
    for i in range(n):
        ans += abs(a[i] - (b + i + 1))
    print(ans)
else:
    bigans = smallans = 0
    for i in range(n):
        bigans += abs(a[i] - (int(b) + i + 2))
        smallans += abs(a[i] - (int(b) + i + 1))
    print(min(bigans,smallans))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
a = np.array(list(map(int, input().split())), dtype=int)
b = a - np.arange(1, N + 1)
b.sort()
if N % 2 == 0:
    bb = (b[N // 2 - 1] + b[N // 2]) // 2
else:
    bb = b[N // 2]
print(np.sum(np.abs(b - bb)))

Submission status: Accepted

Solution code:
# Linear Approximation
from statistics import median
n = int(input())
a = list(map(int, input().split()))
b = []
_sum = 0
for i in range(n):
    b.append(a[i] - i - 1)
med = median(b)
for i in range(n):
    _sum += abs(b[i] - med)
print(int(_sum))

Submission status: Accepted

Solution code:
from statistics import median
n = int(input())
nums = list(map(int, input().split()))
bs = nums.copy()
tmp = 0

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


med = median(bs)

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

print(int(ans))

Submission status: Accepted

Solution code:
n=int(input())                    
a=list(map(int,input().split()))  
c=[]                              
ans=0                             
for i in range(n):                
    c.append(a[i]-(i+1))          
c.sort()                          
if n%2==1:                        
    b=c[(n-1)//2]                 
    for i in range(n):            
        ans+=abs(c[i]-b)          
    print(ans)                    
else:                             
    p=c[n//2]                     
    q=c[n//2+1]                   
    P=0                           
    Q=0                           
    for i in range(n):            
        P+=abs(c[i]-p)            
        Q+=abs(c[i]-q)            
    print(min(P,Q))

Submission status: Accepted

Solution code:
from statistics import median
n = int(input())
nums = list(map(int,input().split()))
bs = nums[:]
tmp =0

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

med = median(bs)

for i in range(n):
  tmp += abs(nums[i]-(med+(i+1)))

print(int(tmp))

Submission status: Accepted

Solution code:
from collections import Counter

def median_sum(N, A):
    median = -1
    if N%2 == 0:
        median = (A[N//2] + A[N//2 - 1]) // 2
    else:
        median = A[N//2]
    sum = 0
    for a in A:
        sum += abs(a - median)
    print(sum)
def main():
    N = int(input())
    A = [j - (i+1) for i , j in enumerate(map(int, input().split()))]
    A.sort()
    median_sum(N, A)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

def sunuke(An,b):
    ret = 0
    for i,Ai in enumerate(An):
        ret += abs(Ai - (b + i + 1))

    return ret

sAn = []
for i,Ai in enumerate(An):
     sAn.append(Ai - (i+1))

sAn.sort()

if N % 2 == 0:
    #偶数の場合
    center_idx1 = N // 2 - 1
    b1 = sAn[center_idx1]
    center_idx2 = center_idx1 + 1
    b2 = sAn[center_idx2]
    # print(b1,b2)
    print(min([sunuke(An,b1),sunuke(An,b2)]))
else:
    #奇数の場合
    center_idx = (N+1) // 2 - 1
    b = sAn[center_idx]
    # print(b)
    print(sunuke(An,b))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
  a[i] -= i
a.sort()
if n%2 == 1:
  m = a[n//2]
else:
  m = (a[n//2]+a[n//2-1])//2

s = 0
for x in a:
  s += abs(x-m)
print(s)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
u=[]
for i in range(N):
    u.append(A[i]-i)
a=sorted(u)
if len(a)%2==0:
    p=a[len(a)//2]
else:
    p=a[len(a)//2]
ans=0
for j in range(N):
    ans+=abs(a[j]-p)
print(ans)

Submission status: Accepted

Solution code:
def f(x,i,n):
    sadness = 0
    for j in range(n):
        sadness += abs(x[j]-i)
    return(sadness)
N = int(input())
H = [int(i) for i in input().split()]
for i in range(N):
    H[i] -= i+1
H = sorted(H)
k = N // 2
if N == 1 :
    print(0)
else:
    print(f(H,H[k],N))

Submission status: Accepted

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

Submission status: Accepted

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


def main():
    from statistics import median

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

    for index, ai in enumerate(a, 1):
        mod_a.append(ai - index)

    b = int(median(mod_a))

    for mod_ai in mod_a:
        ans += abs(mod_ai - b)

    print(ans)


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

X = [abs(a - A[N//2]) for a in A]
print(sum(X))

Submission status: Accepted

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

Submission status: Accepted

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

cnt_plus = 0
cnt_minus = 0
cnt_zero = 0
for i in range(n):
    a[i] -= i + 1
    if a[i] == 0:
        cnt_zero += 1
    elif a[i] > 0:
        cnt_plus += 1
    else:
        cnt_minus += 1

ans = 0
if cnt_plus <= (cnt_minus + cnt_zero) and cnt_minus <= (cnt_plus + cnt_zero):
    for v in a:
        ans += abs(v)
elif cnt_plus > (cnt_minus + cnt_zero):
    c = [v for v in a if v > 0]
    c.sort()
    b = c[(cnt_plus - (cnt_minus + cnt_zero) - 1) // 2]
    for v in a:
        ans += abs(v - b)
else:
    c = [v for v in a if v < 0]
    c.sort(reverse=True)
    b = c[(cnt_minus - (cnt_plus + cnt_zero) - 1) // 2]
    for v in a:
        ans += abs(v - b)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

def abs_quiz(A):
    B = [a-i-1 for i, a in enumerate(A)]
    B.sort()
    ans = sum([abs(b - B[N//2]) for b in B])
    return ans

ans = abs_quiz(A)
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()
if n%2==1:x=b[int((n+1)/2)-1]
else:x=int((b[int(n/2)]+b[int(n/2)-1])/2)
c=0
for j in range(n):
  c+=abs(x-b[j])
print(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()
if N % 2 == 0:
    M = A[N//2]
else:
    M = A[(N-1)//2]
for i in range(N):
    A[i] = abs(A[i] - M)
print(sum(A))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
sum_=0
dic = {}
for i,x in enumerate(A):
    if dic.get(x-(i+1),0) == 0:
        dic[x-(i+1)] = 1
    else:
        dic[x-(i+1)] += 1
tup = sorted(dic.items(),key=lambda x:x[0])
num = 0
mid = 0

for i in range(len(tup)):
    num += tup[i][1]
    if num >= (N+1)//2:
        mid = tup[i][0]
        break

ans = 0
for i,x in enumerate(A):
    ans+=abs(x-mid-(i+1))
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()

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
C - Linear Approximation
https://beta.atcoder.jp/contests/abc102/tasks/arc100_a
TLE
"""
import sys
from sys import stdin
input = stdin.readline

from functools import lru_cache
def _solve(arr):
    @lru_cache(maxsize=None)
    def calc_score(n):
        return sum([abs(a-(n+i)) for i, a in enumerate(arr, start=1)])

    ub = max(arr)
    lb = -max(arr)

    while True:
        mid1 = (lb*2 + ub) // 3
        mid2 = (lb + ub*2) // 3
        mid1_score = calc_score(mid1)
        mid2_score = calc_score(mid2)

        if mid2_score > mid1_score:
            ub = mid2
        else:
            lb = mid1
        if abs(ub - lb) <= 4:
            break

    ans = float('inf')
    for b in range(lb, ub+1):
        t = calc_score(b)
        ans = min(ans, t)
    return ans


from statistics import median

def solve(arr):
    def calc_score(n):
        return sum([abs(a-(n+i)) for i, a in enumerate(arr, start=1)])

    array_b = [a-i for i, a in enumerate(arr, start=1)]
    m = median(array_b)
    ans = float('inf')
    for i in range(int(m)-1, int(m)+2):
        ans = min(ans, calc_score(i))
    return ans



def main(args):
    N = int(input())
    arr = [int(a) for a in input().split()]
    ans = solve(arr)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

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

def sadness(x,y):
  s = 0
  for i in range(len(y)):
    s += abs(y[i]-x)
  return s

if n%2 == 0:
  print(sadness(b[int(n/2)],b))
else:
  print(sadness(b[int((n-1)/2)],b))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [A[i] - 1 - i for i in range(N)]
B.sort()
if N % 2 == 0:
    med = [B[int(N / 2) - 1], int((B[int(N / 2) - 1] + B[int(N / 2)]) / 2), B[int(N / 2)]]
else:
    med = [B[int((N + 1) / 2) - 1]]
ans = 10 ** 100
for b in med:
    S = 0
    for i in range(N):
        S += abs(B[i] - b)
    ans = min(ans, S)
print(ans)

Submission status: Accepted

Solution code:
import statistics

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

b = int(statistics.median(A))
print(sum([abs(n - b) for n in A]))

Submission status: Accepted

Solution code:
# encoding: utf-8
N = int(input())
A = list(map(int, input().split()))

Amb = sorted([Ai - (i + 1) for i, Ai in enumerate(A)])
b = Amb[N // 2]

ans = 0
for i, Ambi in enumerate(Amb):
    if i <= N // 2: ans += b - Ambi
    else: ans += Ambi - b

print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

INF = float('inf')


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


n = int(input())
A = inpl()
tmp = [i + 1 for i in range(n)]

B = [A[i] - tmp[i] for i in range(n)]
B.sort()
b = B[n // 2]

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

print(ans)

Submission status: Accepted

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

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

nums.sort()
        
if (n-1) % 2 != 0:
    m = n//2 - 1
else:
    m = (n-1)//2
    
a = sum(nums[m+1:]) - (n-m-1)*nums[m]
b = - sum(nums[0:m+1]) + (m+1)*nums[m]

print(a+b)

Submission status: Accepted

Solution code:
n = int(input())
a = sorted([ int(v)-i-1 for i,v in enumerate(input().split()) ])
ans = 0
# 中央値で反転
if n % 2 == 0:
    print(sum(a[n//2:]) - sum(a[:n//2]))
else:
    print(sum(a[(n+1)//2:]) - sum(a[:(n-1)//2]))

Submission status: Accepted

Solution code:
n = int(raw_input())
a = map(int,raw_input().split())
b = []
for i in range(n):
  b.append(a[i]-i-1)
b.sort()
if len(b)%2 == 0:
  c = b[len(b)/2]
else:
  c = b[(len(b)-1)/2]
d = 0
for i in range(n):
  d += abs(b[i]-c)
print d

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 range(n):
    ans += abs(a[i]-med)

print(int(ans))

Submission status: Accepted

Solution code:
# coding: utf-8
from math import floor

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

for i in range(n):
    A[i] = (A[i]-1-i)
b = sorted(A)[floor(len(A)/2)]

sum = 0

for a in A:
    sum += abs(a-b)
print(sum)

Submission status: Accepted

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

a.sort()
s=0
b=[-10000000]
for i in range(1,n+1):
  s+=a[i]
  b.append(s)

ave=n//2

s1=0
s2=0
s3=0
for i in range(1,n+1):
  s3+=abs(a[i]-a[(ave-1)])
  s1+=abs(a[i]-a[ave])
  s2+=abs(a[i]-a[(ave+1)])
print(min(s1,s2,s3))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from statistics import median

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

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

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

    
SUM = 0
for i in range(N):
    SUM += abs(C[i] -B)
print(int(SUM))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

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

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

A.sort()
mid = A[n / 2]
print sum(abs(num - mid) for num in A)

Submission status: Accepted

Solution code:
def solution(a):
    a = [a[i] - i - 1 for i in xrange(len(a))]
    a = sorted(a)
    b = a[len(a) >> 1]
    return sum([abs(i - b) for i in a])

def main():
    n = int(raw_input().strip())
    a = [int(i) for i in raw_input().strip().split()]
    print solution(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] -= i
    
a.sort()
n2 = n//2
b = a[n2]
ans = sum([abs(a[i]-b) for i in range(n)])

print(ans)

Submission status: Accepted

Solution code:
import statistics as stc

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

#a[i]-(b+1) = a[i]-i-b
a_ = [a[i]-(i+1) for i in range(len(a))]

b=stc.median(a_)

def sad(a,b):
    b=int(b)
    score=0
    for i in range(len(a)):
        score+= abs(a[i]-b)
    return score

res = sad(a_,b)
print(res)

Submission status: Accepted

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

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:
    print(sum(a[int(n / 2):]) - sum(a[:int(n / 2)]))
else:
    print(sum(a[int((n + 1) / 2):]) - sum(a[:int((n - 1) / 2)]))

Submission status: Accepted

Solution code:
from math import floor, ceil
from statistics import mean, median

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

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

med = median(A)
x = int(floor(med))
y = int(ceil(med))
xans = 0
yans = 0

for i in range(len(A)):
  xans += abs(A[i]-x)
  yans += abs(A[i]-y)

print(xans)

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の最小から最大まで
x=0
z=n-1
y=(x+z)//2
while z!=x:
    s1=0
    s2=0
    for k in range(n):
        s1+=abs(a[k]-a[y])
    for k in range(n):
        s2+=abs(a[k]-a[y+1])
    if s1<s2 :
        z=y
        y=(x+z)//2
    elif s1==s2:
        x=y
        z=y
    else:
        x=y+1
        y=(x+z)//2
#x=y=zとなっている
s=0
for k in range(n):
    s+=abs(a[k]-a[y])

print(s)

Submission status: Accepted

Solution code:
N = int(input())
an = [int(i) for i in input().split()]
for i in range(N): an[i] -= i
b = sorted(an)[N>>1]
print(sum(map(abs, [i-b for i in an])))