Problem:


Score : 300 points

Problem Statement

Snuke has an integer sequence A of length N.

He will freely choose an integer b.
Here, he will get sad if A_i and b+i are far from each other.
More specifically, the sadness of Snuke is calculated as follows:

abs(A_1 - (b+1)) + abs(A_2 - (b+2)) + ... + abs(A_N - (b+N))

Here, abs(x) is a function that returns the absolute value of x.

Find the minimum possible sadness of Snuke.

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the minimum possible sadness of Snuke.

Sample Input 1

5
2 2 3 5 5

Sample Output 1

2

If we choose b=0, the sadness of Snuke would be abs(2-(0+1))+abs(2-(0+2))+abs(3-(0+3))+abs(5-(0+4))+abs(5-(0+5))=2.
Any choice of b does not make the sadness of Snuke less than 2, so the answer is 2.

Sample Input 2

9
1 2 3 4 5 6 7 8 9

Sample Output 2

0

Sample Input 3

6
6 5 4 3 2 1

Sample Output 3

18

Sample Input 4

7
1 1 1 1 2 3 4

Sample Output 4

6



Sample input:
5
2 2 3 5 5


Sample output:
2

Submission status: Accepted

Solution code:
import math
N=int(input())
a=list(map(int,input().split()))
c_list=[]
for i in range(N):
    c_list.append(a[i]-i-1)
c_list.sort()

if len(c_list)%2!=0:
    ind=math.ceil(len(c_list)/2)
    b=c_list[ind-1]
else:
    ind=int(len(c_list)/2)
    b=math.floor((c_list[ind]+c_list[ind-1])/2)
d=0
for i in c_list:
    d+=abs(i-b)
print(d)

Submission status: Accepted

Solution code:
import statistics
import math

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

for bb in b:
    ans+=math.fabs(bb-midb)
print(int(ans))

Submission status: Accepted

Solution code:
import math

def median(l):
    n = len(l)
    ls = sorted(l)
    if n%2 == 0:
        m1 = ls[int(n/2)-1]
        m2 = ls[int(n/2)]
        return (m1+m2)/2
    
    return ls[int(n/2)]

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

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

A_m = median(A_)
A_m1 = math.floor(A_m)
A_m2 = math.ceil(A_m)

A_b = [sum([abs(a - i) for a in A_]) for i in (A_m1, A_m2)]

print(min(A_b))

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] -= i+1
 
A.sort()
b = median(A)
sad = 0
for i in range(N):
    sad += abs(A[i]-b)
print(int(sad))

Submission status: Accepted

Solution code:

import statistics

n=int(input())
a=[]
c=[]
for i in input().split():
    a.append(int(i))
    c.append(a[-1]-len(a))

b=round(statistics.median(c))
k=0

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

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*
N = int(input())
nums = list(map(int, input().split()))
nums = [ nums[i]-i-1 for i in range(N) ]
nums_s = sorted(nums)
b1 = nums_s[N//2]
b2 = nums_s[N//2-1]
res = []
for b in [b1, b2]:
    result = 0
    for i in range(1,N+1):
        result += abs(nums[i-1]-b)
    res.append(result)
print(min(res))

Submission status: Accepted

Solution code:
N = int(input())
AS = input().split()
AS = [int(i) for i in AS]
BS = [int(AS[j-1] - j) for j in range(1,N+1)]
BS_s = BS.sort()
b = BS[N//2]
result_a = 0
result_b = 0
result_c = 0
for j in range (1, N+1):
    result_a += abs(int(AS[j-1]) - b - j)
for j in range (1, N+1):
    result_b += abs(int(AS[j-1]) - b - 1 - j)
for j in range (1, N+1):
    result_c += abs(int(AS[j-1]) - b + 1 - j)
print (int(min(result_a,result_b,result_c)))

Submission status: Accepted

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

npA = np.array(A)
npi = np.arange(1,N+1)
diff = npA - npi
diff = np.sort(diff)

if N%2 == 0:
    bi = int(N / 2 - 1)
    b = (diff[bi] + diff[bi+1])//2
else:
    bi = int((N-1) / 2)
    b = diff[bi]
tmp = diff - b
ans = np.sum(abs(tmp))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
d = []
for i in range(n):
    d.append(a[i]- (i+1))
import statistics as s
b = s.median(d)
c = 0
for i in range(n):
    c += abs(d[i] - b)
print(int(c))

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
A=np.array(list(map(int,input().split(' '))))
A=A-np.arange(N)
Amed=np.int(np.median(A))
err=[]
for b in (Amed,Amed+1):
    err.append(np.sum(np.abs(A-b)))
print(min(err))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import statistics

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

S1=[]
for i in range(N):
    S1.append(S[i]-i)
S1.sort()
chuouchi=statistics.median_high(S1)
chuouchi2=statistics.median_low(S1)
chuouchi3=statistics.median(S1)
ans=10**20
ansj=0
A=chuouchi-4
B=chuouchi+4
C=chuouchi2-4
D=chuouchi2+4
E=int(chuouchi3)-4
F=int(chuouchi3)+4
for i in range(A,B):
    goukei=0
    for j in range(N):
        goukei+=abs(S[j]-(i+j+1))
        
    if ans>goukei:
        ans=goukei
        
for i in range(C,D):
    goukei=0
    for j in range(N):
        goukei+=abs(S[j]-(i+j+1))
        
    if ans>goukei:
        ans=goukei

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

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    factors = [ factor-k for factor,k in zip(a, range(1,n+1)) ]
    factors.sort()
    index = (n//2)
    ans = sum([ abs(factor-factors[index]) for factor in factors ])
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from statistics import median
N = int(input())
A = list(map(lambda x:int(x),input().split(" ")))
npA = np.array(A)
B = npA-(1+np.arange(len(npA)))
opt_b = median(B)
print(int(np.sum(np.abs(B-opt_b))))

Submission status: Accepted

Solution code:
from collections import Counter

def mapdict(n, dictionary):
    return dict(map(lambda t:(t[0]-n,t[1]), dictionary.items()))

def count(dic):
    count = 0
    for k,v in dic.items():
        count += abs(k*v)
    return count

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

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


Adic = Counter(A2)
Ax  = A2[N//2]
Adic = mapdict(Ax, Adic)

res = count(Adic)

if N==1:
    print(0)

elif N==2:
    print(sum(map(abs,map(lambda x:x-min(A2),A2))))

else:
    pl = count(mapdict(A2[N//2 +1],Adic))
    mn = count(mapdict(A2[N//2 -1],Adic))
    if pl<=res:
        tmp = pl
        tmpc = 1
        while tmp <= res:
            tmpc += 1
            if N//2 + tmpc > N-1:
                break
            res = tmp
            Adic = mapdict(A2[N//2 +tmpc], Adic)
            tmp = count(Adic)
    elif mn<=res:
        tmp = mn
        tmpc = 1
        while tmp <= res:
            tmpc += 1
            if N//2 - tmpc < 0:
                break
            res = tmp
            Adic = mapdict(A2[N//2 -tmpc], Adic)
            tmp = count(Adic)

    print(res)

Submission status: Accepted

Solution code:
import math

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

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

ns.sort()

if len(ns) % 2 != 0:
    ind  = math.ceil(len(ns)/2)
    m = ns[ind-1]
    m1 = 0
else:
    ind = int(len(ns)/2)
    m = math.floor((ns[ind-1]+ns[ind])/2)
    m1 = m + 1


ls = 0
hs = 0

for na in ns:
    ls += abs(na-m)
    hs += abs(na-m)


print(min(ls, hs))

Submission status: Accepted

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

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

# ave1=sum(A)//len(A)
# ave2=-(-sum(A)//len(A))
# median=Counter(A).most_common(1)[0][0]

B=A[:]
C=A[:]

B.sort()
# 偶数の場合
if N % 2 == 0:
    median1 = N/2
    median2 = N/2 + 1
    median1 = int(median1) - 1
    median2 = int(median2) - 1
    median = (B[median1] + B[median2]) / 2

    # 奇数の場合
else:
    median = (N + 1) / 2
    median = int(median) - 1
    median = B[median]

median=int(median)

for i in range(0,N):
    C[i]-=median
    C[i]=abs(C[i])

print(sum(C))

Submission status: Accepted

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

if N==1:
    print(0)
else:
    B = [A[i]-i for i in range(N)]
    B.sort()
    b_pl = B[N//2]
    b_mn = B[N//2-1]
    
    sadness_pl = sum([abs(B[i]-b_pl) for i in range(N)])
    sadness_mn = sum([abs(B[i]-b_mn) for i in range(N)])
    
    print(min(sadness_pl, sadness_mn))

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))
sad = 0
for i in A:
    sad += abs(i - b)
print(sad)

Submission status: Accepted

Solution code:
def getScore(xs, b):
    return sum(abs(x - b) for x in xs)

def solve(xs, n):
    xs = sorted([x - i for (x, i) in zip(xs, range(1, n + 1))])
    if n % 2 == 0:
        return getScore(xs, xs[n // 2])
    return min(getScore(xs, xs[n // 2 - 1]), getScore(xs, xs[n // 2]))

if __name__ == "__main__":
    n = int(input())
    xs = [int(s) for s in input().split()]
    print(solve(xs, n))

Submission status: Accepted

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

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

a = [a - (i+1) for i,a in enumerate(A)]
b = int(median(a))
print(k(A,b))

Submission status: Accepted

Solution code:
from pprint import pprint
from statistics import median

N = int(input())
As = list(map(int, input().split(" ")))

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

# pprint(As)

b = int(median(As))

ans = 0

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

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

sub_num = []

for i in range(1, n+1):
#    print(abs(int(a[i-1]-i)))
    sub_num.append(int(a[i-1]-i))


b = np.median(sub_num)
#print(b)

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

print(int(result))

Submission status: Accepted

Solution code:
import math
import statistics

n = int(input())
a = [int(x) for x in input().split()]
a2 = [0] * n
for i in range(n):
    a2[i] = a[i] - (i+1)
median = int(statistics.median(a2))
for i in range(n):
    a2[i] = abs(a2[i]-median)
print(sum(a2))

Submission status: Accepted

Solution code:
import statistics

N = int(input())
A = input().split()
A = list(map(int,A))
sa = 0
sa_list = []

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

sa_list.sort()
if(len(sa_list)%2 != 0):
	b = statistics.median(sa_list)
	sum_As = 0
	for p in range(1,len(A)+1):
		sum_As += abs(A[p-1]-(b+p))
	print(sum_As)
else:
	b = statistics.median_low(sa_list)
	sum_As = 0
	for p in range(1,len(A)+1):
		sum_As += abs(A[p-1]-(b+p))
	
	b2 = statistics.median_high(sa_list)
	sum_As2 = 0
	for p in range(1,len(A)+1):
		sum_As2 += abs(A[p-1]-(b2+p))
	
	print(max(sum_As,sum_As2))

Submission status: Accepted

Solution code:
from statistics import median

# 整数の入力
N = int(input())
l = list(map(int, input().split(" ")))
l_ = [num - i - 1 for i, num in enumerate(l)]
l_ = sorted(l_)

b = median(l_)

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

Submission status: Accepted

Solution code:
import numpy as np

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

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

b = int(np.median(A))
ans = float('inf')
for j in [0, 1]:
    v = 0
    for i in range(N):
        v += abs(A[i] - (b + j))
    ans = min(ans, v)
print(ans)

Submission status: Accepted

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


import statistics
import math
def kanashimi(b):
    
    out = 0
    for i in range(N):
        out = out + abs(A[i]-(b+(i+1)))
    return out 
  
B = [A[i]-(i+1) for i in range(N)]
b = statistics.median(B)

print(int(kanashimi(b)))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split()))) - np.arange(1,N+1)
print(int(np.sum(np.abs(A - np.median(A)))))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().rstrip().split()))
B=list(A[i]-i for i in range(N))
C=list(A[i]-i for i in range(N))
C.sort()
work=C[N//2]
testA=sum(abs(B[i]-work) for i in range(N))
testB=sum(abs(B[i]-work-1) for i in range(N))
testC=sum(abs(B[i]-work+1) for i in range(N))
output=min(testA,testB,testC)
print(output)

Submission status: Accepted

Solution code:
from statistics import median
import math
N = int(input())
*A, = map(int, input().split())
B = [A[i]-i for i in range(N)]
b = median(B)
bm = math.floor(b)
bM = math.ceil(b)
Bm = [abs(x - bm) for x in B]
BM = [abs(x - bM) for x in B]
m = sum(Bm)
M = sum(BM)
print(int(min([m,M])))

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

Submission status: Accepted

Solution code:
import math

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, = read_line(int)

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

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

AA.sort()

if len(AA) % 2 == 0:
    b = int(len(AA) / 2 - 1)
else:
    b = int((len(AA) - 1) / 2)

sadness = 0
for i, a in enumerate(A):
    # sadness1 += abs(a - (i + b1 + 1))
    # sadness2 += abs(a - (i + b2 + 1))
    sadness += abs(a - (i + AA[b] + 1))

print(sadness)

Submission status: Accepted

Solution code:
import statistics

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

Ai_i = [0 for i in range(len(A))]

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

bs = [int(statistics.median(Ai_i))]
abss_ls = [ 0 for i in range(len(bs)) ]

for i in range(len(bs)):
    for j in range(len(Ai_i)):
        abss_ls[i] += abs(Ai_i[j] - bs[i])

min_abs = min(abss_ls)
print(min_abs)

Submission status: Accepted

Solution code:
from math import ceil, floor
import statistics

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

Ai_i = [0 for i in range(len(A))]

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

n = 5

b_ceil = ceil(sum(Ai_i) / len(Ai_i))

bs = list(range(b_ceil-n, b_ceil+n))

bs = [int(statistics.median(Ai_i))]
abss_ls = [ 0 for i in range(len(bs)) ]
for i in range(len(bs)):
    for j in range(len(Ai_i)):
        abss_ls[i] += abs(Ai_i[j] - bs[i])

min_abs = min(abss_ls)
print(min_abs)

Submission status: Accepted

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

import numpy as np
import collections

A = np.array(A)
I = np.array(list(range(1, N + 1)))

G = A - I

b = np.median(G)
G = np.absolute(G - np.full(N, b))
re = np.sum(G)

print(int(re))

Submission status: Accepted

Solution code:
import numpy as np
import statistics

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

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

# print(A)
# print(A_minus_i)

bf = statistics.median(A_minus_i)
# print(bf)

# b_l = int(bf)+1
# b_m = int(bf)
# b_s = int(bf)-1
#
# score_l = sum([abs(a - b_l) for a in A_minus_i])
# score_m = sum([abs(a - b_m) for a in A_minus_i])
# score_s = sum([abs(a - b_s) for a in A_minus_i])

score = sum([abs(a - bf) for a in A_minus_i])

print(int(score))

Submission status: Accepted

Solution code:
n=int(input())
a=map(int,input().split())
import statistics
t=1
b=10**15
c=-(10**15)
d=[]
for i in a:
    e=i-t
    d.append(e)
    t+=1
i=int(statistics.median(d))
k=0
for j in d:
    k+=abs(j-i)
print(k)

Submission status: Accepted

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

def sad(b):
    return int(np.sum(np.abs(A - b)))

l = -1e10
r =  5e10
m = 2e30
tmp = 5e30
tmp2 = 1e30
while tmp2 != sad(m):
    if tmp > sad(m):
        tmp = sad(m)
    tmp2 = sad(m)
    m = (l + r) // 2
    if sad(m) - sad(m+1) >= 0:
        l = m
    else:
        r = m

print(tmp)

Submission status: Accepted

Solution code:
N = int(raw_input())
A = map(int, raw_input().split())
R = [A[i]-(i+1) for i in range(N)]
R.sort()
b1 = sum(R)/N
b2 = sum(R)/N+1
b3 = R[N/2]
print min(sum([abs(b1-r) for r in R]), sum([abs(b2-r) for r in R]), sum([abs(b3-r) for r in R]))

Submission status: Accepted

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

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

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

A.sort()

if len(A) % 2 == 0:
    bi = int(N / 2 - 1)
else:
    bi = int((N - 1) / 2)

#print("A:{}".format(A))
#print("bi:{}".format(bi))
#print("A[bi]:{}".format(A[bi]))

print(sum(map(lambda x: abs(x - A[bi]), A)))

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    input_raw = read_func().strip().split()
    A_i = []
    for i in range(N):
        A_i.append(long(input_raw[i]) - i)


    ave_A = (sum(A_i)/N)
    A_i.sort()
    
    b1 = (ave_A)
    b2 = ave_A + 1
    b3 = A_i[N/2]
    b4 = b3
    b5 = -b1
    b6 = -b2
    score1 = 0L
    score2 = 0L
    score3 = 0L
    score4 = 0L
    score5 = 0L
    score6 = 0L
    for i in range(N):
        score1 += abs(b1 - A_i[i])
        score2 += abs(b2 - A_i[i])
        score3 += abs(b3 - A_i[i])
        score4 += abs(b4 - A_i[i])
        score5 += abs(b5 - A_i[i])
        score6 += abs(b6 - A_i[i])

    print min(score1, score2, score3, score4,score5,score6)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#c

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

for i in range(1,n+1):
    a[i-1] -= i
a.sort()
num0 = 0
num1 = a[int(n/2)-1]
num2 = a[int(n/2)]
num3 = int((num1 + num2)/2)
num4 = num3 - 1
num5 = num3 + 1
num6 = num1 + 1
num7 = num1 - 1
num8 = num2 + 1
num9 = num2 - 1

ans0 = 0
for i in range(n):
    ans0 += abs(a[i]-num0)
ans1 = 0
for i in range(n):
    ans1 += abs(a[i]-num1)
ans2 = 0
for i in range(n):
    ans2 += abs(a[i]-num2)
ans3 = 0
for i in range(n):
    ans3 += abs(a[i]-num3)
ans4 = 0
for i in range(n):
    ans4 += abs(a[i]-num4)
ans5 = 0
for i in range(n):
    ans5 += abs(a[i]-num5)
ans6 = 0
for i in range(n):
    ans6 += abs(a[i]-num6)
ans7 = 0
for i in range(n):
    ans7 += abs(a[i]-num7)
ans8 = 0
for i in range(n):
    ans8 += abs(a[i]-num8)
ans9 = 0
for i in range(n):
    ans9 += abs(a[i]-num9)

ans = min(ans0,ans1)
ans = min(ans,ans2)
ans = min(ans,ans3)
ans = min(ans,ans4)
ans = min(ans,ans5)
ans = min(ans,ans6)
ans = min(ans,ans7)
ans = min(ans,ans8)
ans = min(ans,ans9)
print(ans)

Submission status: Accepted

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

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

c.sort()
ave = c[n//2]


ans = 10**9*n

for b in range(ave-100, ave+100):
    t = 0
    for i in range(n):
        t += abs(c[i]-b)
    ans = min(ans, t)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input().strip())
A=list(map(int, input().strip().split()))
A_posi=[]
A_nega=[]
for i in range(N):
    A[i]=A[i]-(i+1)
    if A[i]<0:
        A_nega.append(A[i]*(-1))
    elif A[i]>0:
        A_posi.append(A[i])
sm=sum(abs(i) for i in A)

A_tgt=A_nega if len(A_nega)>len(A_posi) else A_posi
A_tgt=sorted(A_tgt)

diff=0
old=0
mindiff=0
for i,a in enumerate(A_tgt):
    if old<a:
        diffdiff=(-i+(len(A_tgt)-i))*(a-old)
    else:
        continue
    if diffdiff<0:
        break
    old=a
    diff = diff+diffdiff
    total_diff=-diff+a*(N-len(A_tgt))
    if total_diff<mindiff:
        mindiff=total_diff
print(sm+mindiff)

Submission status: Accepted

Solution code:
import statistics
N = int(input())
a = list(map(int, input().rstrip().split()))
a_ = [x-i for i, x in enumerate(a, 1)]
b = round(statistics.median(a_))
S = 0
for i in a_:
    S += abs(i-b)
print(S)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from statistics import median
input()
*a,=[ai-i-1 for i,ai in enumerate(map(int,input().split()))]
n=int(median(a))
m=n+1
print(min(sum([abs(ai-n) for ai in a]),sum([abs(ai-m) for ai in a])))

Submission status: Accepted

Solution code:
import statistics
import math

N = int(input())
A = list(map(int, input().split(" ")))
A_i = [0]*N
K_1 = 0
K_2 = 0
K_3 = 0


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

try:
    b_1 = statistics.mode(A_i)
except:
    b_1 = int(statistics.mean(A_i))

b_2= int(statistics.mean(A_i))
b_3 = int(statistics.median(A_i))

for i in range(N):
    K_1 = K_1 + abs(A_i[i] - b_1)
    K_2 = K_2 + abs(A_i[i] - b_2)
    K_3 = K_3 + abs(A_i[i] - b_3)

print(min(K_1, K_2, K_3))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import ceil, floor

N = int(input())
A = [int(t) for t in input().split()]
if len(A) != N: raise

p = [A[i-1] - i for i in range(1, N+1)]
p.sort()

q = []
for b in p[N//2 - 1 : N//2 + 2]:
    q.append(sum(abs(x - b) for x in p))
print(min(q))

Submission status: Accepted

Solution code:
import statistics

N = int(input())

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

sum_r2 = 0
median = statistics.median(A)
for i in range(N):
    sum_r2 += abs(A[i] - (median))

print(int(sum_r2))

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
a = list(map(int,input().split()))
b = []
cnt = 1
for num in a:
    num -= cnt
    b.append(num)
    cnt += 1
test = [int(np.mean(b))-1,int(np.mean(b)),int(np.mean(b))+1,int(np.median(b))]
test = list(set(test))
ans = []
s = 9999999999999
for i in test:
    cnt = 1
    c = []
    for num in a:
        st = 0
        st = abs(num - (i+cnt))
        c.append(st)
        cnt += 1
    ans.append(np.sum(c))
print(np.min(ans))

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()
start_index = math.floor(N / 2)

min_sum = 10 ** 9 * 2 * 10 ** 5
for i in range(A[start_index], A[start_index] + 1):
    summ = 0
    for j in range(N):
        summ += abs(A[j] - i)
    min_sum = min(min_sum, summ)
print(min_sum)

Submission status: Accepted

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, b + 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: Accepted

Solution code:
import numpy as np

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

A = np.array(A)
B = np.array(range(1, len(A) + 1))
AminusB = A - B
median = np.median(AminusB)
print(int(sum(abs(AminusB - median))))

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
S = np.array(list(map(int, input().split())))
I = np.arange(1, N + 1, 1)

D = np.sort(S - I)
print(np.sum(np.abs(D - D[N//2])))

Submission status: Accepted

Solution code:
# coding=utf-8

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    A_modify = [A[j] - j - 1 for j in range(N)]
    A_modify.sort()

    mid1 = A_modify[N//2]
    A_modify1 = [abs(elm - mid1) for elm in A_modify]
    print(sum(A_modify1))

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 = sorted(a)
#print(a)
pivot = a[int(n / 2)]
#print(pivot)

count = 0
for i in range(int(n / 2)):
    count -= a[i]

for i in range(int(n / 2), n):
    count += a[i]

if n % 2 == 0:
    print(count)
else:
    print(abs(count - pivot))

Submission status: Accepted

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

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

p_num.sort()
n_num.sort()
n_num.reverse()

if len(p_num) > len(n_num) + len(z_num):
    count_n = len(n_num) + len(z_num)
    count_p = len(p_num)
    index = -1
    while  count_p > count_n:
        count_p -= 1
        count_n += 1
        index += 1
    for i in range(len(b)):
        b[i] = b[i] - p_num[index]

elif len(n_num) > len(p_num) + len(z_num):
    count_n = len(n_num)
    count_p = len(p_num) + len(z_num)
    index = -1
    while  count_n > count_p:
        count_n -= 1
        count_p += 1
        index += 1
    for i in range(len(b)):
        b[i] = b[i] - n_num[index]

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

print(ans)

Submission status: Accepted

Solution code:
import math
import statistics

n = int(input())
a = [int(i) for i in input().split()]
for i in range(n):
    a[i] -= i
mc = math.ceil(statistics.median(a))
mf = math.floor(statistics.median(a))
ac = [0 for i in range(n)]
af = [0 for i in range(n)]
for i in range(n):
    ac[i] = abs(a[i]- mc)
    af[i] = abs(a[i]- mf)

print(min([sum(ac),sum(af)]))

Submission status: Accepted

Solution code:
import statistics
import math

N = int(input())

A = list(map(int, input().split()))
A = [A[i] - i for i in range(N)]
med = round(statistics.median(A))

s0 = sum([abs(A[i] - med) for i in range(N)])
s1 = sum([abs(A[i] - med -1) for i in range(N)])
s2 = sum([abs(A[i] - med + 1) for i in range(N)])

print(min(s0, s1, s2))

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()
kanasisa=0
for i in range(1+(n-1)//2):
  kanasisa+=a[n-1-i]-a[i]
print(kanasisa)

Submission status: Accepted

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

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

    dif.sort()
    if n % 2 == 0:
        med = (dif[n//2-1]+dif[n//2]) // 2
        med2 = med + 1
    else:
        med = med2 = dif[n//2]

    dm1, dm2 = 0, 0
    for i in range(n):
        dm1 += abs(dif[i]-med)
        dm2 += abs(dif[i]-med2)

    print(min(dm1, dm2))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
lst = [int(x) for x in input().split()]
a = 0
for i in range(n):
    lst[i] = lst[i] - (i + 1)
lst.sort()
def sum(k):
    a = 0
    for i in range(n):
        a += abs(lst[i]-k)
    return a
ans = 0
if ans % 2 == 0:
    ans = min([sum(lst[int(n/2)-1]),sum(lst[int(n/2)])])
else:
    ans = sum(lst[int(n/2)])
print(str(ans))

Submission status: Accepted

Solution code:
import numpy as np
def _unique1d(ar, return_index=False, return_inverse=False,
              return_counts=False):
    """
    Find the unique elements of an array, ignoring shape.
    """
    ar = np.asanyarray(ar).flatten()

    optional_indices = return_index or return_inverse
    optional_returns = optional_indices or return_counts

    if ar.size == 0:
        if not optional_returns:
            ret = ar
        else:
            ret = (ar,)
            if return_index:
                ret += (np.empty(0, np.intp),)
            if return_inverse:
                ret += (np.empty(0, np.intp),)
            if return_counts:
                ret += (np.empty(0, np.intp),)
        return ret

    if optional_indices:
        perm = ar.argsort(kind='mergesort' if return_index else 'quicksort')
        aux = ar[perm]
    else:
        ar.sort()
        aux = ar
    flag = np.concatenate(([True], aux[1:] != aux[:-1]))

    if not optional_returns:
        ret = aux[flag]
    else:
        ret = (aux[flag],)
        if return_index:
            ret += (perm[flag],)
        if return_inverse:
            iflag = np.cumsum(flag) - 1
            inv_idx = np.empty(ar.shape, dtype=np.intp)
            inv_idx[perm] = iflag
            ret += (inv_idx,)
        if return_counts:
            idx = np.concatenate(np.nonzero(flag) + ([ar.size],))
            ret += (np.diff(idx),)
    return ret
N = int(input())
A = np.array(list(map(int, input().split())), dtype= int)
I = np.arange(1, N+1)
C = A - I
mincost = -1
P, M = _unique1d(C, return_counts=True)
n = -N
for p , m in zip(P, M):
    n1 = n + 2*m
    if n*n1<=0:
        b = p
        break
    n = n1
cost = np.abs(C - b).sum()
print(cost)

Submission status: Accepted

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

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

B.sort()

Left=0
Right=sum(B)-B[0]*N
ANS=Left+Right
#print(B)
#print(Left,Right)

for i in range(1,N):
    Left=Left+(B[i]-B[i-1])*i
    Right=Right-(B[i]-B[i-1])*(N-i)
    #print(Left,Right)

    if ANS>Left+Right:
        ANS=Left+Right

print(ANS)

Submission status: Accepted

Solution code:
import statistics
n = int(input())
a = list(map(int, input().split()))
a = [a[i]-(i+1) for i in range(n)]
# print(a)
med = statistics.median_low(a)
ans = 0
for i in range(len(a)):
    ans += abs(a[i] - med)
print(ans)