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:
# ABC102 C-Linear Approximation

N = int(input())
A = list(int(s) for s in input().split())
ami = [A[i] - i - 1 for i in range(N)]
ami.sort()
b = ami[N // 2]
print(sum(abs(v - b) for v in ami))

Submission status: Accepted

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

A.sort()

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

ans = 0
for a in A:
    ans += abs(a-T)
print(ans)

Submission status: Accepted

Solution code:
from math import floor, ceil
N = int(input())
A = []
for i,a in enumerate(input().split()):
  A.append(int(a)-(i+1))
A.sort()
if N % 2 :
    print(-1*sum(A[:N//2]) + sum(A[N//2+1:]))
else:
    print(-1*sum(A[:N//2]) + sum(A[N//2:]))

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()
a=N//2

def sad(A,a):
    sadness=0
    for i in range(N):
        sadness+=abs(A[i]-A[a])
    return sadness

if N%2==0:
    ans=min(sad(A,a),sad(A,a+1))
else:
    ans=sad(A,a)
print(ans)

Submission status: Accepted

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

total = 0
for i in range( n):
    total += (dat[i] - (i+1))
    dat_d.append(dat[i] - (i+1))

#print(dat)
#print(dat_d)
#print(total)
#f = (total // n)
#print(f)

dat_d.sort()
#print(dat_d)
f = dat_d[n//2]

total = 0
for i in range( n):
    total += abs(dat_d[i] - f)

print(total)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# editorialを参考にした

N = int(input())
A = [int(x) for x in input().split()]
A_prime = [0]*N
for i in range(N):
    A_prime[i] = A[i] - i-1
A_prime = sorted(A_prime)
center = A_prime[N//2]

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

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
for i in range(N):
    A[i] -= (i+1)
A.sort()
if N%2 == 0:
    b = A[int(N*0.5)]
else:
    b = A[int((N-1)*0.5)]
ans = 0
for j in range(N):
    ans += abs(A[j]-b)
print(int(ans))

Submission status: Accepted

Solution code:
N = int(input())
A = map(int, input().split())
modified_A = []
for i, a in enumerate(A):
    modified_A.append(a - i - 1)

modified_A = sorted(modified_A)

min_sorrow = 1000000000000000
passed_A = 0
sum_A = sum(modified_A)
for i, a in enumerate(modified_A):
    passed_A += a
    sorrow = (2 * (i+1) - N) * a + sum_A - 2 * passed_A
    # print(i, a, sorrow)
    if sorrow < min_sorrow:
        min_sorrow = sorrow
print(min_sorrow)

Submission status: Accepted

Solution code:

###template###
import sys
def input(): return sys.stdin.readline().rstrip()
import heapq
INF = float("inf")
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

def custom_round(number, ndigits=0):
  if type(number) == int: #整数ならそのまま返す
    return number
  d_point = len(str(number).split('.')[1]) #小数点以下が何桁あるか定義
  if ndigits >= d_point:#求める小数点以下の値が引数より大きい場合はそのまま返す
    return number
  c = (10 ** d_point) * 2
    #小数点以下の桁数分元の数に0を足して整数にして2倍するための値(0.01ならcは200)
  return round((number * c + 1) / c, ndigits)
    #元の数に0を足して整数にして2倍して1を足して2で割る。元の数が0.01なら0.015にしてroundを行う

N = ii()
As = list(mi())

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

if N % 2 == 1:
  median = As[(N-1)//2]
else:
  median = (As[(N-1)//2] + As[(N-1)//2 + 1]) // 2

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

Submission status: Accepted

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

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

arr = sorted(arr)
diff = 0
for j in range(N//2):
    diff+=abs(arr[N-j-1]-arr[j])
    
print(diff)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())

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

if N==1:
    print(0)
    exit()
elif N==2:
    B=[A[0]-1,A[1]-2]
    b=sum(B)//2
else:
    B=[]
    for i in range(N):
        B.append(A[i]-(1+i))
    #print(B)
    B.sort()
    #print(B)
    b=B[N//2]

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

Submission status: Accepted

Solution code:
from operator import sub

N = int(input())
a = tuple(map(int, input().split()))

b = list(map(sub, a, range(1, N + 1)))
b.sort()
mb = b[N // 2]
print(sum(map(lambda x: abs(x - mb), 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 = list(sorted(b))
d = b[n//2]
b = [abs(b[i]-d) for i in range(n)]
print(sum(b))

Submission status: Accepted

Solution code:
import statistics
N = int(input())
a = [int(i) for i in input().split()]
ans = 0

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

b = statistics.median(a)
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()))
b = [0] * n
ans = 0

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

sort_b = sorted(b)
num = sort_b[n // 2]

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

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:
    b=B[N//2]
else:
    b=(B[N//2]+B[N//2-1])//2
ans=0
for k in B:
    ans+=abs(k-b)
print(ans)

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)]
#print(A)
A.sort()
i = n/2
a = A[math.floor(i)]
b = A[math.ceil(i)] if i>1 else a
ans,ans1=0,0
for i in A:
    ans += abs(i-a)
    ans1 += abs(i-b)
print(min(ans,ans1))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= i
a.sort()
b = a[n // 2]
answer = 0
for a_i in a:
    answer += abs(a_i - b)
print(answer)

Submission status: Accepted

Solution code:
# ABC102C - Linear Approximation (ARC100C)
def main():
    n = int(input())
    A = tuple(map(int, input().rstrip().split()))
    A = sorted(j - i for i, j in enumerate(A, start=1))
    b = A[n // 2]
    ans = sum(abs(a - b) for a in A)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC102C - Linear Approximation (ARC100C)
from statistics import median


def main():
    n = int(input())
    A = tuple(map(int, input().rstrip().split()))
    A = tuple(j - i for i, j in enumerate(A, start=1))
    b = median(A)
    ans = sum(abs(a - b) for a in A)
    print(int(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
import statistics as stats

n=int(input())
x=list(map(int,input().split()))
x1=list(range(1,n+1))
x2=list(map(lambda a,b: a-b, x,x1))
b=round(stats.median(x2))
x3=[b]*n
x4=list(map(lambda a,b: a-b, x2,x3))
x5=np.abs(x4)
res=sum(x5)
print(res)

Submission status: Accepted

Solution code:
n = int(input())
lst_a = list(map(int, input().split()))
lst_x = [a - i - 1 for i, a in enumerate(lst_a)]
lst_x.sort()
b = lst_x[n // 2]
ans = sum(abs(x - b) for x in lst_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)
c = sorted(B)
ans = float('inf')
l = 0
r = sum(c)
for i in range(N):
    b = c[i]
    l += c[i]
    r -= c[i]
    tmp = b*((i+1) - (N - i - 1)) + r - l
    if tmp < ans:
        ans = tmp
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
from statistics import median
N = int(input())
a_lis = list(map(int, input().split()))

new_lis = [item - i - 1 for i, item in enumerate(a_lis)]

mode = median(new_lis)

count = 0
for i in range(N):
    count += abs(a_lis[i] - mode - i - 1)
    
print(int(count))

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
k = []
for i in range(len(l)):
    k.append(l[i] - i - 1)
k.sort()
if len(k) % 2 == 0:
    middle = len(k) // 2
    median = (k[middle - 1] + k[middle]) / 2
else:
    middle = len(k) // 2
    median = (k[middle])
ans = 0
for j in range(n):
    ans += abs(l[j] - (median + j + 1))
print(int(ans))

Submission status: Accepted

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

def median(seq):
    s = sorted(seq)
    if len(s) % 2 == 0:          # 要素が偶数個なら2つの平均
        return (s[len(s) // 2] + s[(len(s) // 2) - 1]) / 2
    else:
        return s[len(s) // 2]    # 要素が奇数個なら中央の値

b=median(B)

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

print(int(ans))

Submission status: Accepted

Solution code:
import numpy as np

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

b = [a[i] - i for i in range(N)]
median = np.median(b)

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

print(ans)

Submission status: Accepted

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

def median(seq):
    s = sorted(seq)
    if len(s) % 2 == 0:          # 要素が偶数個なら2つの平均
        return (s[len(s) // 2] + s[(len(s) // 2) - 1]) / 2
    else:
        return s[len(s) // 2]    # 要素が奇数個なら中央の値

b=median(B)

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

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

#print(b)

def solve(b):
	result = 0
	for i, a in enumerate(A):
		result += abs(a - (b + i))
	return result

if 0 == N % 2:
	b1, b2 = b[N // 2 - 1], b[N // 2]
	print(min(solve(b1), solve(b2)))
else:
	b1 = b[N // 2]
	print(solve(b1))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

N = int(input())

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

ans = 0


for i in range(N):

    A[i] -= i + 1

A.sort()



if N % 2 != 0:

    kz = A[ N // 2 ]

elif A[N // 2] - A[N // 2 - 1] > 1:
    kz = A[ N // 2 ] - 1

else:
    kz = A[ N // 2 ]


for i in A:

    i -= kz

    if i < 0:
        ans -= i
    else:
        ans += i

print (ans)

Submission status: Accepted

Solution code:
n = int(input())
a_list = [int(s) - i for i, s in enumerate(input().split())]

a_list.sort()
center = a_list[len(a_list) // 2]

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

Submission status: Accepted

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

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

chuoh=0
count=0
count2=0
if n%2==1:
    chuoh=b[int(n/2)]
    for i in range(n):
        count+=abs(a[i]-chuoh-i-1)
else:
    chuoh=b[int(n/2)]
    for i in range(n):
        count+=abs(a[i]-chuoh-i-1)
    chuoh=b[int(n/2)-1]
    for i in range(n):
        count2+=abs(a[i]-chuoh-i-1)
    count=min(count, count2)

print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

input = sys.stdin.readline

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

    A2 = []
    for i, a in enumerate(A):
        A2.append(a - (i+1))
    A2.sort()
    b = 0
    if N%2 == 1:
        b = A2[int(N/2)]
    else:
        b = int((A2[int(N/2)-1] + A2[int(N/2)]) / 2)
    
    s = 0
    for a in A2:
        s += abs(a - b)
    print(s)

main()

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.array(input().split(), dtype = np.int64)

A -= np.arange(N)
A.sort()

x = A[N//2]
answer = np.abs(A - x).sum()
print(answer)

Submission status: Accepted

Solution code:
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import string
import sys

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

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

A = np.array(A, dtype=int)
D = A - np.arange(N)
print(int(np.abs(D - np.median(D)).sum()))

Submission status: Accepted

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

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()
med = a[len(a) // 2]

n = 0

for ai in a:
  n += abs(ai - med)

print(n)

Submission status: Accepted

Solution code:
from statistics import median
 
n = int(input())
xs = [int(x) for x in input().split()]

ys = [x-i for i, x in enumerate(xs,1)]
m = int(median(ys))

print(sum(abs(y-m) for y in ys))

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)
indx = int(len(A) / 2)

b = sum([abs(a - A[indx]) for a in A])

ans = [b]

if N > 1:
    b1 = sum([abs(a - A[indx-1]) for a in A])
    ans.append(b1)

if N > 2:
    b2 = sum([abs(a - A[indx+1]) for a in A])
    ans.append(b2)

print(min(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()
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 = [int(x)-i-1 for i,x in enumerate(input().split())]
a.sort()
if len(a)%2==1:
    md = a[len(a)//2]
    ans = 0
    for i in a:
        ans += abs(i-md)
    print(ans)
else:
    md1 = a[len(a)//2]
    md2 = a[len(a)//2-1]
    ans1 = 0
    ans2 = 0
    for i in a:
        ans1 += abs(i-md1)
        ans2 += abs(i-md2)
    print(min(ans1,ans2))

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

c_s = [a_s[i] - (i+1) for i in range(0, n)]
#print(c_s)

c_s.sort()
#print(c_s)

med = c_s[n // 2]
d_s = [abs(c - med) for c in c_s]
#print(d_s)
ans = sum(d_s)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [0] * n

s1 = 0
s2 = 0

for i in range(n):
    b[i] = a[i] - i
b.sort()

b1 = b[n//2]
b2 = b[n//2-1]

for i in range(n):
    s1 += abs(a[i] - b1 - i)

for i in range(n):
    s2 += abs(a[i] - b2 - i)

print(min(s1, s2))

Submission status: Accepted

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

ans = [a-i-1 for i,a in enumerate(A) ]
sorted_ans = sorted(ans)

def final_ans(ans_list , b):
    count = [abs(a-i-1-b) for i,a in enumerate(A) ]
    return(sum(count))

    

if len(sorted_ans) %2 == 1:
    mediam_place = len(sorted_ans)//2
    b = sorted_ans[mediam_place]
    print(final_ans(A , b))
else:
    mediam_place = len(sorted_ans)//2
    b = sorted_ans[mediam_place]
    val1 = final_ans(A , b)

    mediam_place = len(sorted_ans)//2 + 1
    b = sorted_ans[mediam_place]
    val2 = final_ans(A , b)
    print(min(val1 , val2))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x)-i for x,i in zip(input().split(),range(1,N+1))]
from math import ceil,floor
    
A.sort()


if N%2 == 0:
    b = round((A[floor(N/2)]+A[ceil(N/2)])/2)
else:
    b = A[floor(N/2)]
ans = 0
for a in A:
    ans += abs(a-b)
print(ans)

Submission status: Accepted

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

B.sort()
#print(B)
#print(B[len(B)//2])
if len(B) % 2 == 1:
  pt = B[len(B)//2]
  val = sum([abs(pt - i) for i in B])
else:
  ptA = B[len(B)//2]
  valA = sum([abs(ptA - i) for i in B])
  ptB = B[len(B)//2 + 1]
  valB = sum([abs(ptB - i) for i in B])
  if valA < valB:
    val = valA
  else:
    val = valB
print(val)

Submission status: Accepted

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

b = Alist[N//2]

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

Submission status: Accepted

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

Submission status: Accepted

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

b = sorted(B)[(N-1)//2]

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

Submission status: Accepted

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

b = sorted(B)[(N-1)//2]

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

print(ans)

Submission status: Accepted

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

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

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


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

print(ans)

Submission status: Accepted

Solution code:
#import numpy
n=int(input())
da=list(map(int,input().split()))
for i in range(n):
    da[i]-=i+1
da=sorted(da)
b=da[n//2]
ans=0
for i in range(n):
    ans+=abs(b-da[i])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
memo={}
def calc(A, b):
    score = memo.get(b, None)
    if not score is None:
        return score
    score = sum(abs(a-b) for a in A)
    memo[b] = score
    return score

c = 0
def findmin(A, l, u):
    global c
    c+=1
    d = (u-l)//3
    if d == 0:
        return min(calc(A, i) for i in range(l, u+1))
    left, right = l + d, u - d
    sl = calc(A, left) 
    sr = calc(A, right) 
    if sl > sr:
        return findmin(A, left, u)
    else:
        return findmin(A, l, right)

def solve(A):
    B= [0] * len(A)
    l = A[0]
    u = A[0]
    for i, a in enumerate(A):
        b = a-(i+1)
        l = min(l, b)
        u = max(u, b)
        B[i] = b
    #A = [a-(i+1) for i, a in enumerate(A)]
    return findmin(B, l, u)

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

#abs(A1-(b+1)) + abs(Ai-(b-i)) + abs(AN-(b-N))


# b1 = A[0]    ならば (A[i]-b1) >= 0
# b2 = A[0] -1 ならば (A[i]-b2) > (A[i]-b1) >= 0 なので、スコアは大きくなる

# b = A[-1] ならば (A[i]-b) <= 0
print(solve(A))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
import statistics
import math

def main():
	N = int(input())
	A = list(map(int, input().split(" ")))
	
	A_tmp = []
	for i, val in enumerate(A):
		A_tmp.append(val - (i+1))
		
	hey = np.median(A_tmp)
	ans = 0
	for i, val in enumerate(A):
		ans += abs(val-(hey+(i+1)))
		
	#print(A_tmp)
	print(int(ans))
	
if __name__ == "__main__":
	main()

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()
mid = A[N // 2]
res1 = 0
for a in A:
    res1 += abs(a - mid)

mid += 1
res2 = 0
for a in A:
    res2 += abs(a - mid)


print(min(res1, res2))

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N= int(input())
    A_list = list(map(int, input().split()))

    B_list = []

    for i in range(len(A_list)):
        B_list.append(A_list[i]-(i+1))

    B_list = sorted(B_list)

    if len(B_list)%2 == 1:
        b = B_list[(len(B_list)-1)//2]
    else:
        b = B_list[len(B_list)//2-1]

    answer = 0
    for Bi in B_list:
        answer += abs(Bi-b)
    print(answer)

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:
    B=A.copy()
    C=A.copy()
    for i in range(n):
        s=A[n//2]
        B[i]=abs(B[i]-s)
    a=sum(B)
    for i in range(n):
        t=A[n//2-1]
        C[i]=abs(C[i]-t)
    b=sum(C)

    print(min(a,b))
else:
    B=A.copy()
    for i in range(n):
        B[i]=abs(B[i]-A[n//2])
    print(sum(B))

Submission status: Accepted

Solution code:
n = int(input())

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

diff = []
for i, x in enumerate(arr, 1):
    diff.append(x - i)

diff.sort()
b = (diff[(n-1)//2] + diff[n//2]) // 2

abs_diff = 0
for i, x in enumerate(arr, 1):
    abs_diff += abs(x - (i + b))
print(abs_diff)

Submission status: Accepted

Solution code:
import numpy as np

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

ans = 0
b = np.median(A)
for i in A:
    ans += abs(i-b)

print(int(ans))

Submission status: Accepted

Solution code:
import math

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

Submission status: Accepted

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

N = int(input())
d = 0
A = [int(i) for i in input().split()]
B = []
for i in range(N):
    B.append(A[i] - (i+1))
b = sorted(B)[N//2]

f = [abs(i-b) for i in B]
print(sum(f))

Submission status: Accepted

Solution code:
n=int(input())
a=[x-i for i,x in enumerate(map(int,input().split()))]
a.sort()
S=s=0
a_l=len(a)
a_m=(a_l+1)//2
for j in range(a_l-a_m):
    S+=a[a_m]-a[j]
for j in range(a_m-1):
    S+=a[-j-1]-a[a_m]
print(S)

Submission status: Accepted

Solution code:
N = int(raw_input())
A = map(int, raw_input().split())
for i in range(0, N):
	A[i] -= i+1
A.sort()
m = 0
if N % 2 == 0:
	m = (A[N/2-1]+A[N/2])/2
else:
	m = A[N/2]
sum = 0
for i in range(0, N):
	sum += abs(A[i]-m)
print sum

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int,input().split()))
As1 = [a-(i+1) for i,a in enumerate(As)]
m = sorted(As1)[len(As)//2]

f = [abs(a-m) for a in As1]
print(sum(f))

Submission status: Accepted

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

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

A.sort()

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

Submission status: Accepted

Solution code:
N, *a = map(int, open(0).read().split())
x = [a[i] - i - 1 for i in range(N)]
x.sort()
print(sum([abs(v - x[N // 2]) for v in x]))

Submission status: Accepted

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

def F(b,A):
    L = [abs(a-(b+i+1)) for i,a in enumerate(A)]
    return sum(L)

def solve(N: int, A: "List[int]"):
    L = [ a-(i+1) for i,a in enumerate(A) ]
    medl = statistics.median_low(L)
    medh = statistics.median_high(L)

    print(min(F(medl,A),F(medh,A)))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import statistics

def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] -= i + 1

    data.sort()
    mean = statistics.median(data)
    mean = int(round(mean, 0))

    ans = 0

    for i in range(num):
        data[i] -= mean
        ans += abs(data[i])
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect as bi

N = int(input())
A = [int(t) for t in input().split()]

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

nega_cnt = bi.bisect_left(A, 0)
posi_cnt = N - bi.bisect_right(A, 0)
zero_cnt = N - nega_cnt - posi_cnt


def calc():
    if nega_cnt + zero_cnt >= posi_cnt and posi_cnt + zero_cnt >= nega_cnt:
        return sum([abs(t) for t in A])

    if posi_cnt > nega_cnt + zero_cnt:
        idx = (posi_cnt-(nega_cnt + zero_cnt)) // 2 + 1
        a = A[-posi_cnt:][idx-1]
        return sum([abs(t-a) for t in A])

    if posi_cnt + zero_cnt < nega_cnt:
        idx = (nega_cnt-(posi_cnt + zero_cnt))//2 + 1
        a = A[:nega_cnt][-idx]
        return sum([abs(t-a) for t in A])


print(calc())

Submission status: Accepted

Solution code:
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n = f()[0]
    a = f()

    a = [a[i]-(i+1) for i in range(n)]
    a = sorted(a)
    b = a[n//2]

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

solve()

Submission status: Accepted

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

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

if n == 1:
    print(0)
elif n % 2 == 0:
    l = n // 2
    s = 0
    for i in range(l):
        s += li[i]
    print(sum(li)- 2 * s)
else:
    l = (n - 1) // 2
    s = 0
    for i in range(l):
        s += li[i]
    print(sum(li) - 2 * s - li[l])

Submission status: Accepted

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

b = [a[i]-i for i in range(n)]
m = round(median(b))
ans = 0
for i in range(n):
    ans += abs(a[i] - (m+i))
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))
med = b[N // 2]
ans = 0
for e in b:
  ans += abs(e - med)
print(ans)

Submission status: Accepted

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n = readi()
p = readl()
for i in range(1, n + 1):
    p[i - 1] = p[i-1] - i
p.sort()
if n % 2 == 1:
    t = p[n // 2]
else:
    t = (p[n // 2] + p[n // 2 -1]) // 2
count = 0
for i in p:
    count += abs(i - t)
print(count)

Submission status: Accepted

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


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

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

Submission status: Accepted

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

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

A.sort()


def get_pity_sum(x):
    pity_sum = 0
    for l in A:
        if A[x] - l >= 0:
            pity_sum += A[x] - l
        else:
            pity_sum += l - A[x]
    return pity_sum


if N % 2 == 1:
    c = get_pity_sum(int((N - 1) / 2))
    if N == 1:
        print(c)
    else:
        print(min(c, get_pity_sum(int((N - 1) / 2 - 1)), c + (A[int((N - 1) / 2) + 1] - A[int((N - 1) / 2)]) * 2, c + (A[int((N - 1) / 2)] - A[int((N - 1) / 2 - 1)]) * 2))
else:
    d = get_pity_sum(int(N / 2))
    print(min(get_pity_sum(int(N / 2)), d + (A[int(N / 2) + 1] - A[int(N / 2)]) * 2))