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: Time Limit Exceeded

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

a.sort()
w=10**9
for j in range(a[0],a[n-1]+1):
    s=0

    for k in range(n):
        s+=abs(a[k]-j)
    if s<w :
        w=s
print(w)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
list1=[int(i) for i in input().split()]
list2=[]
for i in range(max(list1)-min(list1)+N+1):
    kana=0
    for j in range(N):
        kana+=abs(list1[j]-(min(list1)-N+i+j))
    list2.append(kana)
print(min(list2))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = 0
flag = True

while flag:
    sum = 0
    plus = 0
    zero = 0
    minus = 0
    for index,i in enumerate(a):
        tmp = i - (b+(index+1))
        if tmp > 0:
            sum += tmp
            plus += 1
        elif tmp == 0:
            zero += 1
        else:
            sum += -1 * tmp
            minus += 1
    if plus > minus:
        if plus <= (zero + minus):
            break
        b += 1
    elif plus == minus:
        break
    else:
        if minus <= (zero + plus):
            break
        b -= 1
print(sum)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
S=list(map(int,input().split()))

ans=10**10

ave=0
for i in range(N):
    ave+=S[i]
ave=ave//N

for i in range(ave-N//2-100,ave-N//2+100):
    goukei=0
    for j in range(N):
        goukei+=abs(S[j]-(i+j+1))
        
    if ans>goukei:
        ans=goukei
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def k(arr,n):
  o=1
  s=0
  for k in arr:
    s+=abs(k-(n+o))
    o+=1
  return s

input()
a=input().split()
b=[]
for x in a:
  b.append(int(x))

r=9999999999
for z in range(-max(b),max(b)):
  buf=k(b,z)
  if buf<r:
    r=buf

print(r)

Submission status: Time Limit Exceeded

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

b_0 = round((NM-NP)/N - (N/2))

out = NM**2
for j in range(N):
	b = b_0 + j
	sad = 0
	for i in range(N):
		sad = sad + abs(A[i]-b-i-1)
	if sad<out:
		out = sad
print(out)

Submission status: Time Limit Exceeded

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

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

while True:
    p_num = []
    n_num = []
    z_num = []
    for i in range(len(b)):
        if b[i] > 0:
            p_num.append(b[i])
        elif b[i] < 0:
            n_num.append(b[i])
        else:
            z_num.append(b[i])

    if len(p_num) > len(n_num) + len(z_num):
        for i in range(len(b)):
            b[i] = b[i] - 1
    elif len(n_num) > len(p_num) + len(z_num):
        for i in range(len(b)):
            b[i] = b[i] + 1
    else:
        break

ans = 0
for i in range(len(b)):
    ans += abs(b[i])

print(ans)

Submission status: Time Limit Exceeded

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

res = float('inf')
for i in range(min(a),max(a)+1):
    sum = 0
    for j in a:
        sum += abs(j - i)
    res = min(res, sum)
print(res)

Submission status: Time Limit Exceeded

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

for i in range(-max(A),max(A)):
    sad = 0
    ite = 1
    for j in A:
        sad += abs(j - (i + ite))
        ite += 1
    ans.append(sad)

print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[a-i-1 for i,a in enumerate(map(int,input().split()))]
k=sum(A)//N+1
print(min(sum(abs(a-x)for a in A)for x in range(min(0,k-1),max(k+1,1))))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
AS = input().split()
for i in AS:
    i = int(i)
abs_list = []
for i in range (-int(max(AS))-1, int(max(AS)) + 1):
    counter = 0
    for j in range (1,N+1):
        counter += abs(int(AS[j-1]) - i - j)
    abs_list.append(counter)
print(min(abs_list))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = input().split()
i = 0
while i < N:
    A[i] = int(A[i])
    i += 1
i = 0
B = []
while i < N:
    B.append(A[i] - i)
    i += 1
maxB = max(B)
minB = min(B)
M = max(B) - min(B) + 1
C = []
i = 0
while i < M:
    K = min(B) + i
    temp = 0
    j = 0
    while j < N:
        temp += abs(B[j] - K)
        j += 1
    C.append(temp)
    i += 1
print(min(C))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
sadlist = []
for i in range(min(a) - n, max(a) + n):
    sad = 0
    for j in range(n):
        sad = sad + abs(a[j] - (i + j + 1))
    sadlist.append(sad)
print(min(sadlist))

Submission status: Time Limit Exceeded

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

ans=9999999999
for b in range(min(min(A),max(A)-N),max(A)):
    num=0
    for i,a in enumerate(A):
        num += abs(a-(b+i+1))
    if num<ans:ans=num
print(ans)

Submission status: Time Limit Exceeded

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

points = [(i+1, y) for i, y in enumerate(A)]

diff_list = [y - x for x, y in points]
diff_list.sort()

max_b = diff_list[-1]
min_b = diff_list[0]

sadness_list = []
for b in range(min_b, max_b+1):
    sadness_list.append(sum([abs(y - (b + x)) for x, y in points]))

print(min(sadness_list))

Submission status: Time Limit Exceeded

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

def abs(x):
    if x>=0:
        return x
    else:
        return x*(-1)

k=[]
for b in range((-1)*max(a),max(a)+1):
    k.append(0)
    for i in range(n):
        k[b+max(a)]+=abs(a[i]-(b+i+1))
        
print(min(k))

Submission status: Time Limit Exceeded

Solution code:
from statistics import mean
import math
N = int(input())
*A, = map(int, input().split())
B = [A[i]-i for i in range(N)]
b = mean(B)
bm = math.floor(b)
K = [x - bm for x in B]
KZ = [abs(x) for x in K]
Z = sum(KZ)
for i in range(2000):
    C = [abs(x-i+1000) for x in K]
    Z = min([sum(C),Z])
print(int(Z))

Submission status: Time Limit Exceeded

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

a = []
for i in range(n):
    a.append(aa[i]-(i+1))
    
b = {}
for i in a:
    if i in b:
        b[i] += 1
    else:
        b.update({i:1})
        
ans_l = []
for k in b.keys():
    counts = 0
    for k_, val in b.items():
        counts += (abs(k - k_)) * val
    ans_l.append(counts)
    
print(min(ans_l))

Submission status: Time Limit Exceeded

Solution code:
def BinSearch(A, hi, lo):
    b = (hi + lo) // 2
    tmp0 = FindAns(A, b - 1)
    tmp1 = FindAns(A, b)
    if hi == lo:
        tmp2 = FindAns(A, b + 1)
        return min(tmp0, tmp1, tmp2)
    if tmp0 < tmp1:
        return BinSearch(A, b - 1, lo)
    else:
        return BinSearch(A, hi, lo + 1)
    
def FindAns(A, b):
    ans = 0
    for a in A:
        ans += abs(a - b)
    return ans

n = int(input())
A = list(map(int, input().split()))
for i in range(n):
    A[i] -= i + 1
    
hi = max(A)
lo = min(A)

print(BinSearch(A, hi, lo))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
S=[]
d=sum(A)//len(A)+1
for b in range(-d,d):
    s=0
    for i in range(N):
        s+=abs(A[i]-b-i)
    S.append(s)
print(min(S))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
max_A = 0
max_i = 0
total = 0
min_total = float("inf")

for i, v in enumerate(A):
    if v > max_A:
        max_A = v
        max_i = i

for b in range(-1*abs(max_A - max_i), (max_A - max_i)+1):
    total = 0
    for i in range(N):
        total += abs(A[i]-(b+i))
    if min_total > total:
        min_total = total

print(min_total)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
 
A=list(map(int,input().split()))
 
B=max(A)
 
answer=10**9
 
for j in range(-B,B+1):
	total=0
	for i in range(len(A)):
		total=total+abs(A[i]-(i+j))
		if total>=answer:
			break;
	answer=min(total,answer)
print(answer)

Submission status: Time Limit Exceeded

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

max = max(a)
list = []
for b in range(max*-1,max):
  sum = 0
  for i, j in enumerate(a):
    i = i+1
    sum += abs(j - (b+i))
  list.append(sum)

print(min(list))

Submission status: Time Limit Exceeded

Solution code:
def BinSearch(A, hi, lo):
    b = (hi + lo) // 2
    tmp0 = FindAns(A, b - 1)
    tmp1 = FindAns(A, b)
    tmp2 = FindAns(A, b + 1)
    if hi == lo:
        return min(tmp0, tmp1, tmp2)
    if tmp0 < tmp1:
        return BinSearch(A, b - 1, lo)
    else:
        return BinSearch(A, hi, lo + 1)
    
def FindAns(A, b):
    ans = 0
    for a in A:
        ans += abs(a - b)
    return ans

from bisect import  bisect_left as bl
n = int(input())
A = list(map(int, input().split()))
for i in range(n):
    A[i] -= i + 1
    
hi = max(A)
lo = min(A)

print(BinSearch(A, hi, lo))

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8

def calcSad(a_list, b):
    sadness = 0
    for i in range(len(a_list)):
        sadness += abs( a[i] - (b + i + 1) )
    return sadness

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split(" ")))
    flag = 0
    b = 0
    min = calcSad(a,b)
    dir = 1
    while flag == 0:
        if dir == 1:
            b += 1
            tmp = calcSad(a,b)
            if tmp < min:
                min = tmp
            else:
                dir = -1
                b = 0
        if dir == -1:
            b -= 1
            tmp = calcSad(a,b)
            if tmp < min:
                min = tmp
            else:
                flag = 1
    print(min)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


def main():
    N = int(stdin.readline().rstrip())
    A = [int(x) for x in stdin.readline().rstrip().split()]
    result0 = sum([abs(x - (-1 + i + 1)) for i, x in enumerate(A)])
    result1 = sum([abs(x - (0 + i + 1)) for i, x in enumerate(A)])
    result2 = sum([abs(x - (1 + i + 1)) for i, x in enumerate(A)])
    if min(result0, result1, result2) == result1:
        print(result1)
    elif min(result0, result1, result2) == result0:
        b = -2
        result = result0
        while True:
            tmp = sum([abs(x - (b + i + 1)) for i, x in enumerate(A)])
            if result < tmp:
                print(result)
                return
            result = tmp
            b -= 1
    else:
        b = 2
        result = result0
        while True:
            tmp = sum([abs(x - (b + i + 1)) for i, x in enumerate(A)])
            if result < tmp:
                print(result)
                return
            result = tmp
            b += 1


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	N = int(input())
	seq = list(map(int, input().split()))
	seq = [seq[i] - i - 1 for i in range(N)]
	def helper(b):
		return sum([abs(seq[i] - b) for i in range(N)])
	temp = []
	for i in range(N):
		temp.append(helper(seq[i]))
	print(min(temp))
	return 0
main()

Submission status: Time Limit Exceeded

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

ans = list()
for i in range(-1 * max(a), n):
    tmp = 0
    for j in range(n):
        tmp += abs(a[j] - (i + (j + 1)))
    ans.append(tmp)

print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
a_tmp = input().split()
a = []
for i in range(n):
    a.append(int(a_tmp[i]))
a1 = []
for i in range(n):
    a1.append(a[i]-1-i)
b_max = max(a1)
b_min = min(a1)
sadness = []
for b in range(b_min, b_max+1):
    abs = [math.fabs(a1[i]-b) for i in range(n)]
    sadness.append(int(sum(abs)))
print(min(sadness))

Submission status: Time Limit Exceeded

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

ans = sum(A)

for b in range(min(A)-N,max(A)+N):
        tmp = sum([abs(A[i]-(b+i+1)) for i in range(N)])
        if ans > tmp:
                ans = tmp

print(ans)

Submission status: Time Limit Exceeded

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

ans = float("inf")
for b in range(min(A) - N, max(A) + 1):
    cost = 0
    for index, i in enumerate(A):
        cost += abs(b + index + 1 - i)
    ans = min(ans, cost)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[a-i-1 for i,a in enumerate(map(int,input().split()))]
k=abs(sum(A)//N+1)
print(min(sum(abs(a-x)for a in A)for x in range(-k-1,k+1)))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
S=list(map(int,input().split()))

ans=10**10

ave=0
for i in range(N):
    ave+=S[i]
ave=ave//N

for i in range(ave-N-1000,ave-N+1000):
    goukei=0
    for j in range(N):
        goukei+=abs(S[j]-(i+j+1))
        
    if ans>goukei:
        ans=goukei
        
print(ans)

Submission status: Time Limit Exceeded

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

from copy import deepcopy
n = int(input())
A = list(map(int, input().split()))
for i in range(len(A)):
    A[i] -= i + 1

ans = 10 ** 100
for a in A:
    B = deepcopy(A)
    for i in range(len(A)):
        B[i] -= a
    count = 0
    for b in B:
        count += abs(b)
    ans = min(ans, count)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
S=[]
B=[max(A), N]
for b in range(-max(B),max(B)):
    s=0
    for i in range(N):
        s+=abs(A[i]-b-i)
    S.append(s)
print(min(S))

Submission status: Time Limit Exceeded

Solution code:
import sys 

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

a_sorted = sorted(a)

a_max = a_sorted[-1]
a_min = a_sorted[0] - n

kanasisa_min = sys.maxsize
for b in range(a_min,a_max+1):
    kanasisa = 0
    for i,data in enumerate(a):
        kanasisa += abs(data - (b + i + 1))
    if kanasisa < kanasisa_min:
        kanasisa_min = kanasisa

print(kanasisa_min)

Submission status: Time Limit Exceeded

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

def abs(a):
    if a<0:
        return -a
    else:
        return a

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

a.sort()
ans=10**12
middle=(a[0]+a[n-1])//2
for b in range(middle-10**3,middle+10**3):
    S=0
    for j in range(n):
        S+=abs(a[j]-b)
    ans=min(ans,S)
if ans==10**12:
    ans=0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
S=list(map(int,input().split()))

ans=10**10

ave=0
for i in range(N):
    ave+=S[i]
ave=ave//N

for i in range(ave-200000,ave+10000):
    goukei=0
    for j in range(N):
        goukei+=abs(S[j]-(i+j+1))
        
    if ans>goukei:
        ans=goukei
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

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

B=max(A)

answer=10**9

for j in range(-B,B+1):
	total=0
	for i in range(len(A)):
		total=total+abs(A[i]-(i+j))
	answer=min(total,answer)
print(answer)

Submission status: Time Limit Exceeded

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

def abs(a):
    if a<0:
        return -a
    else:
        return a

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

a.sort()
ans=10**12
middle=(a[0]+a[n-1])//2
for b in range(middle-10**4,middle+10**4):
    S=0
    for j in range(n):
        S+=abs(a[j]-b)
    ans=min(ans,S)
if ans==10**12:
    ans=0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split(' ')]
def score(C, b):
    s = 0
    for i, Ci in enumerate(C):
        s += abs(Ci - b)
    return s

C = [Ai - (i+1) for i, Ai in enumerate(A)]
min_b = min(C)
max_b = max(C)
if min_b == max_b:
    print(0)
else:
    s = float('inf')
    for b in range(min_b, max_b):
        si = score(C, b)
        if si < s:
            s = si
    print(s)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
INF = 10**10
n = int(input())
a = [int(_) - (i + 1) for i, _ in enumerate(input().split())]
a.sort()

grief = INF
for b in range(a[0], a[-1] + 1):
    tmp = sum([abs(ai - b) for ai in a])
    if tmp < grief:
        grief = tmp

print(grief)

Submission status: Time Limit Exceeded

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

a = []
for i in range(n):
    a.append(aa[i]-(i+1))
        
c = list(set(a))

#print(c[-1][0])

count = []

for i in c:
    counts = 0
    for j in a:
        counts += abs(j-i)
    count.append(counts)
print(min(count))

Submission status: Time Limit Exceeded

Solution code:
import  math


def sadness(numbers, b, n):
    sum = 0
    for i in range(1, n+1):
        sum += abs(numbers[i-1] - (b+i))
    return sum


n = int(input())
arr = input().split(" ")
numbers = []
for i in range(0,len(arr)):
    numbers.append(int(arr[i]))

max = sorted(numbers)[len(numbers)-1]
#print(max)
min = 9223372036854775807
for i in range(-max**2, max**2):
   s = sadness(numbers,i,n)
   #print(min)
   if s < min:
       min = s
print(min)

Submission status: Time Limit Exceeded

Solution code:
def abs(x):
    if x>0:
        return x
    else:
        return x * (-1)

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    a_mi = list(a[idx] - idx for idx in range(len(a)))

    s = float('inf')
    for b in range(min(a_mi), max(a_mi) + 1):
        s = min(s, sum(abs(x - b) for x in a_mi))
    print(s)

Submission status: Time Limit Exceeded

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

ans=99999999
for b in range(min(A)-N,max(A)+N+1):
    num=0
    for i,a in enumerate(A):
        num += abs(a-(b+i+1))
    if num<ans:ans=num
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split(' ')]
def score(A, b):
    s = 0
    for i, Ai in enumerate(A):
        s += abs(Ai - (b + i + 1))
    return s
s = float('inf')
for b in range(-max(A), max(A)):
    si = score(A, b)
    if si < s:
        s = si
print(s)

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
a = map(int, raw_input().split())
for i in range(len(a)):
  a[i] -= (i+1)
min_total = sum([abs(t) for t in a])
for item in a:
  total = sum([abs(t-item) for t in a])
  if total < min_total:
    min_total = total

print(min_total)

Submission status: Time Limit Exceeded

Solution code:
# 整数の入力
N = int(input())
l = list(map(int, input().split(" ")))

l_ = []
for i in range(N):
    l_.append(l[i] - i - 1)

# print(l_)


count_list = []
for j in range(min(l_), max(l_) + 1):
    # print(j)
    count = 0
    for num in l_:
        count += abs(num - j)

    count_list.append(count)

# print("===")
print(min(count_list))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import groupby
N = int(input())
A = list(map(int, input().split(' ')))

p = [v - (i + 1) for i, v in enumerate(A)]
s_p = list(groupby(sorted(p)))

res = float('INF')
for k, g in s_p:
    res = min(res, sum([abs(i - k) for i in p]))
    
print(res)

Submission status: Accepted

Solution code:
import statistics

n = int(input())
A = list(map(int, input().split()))
A_1 = [A[i] - (i+1) for i in range(n)]
m = int(statistics.median(A_1))
A_2 = [abs(m - A_1[i]) for i in range(n)]
print(sum(A_2))

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 j in range(N):
  A[j] = abs(A[j]-b)
 
print(sum(A))

Submission status: Accepted

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

for i in range(N):
  A[i] -= i+1  
A.sort()
b=A[N//2]
for j in range(N):
  A[j] = abs(A[j]-b)

print(sum(A))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import statistics


def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N = int(input())
    A = list(map(int, input().split()))

    return N, A


def main(N: int, A: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): 整数列の長さ(1 <= N <= 2 × 10^5)
        A (list): 整数列(1 <= A_i <= 10^9)
    """
    # 求解処理
    B = [A[i] - (i + 1) for i in range(N)]
    b = statistics.median_high(B)
    ans = sum([abs(B[i] - b) for i in range(N)])

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, A = get_input()

    # メイン処理
    main(N, A)

Submission status: Accepted

Solution code:
import statistics
n=int(input())
alist=list(map(int, input().split()))
blist=[]
for i in range(n):
  blist.append(alist[i]-i-1)
blist.sort()
median=statistics.median_high(blist)
ans=0
for i in range(n):
  ans+=abs(blist[i]-median)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import statistics

# 標準入力を取得
N = int(input())
A = list(map(int, input().split()))

# 求解処理
A = [A[i] - (i + 1) for i in range(N)]
b = statistics.median_high(A)
ans = sum([abs(A[i] - b) for i in range(N)])

# 結果出力
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n = i_input()
    a = i_list()
    a = [k-(i+1) for i,k in enumerate(a)]

    a.sort()
    import statistics

    ans = int(statistics.median(a))
    trial = 0
    for i in a:
        trial += abs(i - ans)
    print(trial)


if __name__=="__main__":
    main()

Submission status: Accepted

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

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()
import bisect
z = bisect.bisect_left(A,0)
ans = sum(A[z:])-sum(A[:z])
if z > N-z:
    p = 0
    while z>N-z:
        b = A[z-1]
        ans += (N - 2*z) * (p-b)
        p = b
        z = bisect.bisect_left(A,b)
elif N > 2*bisect.bisect_right(A,0):
    z = bisect.bisect_right(A,0)
    p = 0
    while N-z>z:
        b = A[z]
        ans += (2*z - N) * (b-p)
        p = b
        z = bisect.bisect_right(A,b)
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A = [a - i for i, a in enumerate(A, start=1)]
    A.sort()
    b = A[N//2]
    print(sum([abs(a - b) for a in 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] = A[i] - i - 1

A = sorted(A)

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

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

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

b = a[n//2]

print(b * (n//2) - sum(a[:n//2]) + sum(a[n//2:]) - b * (n - n//2))

Submission status: Accepted

Solution code:
import statistics

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

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


mid=b
  
ans1=0

for j in range(n):
  ans1+=abs(a[j]-mid-(j+1))
  
print(ans1)

Submission status: Accepted

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

diff = [0] * n
for i in range(n):
    d = a[i] - (i + 1)
    diff[i] = d

diff = sorted(diff)
if n % 2 == 1:
    x = diff[n // 2]
else:
    x = (diff[(n // 2) - 1] + diff[n // 2]) // 2

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

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)
import numpy as np
an=np.array(a)
b=int(np.median(an))
ans=0
for i in a:
    ans+=abs(i-b)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]=a[i]-(i+1)
ac=Counter(a)
if len(a)%2==0:
    dist=len(a)//2
else:
    dist=len(a)//2+1
temp=0
for i,j in sorted(ac.items()):
    temp+=j
    if temp>=dist:
        ans=0
        for k in range(n):
            ans+=abs(a[k]-i)
        print(ans)
        
        exit()

Submission status: Accepted

Solution code:
def median(array):
    L = len(array)
    if L%2==0:
        return (array[L//2-1]+array[L//2])/2
    else:
        return array[L//2]

N = int(input())
A = []
for i, a in enumerate(map(int, input().split())):
    A.append(a-i)
A.sort()
b = median(A)
res = 0
for a in A:
    res += abs(a-b)
print(round(res))

Submission status: Accepted

Solution code:
import math
n = int(input())
ls = list(map(int,input().split()))
bs = [ls[i]-i-1 for i in range(n)]
bs.sort()
#print(bs)
if n %2 ==0:
    a = round(n/2)
    #print(a)
    can = [bs[a],bs[a-1],math.floor((bs[a] +bs[a-1])/2),math.ceil((bs[a] +bs[a-1])/2)]
elif n ==1:
    can = [bs[0],bs[0]]
else:
    a = math.floor(n/2)
    #print(a)
    can = [bs[a+1],bs[a-1],bs[a]]

#print(can)
result = 10**27
for k in can:
    ans =0
    for kn in bs:
        ans += abs(kn-k)
    #print(ans)
    result = min(result, ans)
    
print(result)

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
left = -10**9
right = 10**9

@lru_cache(maxsize=100000)
def cal(num):
  tmp = 0
  for i in range(n):
    tmp += abs(a[i]-(num+(i+1)))
  return tmp
 

while abs(right-left)>1:
  mid = (right+left)//2
  if cal(mid-1)<cal(mid+1):
    right = mid
  else:
    left = mid
print(min(cal(left),cal(right)))

Submission status: Accepted

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

for i in range(n):
    l[i] = l[i] - i-1
l.sort()
if n % 2 == 1:
    print(sum(list(map(lambda x: abs(x-l[((n//2))]),l))))
else:
    print(min(sum(list(map(lambda x: abs(x-l[(n//2)-1]),l))),sum(list(map(lambda x: abs(x-l[(n//2)]),l)))))

Submission status: Accepted

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

hu=0
sei=0
ans=0
ahu=[]
asei=[]

for i in range(1,n+1):
  a[i-1]-=i
  ans+=abs(a[i-1])
  if a[i-1]<0:
    hu+=1
    ahu.append(abs(a[i-1]))
  elif a[i-1]>0:
    asei.append(a[i-1])
    sei+=1
zero=n-sei-hu
now=0
#print(ahu)
#print(asei)
asei.sort()
ahu.sort()

if sei < hu and sei+zero <hu:
  sei+=zero
  for i in range((hu-sei)//2+1):
    ans-=(ahu[i]-now)*(hu-sei-2*i)
    now=ahu[i]
    
elif sei > hu and sei > hu+zero:
  hu+=zero
  for i in range((sei-hu)//2+1):
    ans-=(asei[i]-now)*(sei-hu-2*i)
    now=asei[i]

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

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

k = []
for i in range(N):
    y = abs(an[i] - b)
    k.append(y)
ans = sum(k)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]-=i+1
a=sorted(a)
def f(x):
    ans=0
    for i in range(n):
        ans+=abs(x-a[i])
    return ans

if n%2==0:
    m=n//2
else:
    m=(n+1)//2

print(f(a[m-1]))

Submission status: Accepted

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

Submission status: Accepted

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

print(ans)

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()
med = A[N // 2]
A = [abs(A[i] - med) for i in range(N)]

print(sum(A))