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:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
B = [a-i-1 for i,a in enumerate(A)]
ctr = Counter(B)
st = sorted(list(ctr.items()))

left = l_sum = 0
ans = r_sum = sum([(k - st[0][0])*v for k,v in st[1:]])

for (k1,v1),(k2,v2) in zip(st,st[1:]):
    left += v1
    l_sum += left * (k2-k1)
    right = N-left
    r_sum -= right * (k2-k1)
    ans = min(ans, l_sum + r_sum)
print(ans)

Submission status: Accepted

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

#N = 1
#A = [10**9]*N

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

A_n.sort()

if N%2 == 0:
    cent_max = A_n[N//2]
    cent_min = A_n[N//2-1]
else:
    cent = A_n[N//2]
    
if N%2 == 0:    
    sadness1 = sum([abs(A_n[i]-cent_min) for i in range(N)])
    sadness2 = sum([abs(A_n[i]-cent_max) for i in range(N)])
    sadness = min(sadness1, sadness2)

else:
    sadness = sum([abs(A_n[i]-cent) for i in range(N)])

print(sadness)

Submission status: Accepted

Solution code:
import statistics

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

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

b = int(statistics.median(A))
print(sum(map(lambda x:abs(x-b), A)))

Submission status: Accepted

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

Submission status: Accepted

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

i = 1
A_2 = []
for a in A:
    A_2.append(a-i)
    i += 1

A_3 = sorted(A_2)

b = A_3[N//2]

i = 0
mini = 0
for a in A_3:
    mini += abs(A_3[i] - b)
    i += 1

print(mini)

Submission status: Accepted

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

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

print(sum(abs(x-y) for x,y in zip(A, A[::-1]))//2)

Submission status: Accepted

Solution code:
# https://beta.atcoder.jp/contests/abc102/tasks/arc100_a

from statistics import median

if __name__ == '__main__':
    # n = 7
    # a = [1, 1, 1, 1, 2, 3, 4]

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

    d = []

    for i, a_i in enumerate(a):
        diff = int(a_i) - (i + 1)
        d.append(diff)

    m = int(round(median(d)))

    ans = 0
    for d_i in d:
        ans += abs(d_i - m)
    print(ans)

Submission status: Accepted

Solution code:
from statistics import median

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


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

b=round(float(median(A)))





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

print(summ)

Submission status: Accepted

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

a = sorted(a)
mid = a[n // 2]
num = 0
for i in range(n):
    num += abs(a[i] - mid)

print(num)

Submission status: Accepted

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

print(m())

Submission status: Accepted

Solution code:
import statistics

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

tmp = [num - (i+1) for i, num in enumerate(A)]
med = int(statistics.median(tmp))
answer = sum([abs(num - med) for num in tmp])

print(answer)

Submission status: Accepted

Solution code:
import statistics


N   = int(input())
A   = list(map(int, input().split()))
A_b = [a - (idx + 1) for idx, a in enumerate(A)]
med = int(statistics.median(A_b))

print(int(sum([abs(x - med) for x in A_b])))

Submission status: Accepted

Solution code:
def med(data):
    N = len(data)
    data.sort()
    if N % 2 == 0:
        median1 = N/2
        median2 = N/2 + 1
        median1 = int(median1) - 1
        median2 = int(median2) - 1
        median = (data[median1] + data[median2]) / 2
        return median
    else:
        median = (N + 1) / 2
        median = int(median) - 1
        median = data[median]
        return median

import sys
N = int(input())
lists = [int(i) for i in input().split()]
sok = sys.maxsize
list2 = [x - j - 1 for j, x in enumerate(lists)]
b = med(list2)
kanashi = 0
for xx in list2:
    kanashi += abs(xx - b)
print(int(kanashi))

Submission status: Accepted

Solution code:
# coding: utf-8

def getBList(A):
    bList = []
    for i in range(1, len(A)+1):
        bList.append(A[i-1]-i)
    return bList

def getMedian(bList):
    tmp = sorted(bList)
    if len(bList) % 2 == 1:
        return tmp[len(bList)//2]
    else:
        return (tmp[len(bList)//2]+tmp[len(bList)//2-1])//2

def solve(A, b):
    ssum = 0
    for i in range(len(A)):
        ssum += abs(A[i] - (b+i+1))
    return ssum

if __name__ == "__main__":

    N = int(input())
    A = [int(x) for x in input().split()]
    print(solve(A, getMedian(getBList(A))))

Submission status: Accepted

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

#Biを作成
B = A.copy()
for i in range(N):
    B[i] = B[i] - (i+1)

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

tmp=0
for i in B:
    tmp += abs(i - chuo)
print(tmp)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

def calc(b, A):
    ans = 0
    for i, a in enumerate(A, start=1):
        ans += abs(a - (b + i))
    return ans

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

    ans = INF
    x = N // 2
    for i in range(max(0, x - 1), min(x + 1, N)):
        ans = min(ans, calc(B[i], A))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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()
mid1 = a[int(len(a) / 2) - 1]
mid2 = a[int(len(a) / 2)]
res1 = res2 = 0
for i in range(n):
    res1+=abs(a[i] - mid1)
    res2+=abs(a[i] - mid2)
print(min(res1,res2))

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]
sum = 0;
for x in a:
  sum += abs(x - m)
print(sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a_list1 = [int(a) for a in input().split()]
a_list2 = list()
for i in range(1, n+1):
    a_list2.append(a_list1[i-1]-i)
a_list3 = sorted(a_list2)

def sunuke_func(m):
    b = a_list3[m-1]
    sumv = 0
    for i in range(n):
        sumv += abs(a_list3[i]-b)
    return sumv

if n%2 == 0:
    m1 = n//2
    m2 = n//2 + 1
    sumv1 = sunuke_func(m1)
    sumv2 = sunuke_func(m2)
    if sumv1 < sumv2:
        print(sumv1)
    else:
        print(sumv2)
else:
    m = n//2 + 1
    sumv = sunuke_func(m)
    print(sumv)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

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

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

d.sort()
m = d[int(n/2)]

s = 0
for i in range(n):
    s += abs((a[i] - (i + 1 + m)))

print(s)

Submission status: Accepted

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

X = A - np.arange(1,N+1,dtype='int')
b = int(np.median(X))
out = np.sum(np.abs(X - b))

print(out)

Submission status: Accepted

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

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

b = s[n//2]

sm = 0
for i in range(0, n):
    sm = sm + abs(s[i] - b)

print(sm)

Submission status: Accepted

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

B_s = sorted([y - x - 1 for x, y in enumerate(a)])


medians = []
if N%2 == 0 :
    medians.append(B_s[N // 2])
    medians.append(B_s[N // 2 + 1])
else :
    medians.append(B_s[N // 2])
    
min_sum = sum(a)

for m in medians :
    sum_over = 0
    
    for i in range(N) :
        sum_over += abs(B_s[i] - m)
        
    min_sum = min(min_sum, sum_over)
    
print(min_sum)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# encoding: utf-8

#input
n = int(input())
A = [int(i) for i in input().split()]
# print(A)
def sad_value(A,b):
    sadness = 0
    for i in range(len(A)):
        sadness += abs(A[i]-b-i-1)
    return sadness
A_i = []
for i in range(len(A)):
    A_i.append(A[i]-i)
A_i.sort()
sadness = []
for i in range(5):
    a = int(n/2)
    sadness.append(sad_value(A, A_i[a]-2+i))
sadness.sort()
print(sadness[0])

Submission status: Accepted

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

temp = range(1,N+1)
temp2=[]
counter_m = 0
temp_ans = 10**20
ans = 0
# counter_p = 0
for i in range(N):
    temp2.append(A[i]-temp[i])
    if A[i] -temp[i] <= 0:
        counter_m+=1
temp2 = sorted(temp2)
if len(temp2)%2 == 0:
    b = (temp2[int(len(temp2)/2)]+temp2[int(len(temp2)/2 - 1)])/2
else:
    b = temp2[int(len(temp2)/2)]
# print(b)

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

Submission status: Accepted

Solution code:
from statistics import median

def main():
    N = int(input())
    strs = input()
    As = [int(num) for num in strs.split()]
    nums = [a - i for i, a in enumerate(As, 1)]
    m = int(median(nums))
    print(sum([abs(a - m) for a in nums]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = [A[i - 1] - i for i in range(1, N + 1)]
A.sort()
if N % 2 == 1:
    b = A[(N - 1) // 2]
else:
    b = round((A[N // 2] + A[N // 2 - 1])) // 2
print(sum([abs(A[i] - b)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]

for i in range(n):
    a[i] = abs(a[i]-b)
print(sum(a))

Submission status: Accepted

Solution code:
# https://beta.atcoder.jp/contests/abc102/tasks/arc100_a
import statistics
import numpy as np

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

difference_list = nums - iteration
median = statistics.median(difference_list)
print(int(sum(abs(difference_list - median))))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# AtCoder Beginner Contest


if __name__ == '__main__':
    from statistics import median

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

    # See:
    # https://www.youtube.com/watch?v=UX4AuiCVtN4
    # https://beta.atcoder.jp/contests/abc102/submissions/2768315
    mod_a = sorted([ai - i for i, ai in enumerate(a, 1)])
    b = median(mod_a)

    for i in range(n):
        total += abs(mod_a[i] - b)

    print(int(total))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# AtCoder Beginner Contest


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    total = 0

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

    sorted_a = sorted(a)
    b = sorted_a[n // 2]

    for i in range(n):
        total += abs(a[i] - b)

    print(int(total))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
L=len(a)
for i in range(L):
    a[i]-=(i+1)
a=sorted(a)
c=0
d=0
ans=0
ans_c=0
ans_d=0
if len(a)%2==1:
    c=int(len(a)/2)+1
    for i in a:
        ans+=abs(i-a[c-1])
    print(ans)
else:
    c=int(len(a)/2)
    d=int(len(a)/2)+1
    for i in a:
        ans_c+=abs(i-a[c-1])
        ans_d+=abs(i-a[d-1])
    print(min(ans_c,ans_d))

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 a:
    ans += abs(i - b)

print(ans)

Submission status: Accepted

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

A = [A[i]-(i+1) for i in range(N)]
A.sort()
b =  A[len(A)/2]
print sum(map(lambda x:abs(x-b),A))

Submission status: Accepted

Solution code:
import statistics

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

sub_a = [a_n - i - 1 for i, a_n in enumerate(a)]
median = statistics.median(sub_a)
print(int(sum([abs(sub_a_n-median) for sub_a_n in sub_a])))

Submission status: Accepted

Solution code:
import math
import statistics
import numpy as np
size = int(input())
A = np.array(list(map(int,input().split())))
i = np.array(list(range(1,size+1)))

remain_list = A-i
median = statistics.median(remain_list)
print(int(sum(abs(remain_list - median))))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from statistics import *

n = int(input())
list = input().split()

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

b = int(median(list))

for i in range(n):
    list[i] = abs(list[i]-b)
    
print(sum(list))

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


count = 0
b=B[N/2]
for i in range(N):
    count += abs(B[i]-b)
print count

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
from copy import deepcopy

n=int(input())
a=list(map(int,input().split()))
b=a
d=[]
m=0
for i,j in enumerate(a):
    d.append(j-i-1)
    # print(d[i])
e=deepcopy(d)
e.sort()
c=e[n//2]
ans=0
for i,j in enumerate(d):
    # print(d[i])
    ans+=abs(d[i]-c)
print(ans)

Submission status: Accepted

Solution code:
import statistics
import math

N = int(input())
a = input().split()
ans = 0
for i in range(0,N):
	a[i] = int(a[i])-i
med = int(statistics.median(a))
for i in range(0,N):
	ans += abs(a[i]-med)
print(int(ans))

Submission status: Accepted

Solution code:
list_length = int(input())
list_num = list(map(int, input().split()))

for num in range(1,list_length+1):
    list_num[num-1] = list_num[num-1] - (num+1)

max = 0

list_num.sort()

if (list_length % 2 != 0):
    b = list_num[(list_length+1)//2 - 1]
else:
    b = list_num[list_length//2 - 1]


for num in range(1,list_length+1):
    max += abs(list_num[num-1] - b )


print (max)

Submission status: Accepted

Solution code:
import statistics
N = int(input())
A = input().rstrip().split()

i = 0
kari =[]
for j in A:
    i +=1
    B = int(j)-i
    kari.append(B)
b= statistics.median(kari)

sum = 0
for i in kari:
    sum+=abs(i-b)
print(int(sum))

Submission status: Accepted

Solution code:
import math
import statistics
N = int(input())

A = input().rstrip().split()
#print(A)
i = 0
kari =[]
for j in A:
    i +=1
    B = int(j)-i
    kari.append(B)
#print(kari)
b = statistics.median(kari)

sum = 0
for i in kari:
    sum+=abs(i-b)
print(int(sum))

Submission status: Accepted

Solution code:

N = int(input())
li = input().rstrip().split()

le =[0]*N
le2 = [0]*N

for i in range(0,N):
    le[i]=int(li[i])


for i in range(0,N):
    le2[i]=le[i]-i-1
le2.sort()


b = le2[int(N/2)]
sum = 0
for i in range(0,N):
    sum = sum + abs(le[i]-i-1-b)

print(sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())

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

arrb = []

for i in range(n):
	arrb.append(arr[i]-i)

med = np.median(arrb)

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

print int(ans)

Submission status: Accepted

Solution code:
n = int(input())
array = [int(x) for x in input().split()]
array2 = [x-(i+1) for i, x in enumerate(array)]

b_ = sorted(array2)[n//2]

res = [abs(array[x]-(b_+x+1)) for x in range(n)]
print(sum(res))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

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

A = np.asarray(A)
i = np.asarray([x for x in range(1, N+1)])
A = A - i

#b = np.round(np.median(A))
b = np.ceil(np.median(A))
A = A - b
A = np.absolute(A)
print(A.sum().astype(np.uint64))

Submission status: Accepted

Solution code:
import numpy as np

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

A = np.asarray(A)
i = np.asarray([x for x in range(1, N+1)])
A = A - i

b = np.round(np.median(A))
A = A - b
A = np.absolute(A)
print(A.sum().astype(np.uint64))

Submission status: Accepted

Solution code:
import math
n = int(input())
a_tmp = input().split()
a_tmp1 = []
for i in range(n):
    a_tmp1.append(int(a_tmp[i])-i-1)
a = sorted(a_tmp1)
if n % 2 == 0:
    x = a[n//2]
else:
    x = a[n//2]
ans = 0
for _ in a:
    ans += math.fabs(_ - x)
print(int(ans))

Submission status: Accepted

Solution code:
# coding: utf-8

import statistics

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

for i,num in enumerate(a):
    a[i] = a[i] - (i + 1)

b = statistics.median_low(a)

res = 0
for i in a:
    res += abs(i - b)

print(res)

Submission status: Accepted

Solution code:
# coding: utf-8

import statistics

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

for i,num in enumerate(a):
    a[i] = a[i] - (i + 1)

b = int(statistics.median(a))

res = 0
for i in a:
    res += abs(i - b)

print(res)

Submission status: Accepted

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output
def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

# Binary converter
def to_bin(x):
    return bin(x)[2:]

# --------------------------------------------

dp = None

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

    i = 0
    while i < len(A):
        A[i] -= (i + 1)
        i += 1

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

    sad = 0
    for a in A:
        sad += abs(a - b)

    print(sad)

main()

Submission status: Accepted

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

ar = a - range(1, len(a) + 1)
bm = np.median(ar)
b1, b2 = np.floor(bm), np.ceil(bm)
result1 = int(min(np.abs(ar - b1).sum(), np.abs(ar - b2).sum()))

bm = np.mean(ar)
b1, b2 = np.floor(bm), np.ceil(bm)
result2 = int(min(np.abs(ar - b1).sum(), np.abs(ar - b2).sum()))
print(min(result1, result2))

Submission status: Accepted

Solution code:
import copy
input()
a=[int(i) for i in input().split()]
sa=copy.copy(a)
for i in range(len(a)):
    sa[i]=sa[i]-(i+1)
sa.sort()
msa=sa[int(len(sa)/2)]
sb=0
for i in range(len(a)):
    sb=sb+abs(a[i]-(msa+i+1))
print(sb)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

def main():
    #入力
    N = int(input())
    lists = list(map(int, input().split()))

    #変数
    int_list = [i for i in range(1, N+1)]
    #Ai - iを計算
    diff = [x - y for (x, y) in zip(lists, int_list)]
    diff.sort()
    
    #中央値をbとしたものが最小となる
    b = diff[int(len(diff)/2)]
    sadness = 0
    for i in diff:
        sadness += abs(i-b)
    print(sadness)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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()
median = A[N//2]

for i in range(N):
    A[i] -= median
    A[i] = abs(A[i])
print(sum(A))

Submission status: Accepted

Solution code:
def is_even(u):
    return u % 2 == 0


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

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

a_sorted = sorted(adash)


if is_even(n):
    b = a_sorted[n//2]
else:
    b = a_sorted[(n-1)//2]
ans = 0
for i in range(n):
    ans += abs(adash[i] - b)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

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

a = np.array(A)

m = int(np.median(a))

sad = int(abs(a-m).sum())

M = int(a.max() - a.min())

for i in range(1,M):
    s = int(abs(a-m-i).sum())
    if sad > s:
        sad = s
    else:
        break

for i in range(1,M):
    s = int(abs(a-m+i).sum())
    if sad > s:
        sad = s
    else:
        break

print(sad)

Submission status: Accepted

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

Submission status: Accepted

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

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

A = sorted(A)
b = A[len(A)//2]

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

print(ans)

Submission status: Accepted

Solution code:
from statistics import median

N = int(input())
numbers = [int(a)-i for i, a in enumerate(input().split())]
b = median(numbers)
abs_1 = sum([abs(c-int(b)) for c in numbers])
abs_2 = sum([abs(c-int(b)-1) for c in numbers])
print(min(abs_1, abs_2))

Submission status: Accepted

Solution code:
import math

n = int(input())
a = [int(i) for i in input().split()]
b = [elem - i for i, elem in enumerate(a, 1)]
b.sort()
center = b[math.floor(len(b) / 2)]
c = [abs(i - center) for i in b]
print(sum(c))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import statistics

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


for i in range(len(a)):
    a[i] -= (i+1)
med = statistics.median(a)
b = [a_i-med for a_i in a] 
S=0
for i in b:
    S += abs(i)
    
print(int(S))

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
a = np.array(sorted([int(num) - i for i, num in enumerate(input().split())]))

if N % 2 == 0:
    center = center = int(N/2-1) if a[int(N/2-1)] >= a[int(N/2)] else int(N/2)
else:
    center = int((N-1)/2)

a = np.abs(a - a[center])
print(sum(a))

Submission status: Accepted

Solution code:
N = int(input())
*A, = map(int, input().split())
for i in range(N):
    A[i] -= i+1
A.sort()
ans = 10**30
S = sum(A); s = 0
for i in range(N):
    s += A[i]
    ans = min(ans, (S-s-A[i]*(N-i-1)) + A[i]*(i+1)-s)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from statistics import median_low

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

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

b = median_low(A)
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 桁数の入力
a = int(input())
# スペース区切りの整数の入力
b = input().split()
b = list(map(int, b))
c = list(range(1, a + 1))

d = []
for i, j in zip(b, c):
    d.append(i-j)
d.sort()
e = d[a // 2]
f = 0
for i in range(a):
    f += abs(d[i]-e)

print(f)

Submission status: Accepted

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

Ni = list(range(1, N + 1))

sum_diff = [(a-i) for a, i in zip(A, Ni)]
sum_diff.sort()
b = sum_diff[N // 2]

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

Submission status: Accepted

Solution code:
n = input()
n = int(n)
a = input().split()
a = [int(aa) for aa in a]
 
ans = 10000000000000000
 
l = -100000000000
r =  100000000000
 
for count in range(100):
    mid = (l + r) // 2
    temp = 0
    for i in range(n):
        temp1= abs(a[i] - (mid + i + 1))
        temp2= abs(a[i] - ((mid - 1) + i + 1))
        temp += temp1 - temp2
    if temp > 0:
        r = mid
    else:
        l = mid
for b in range(l, r + 1):
    temp = 0
    for i in range(n):
        temp += abs(a[i] - (b + i + 1))
    ans = min(ans, temp)
print(ans)

Submission status: Accepted

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

ans = 10000000000000000

l = -100000000000
r =  100000000000

for count in range(100):
    mid = (l + r) // 2
    temp = 0
    for i in range(n):
        temp1= abs(a[i] - (mid + i + 1))
        temp2= abs(a[i] - ((mid - 1) + i + 1))
        temp += temp1 - temp2
    if temp > 0:
        r = mid
    else:
        l = mid
for b in range(l, r + 1):
    temp = 0
    for i in range(n):
        temp += abs(a[i] - (b + i + 1))
    ans = min(ans, temp)
print(ans)

Submission status: Accepted

Solution code:
n = input()
n = int(n)
a = input().split()
a = [int(aa) for aa in a]
 
ans = 10000000000000000
 
l = -100000000000
r =  100000000000
 
for count in range(100):
    mid1 = 1 * (r - l) // 3 + l
    mid2 = 2 * (r - l) // 3 + l
    temp1 = 0
    temp2 = 0
    for i in range(n):
        temp1 += abs(a[i] - (mid1 + i + 1))
        temp2 += abs(a[i] - (mid2 + i + 1))
    if temp1 < temp2:
        r = mid2
    else:
        l = mid1
for b in range(l, r + 1):
    temp = 0
    for i in range(n):
        temp += abs(a[i] - (b + i + 1))
    ans = min(ans, temp)
print(ans)

Submission status: Accepted

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

ans = 10000000000000000

l = -100000000000
r =  100000000000

for count in range(100):
    mid1 = 1 * (r - l) // 3 + l
    mid2 = 2 * (r - l) // 3 + l
    temp1 = 0
    temp2 = 0
    for i in range(n):
        temp1 += abs(a[i] - (mid1 + i + 1))
        temp2 += abs(a[i] - (mid2 + i + 1))
    if temp1 < temp2:
        r = mid2
    else:
        l = mid1
for b in range(l, r + 1):
    temp = 0
    for i in range(n):
        temp += abs(a[i] - (b + i + 1))
    ans = min(ans, temp)
print(ans)

Submission status: Accepted

Solution code:
from statistics import median

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

b = [v - (i + 1) for i, v in enumerate(a)]

median = int(median(b))

c = sum(abs(v - median) for v in b)

print(c)

Submission status: Accepted

Solution code:
from statistics import median

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

b = []

for i, v in enumerate(a):
    b.append(v - (i + 1))

median = int(median(b))

c = 0

for v in b:
    c = c + abs(v - median)

print(c)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]
B = [ av - i  for i, av in enumerate(a,1)]
B.sort()

middle = n //2
b = B[middle]

result = 0
for a2 in B:
  result = result + abs(a2 -b)
print(result)