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 sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

import numpy as np
from numba import i8, njit

#AOTにするとさらに早くなる?
@njit(i8(i8, i8[:]), cache=True)
def binary_search(n, a):
    right = np.max(a) + 10 ** 9
    left = np.min(a) - 10 ** 9

    def calc(b):
        score = 0
        for i in range(n):
            score += abs(a[i] - (b + i + 1))
        return score

    while right - left > 1:
        middle = (right + left) // 2
        if calc(middle) < calc(middle+1):
            right = middle
        else:
            left = middle
    
    return calc(right)

def Main():
    n = read_int()
    a = np.array(read_int_list(), dtype=np.int64)
    
    print(binary_search(n, a))

if __name__ ==  '__main__':
    Main()

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

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

Submission status: Accepted

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

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

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

ans=0
for x in aa:
    ans+=abs(x-b)

print(ans)

Submission status: Accepted

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

li = sorted([a[i]-(i+1) for i in range(n)])
if n%2==0:
    ave = (li[n//2]+li[n//2-1])//2
else:
    ave = li[(n-1)//2]

import math
ave1 = math.floor(ave)
ave2 = math.ceil(ave)

ll = []
c = 0
for i in range(n):
    c += abs(a[i]-(ave1+i+1))
else:
    ll += [c]

c =0
for i in range(n):
    c += abs(a[i]-(ave2+i+1))
else:
    ll += [c]

print(min(ll))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, *a = map(int, read().split())

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

a.sort()

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

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

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

m1 = b[n//2]
s1 = sum([abs(b[i] - m1) for i in range(n)])

if n % 2 == 1:
    m1 = b[n//2]
    s1 = sum([abs(b[i] - m1) for i in range(n)])
    print(s1)
else:
    m1 = b[n//2-1]
    m2 = b[n//2]
    if (m1 + m2) % 2 == 0:
        l1 = (m1 + m2) // 2
        s1 = sum([abs(b[i] - l1) for i in range(n)])
        print(s1)
    else:
        l1 = (m1 + m2) // 2
        l2 = l1 + 1
        s1 = sum([abs(b[i] - l1) for i in range(n)])
        s2 = sum([abs(b[i] - l2) for i in range(n)]) 

        print(min(s1, s2))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
ahu=[]
asei=[]
hu=0
ans=0
for i in range(1,n+1):
  if a[i-1]-i<0:
    hu+=1
    ahu.append(abs(a[i-1]-i))
  else:
    asei.append(a[i-1]-i)
  ans+=abs(a[i-1]-i)  
sei=n-hu
asei.sort()
ahu.sort()
#print(ahu)
#print(asei)
#print(ans)
rui=0
if sei<hu:
  for i in range((hu-sei)//2+1):
    ans-=(hu-sei-2*i)*(ahu[i]-rui)
    rui=ahu[i]
  print(ans)
elif sei>hu:
  for i in range((sei-hu)//2+1):
    ans-=(sei-hu-2*i)*(asei[i]-rui)
    rui=asei[i]
  print(ans)
else:
  print(ans)

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 = sorted(b)

if n % 2 == 1:
  res = b[(n-1)//2]
else:
  res = (b[n//2-1] + b[n//2])//2
  
print(sum(map(abs, [b[i]-res for i in range(n)])))

Submission status: Accepted

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

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

pin=b[n//2]

ans=0

for i in b:
  ans+=abs(pin-i)
  

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = [a - i - 1 for i, a in enumerate(list(map(lambda x: int(x), input().split(" "))))]
A.sort()
 
ini = int(N/2)
m_abs = ""
sumlist = 0
for i in range(ini, len(A)):
  tmp = 0
  if i == ini:
    sumlist = - sum(A[:i]) + sum(A[i:])
  else:
    sumlist -= 2 * A[i]
 
  if 2 * i - N > 0:
    tmp = sumlist + (2 * i - N) * A[i - 1]
  else:
    tmp = sumlist + (2 * i - N) * A[i]
  if not m_abs or m_abs > tmp:
    m_abs = tmp
  if m_abs and m_abs <= tmp:
    break
    
print(m_abs)

Submission status: Accepted

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

cnt = 1
for i in range(N):
    A[i] = A[i] - cnt
    cnt += 1
A.sort(reverse=True)
medA = statistics.median(A)

ans = 0
cnt = 1
for j in range(N):
    ans += abs(A[j] - medA)
    cnt += 1

print(int(ans))

Submission status: Accepted

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

a=[a[n]-(n+1) for n in range(N)]
a.sort()
result=sum(a[N//2:N])-sum(a[:N//2]) if N%2==0 else sum(a[N//2+1:N])-sum(a[:N//2])
print(result)

Submission status: Accepted

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

A = [A[i]-(i+1) for i in range(N)]
A.sort()
cumsum = [0]*N
cumsum[0] = A[0]
for i in range(1, N):
    cumsum[i] = cumsum[i-1] + A[i]
ans = 1e20
for i in range(N):
    tmp = -(cumsum[i]) + (cumsum[N-1]-cumsum[i]) + (i+1)*A[i] - (N-i-1)*A[i]
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from statistics import median
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
for i in range(N):
  B[i]=A[i]-i
b=int(median(B))
ans=0
for i in range(N):
  ans+=abs(B[i]-b)
print(ans)

Submission status: Accepted

Solution code:
import sys


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n = ni()
    A = nl()
    A = sorted(list(map(lambda x: A[x] - (x + 1), range(n))))
    b = A[n // 2]
    print(sum(list(map(lambda x: abs(x - b), A))))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
if n==1:print(0);exit()
A=[A[i]-i-1 for i in range(n)]
B=sorted(A)

#print(B)

if n%2==1:
    d=B[n//2]
    print(sum([abs(A[i]-d) for i in range(n)]))
    exit()

ans=0
d=(B[n//2-1]+B[n//2])//2
print(sum([abs(A[i]-d) for i in range(n)]))

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    A = [a - i for i, a in enumerate(A, 1)]
    A.sort()

    b = A[N // 2]
    ans = sum(abs(a - b) for a in A)

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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 = sorted(b)
if n % 2 == 1:
  c = b[(n-1)//2]
else:
  c = round((b[n//2-1] + b[n//2])//2)

print(sum(map(abs,[b[i]-c for i in range(n)])))

Submission status: Accepted

Solution code:
from statistics import median
n = int(input())
a = list(map(int, input().split()))
b = [a[i]-i-1 for i in range(n)]
B = median(b)
ans = 0
for i in range(n):
    ans += abs(b[i]-B)
print(int(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] -= i+1

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

# Nの偶奇に依らず、中央値はこのように表せることが知られている
med = ai[N // 2]

ans = 0
for i in range(N):
    tmp = abs(ai[i] - med)
    ans += tmp
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

al = list(map(int, input().split()))
sl = [i for i in range(n)]

c = [x - y for (x, y) in zip(al,sl)]
cs = sorted(c)

m = n//2
b = cs[m]
ssl = [i+b for i in range(n)]

cc = [x-y for (x,y) in zip(al,ssl)]
res = sum(list(map(lambda x:abs(x),cc)))
print(res)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

a.sort()

b = a[n//2]

ans = 0
for i in a:
    ans += abs(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] = A[i] - i
A.sort()

b = A[N // 2]
answer = 0
for i in range(N):
    answer += abs(A[i] - b)

print(answer)

Submission status: Accepted

Solution code:

from statistics import median

n = int(input())
ar = list(map(int, input().split()))
ans = 0
temp = sorted([ai - i for i, ai in enumerate(ar, 1)])
b = median(temp)

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

print(int(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] - 1 - i
  
#print(B)
B = sorted(B)

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

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

Submission status: Accepted

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

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

arr.sort()

ans = []

s = 0
b = arr[n//2]
for i in range(n):
    s += abs(a[i] - (b + (i+1)))
ans.append(s)

if n == 1:
    print(ans[0])
    exit()
    
s = 0
b = arr[n//2 + 1]
for i in range(n):
    s += abs(a[i] - (b + (i+1)))
ans.append(s)

print(min(ans))

Submission status: Accepted

Solution code:
import statistics
import numpy as np
import math
#-------------
N = int(input())
A = list(map(int, input().split()))
#-------------
 
B = [A[i]-i-1 for i in range(N)]
 
point = statistics.median(B)
point = math.floor(point)
 
ans_list = []
ans = 0
for b in range(point-2 , point+2):
  for i in range(N):
    X = B[i]-b
    ans += np.abs(X)
  ans_list.append(ans)
  ans = 0

min_ans_list = min(ans_list)
print(min_ans_list)

Submission status: Accepted

Solution code:
import statistics

NN = int(input())
AA = list(map(int,input().split()))
BB = [0]*NN
for nn in range(1,NN+1):
    BB[nn-1] = AA[nn-1] - nn
#print(BB)
MBB = statistics.median(BB)

CC = list(map(lambda x: x - MBB, BB))
#print(CC)
ACC = list(map(lambda x: abs(x),CC))
ANS = sum(ACC)
print(int(ANS))

Submission status: Accepted

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

N = int(input())
A = list(map(int, input().split()))
nA = [a-i-1 for i, a in enu(A)]

# print(nA)
nA.sort()
# print(nA)

# minA = min(nA)
# maxA = max(nA)
# for val in range(minA, maxA+1):
#     res = sum([abs(a-val) for a in nA])
#     print(val, ':', res)

midA1 = nA[N//2-1]
midA2 = nA[N//2]
res = min(sum([abs(a-midA1) for a in nA]), sum([abs(a-midA2) for a in nA]))
print(res)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = [int(i)- k-1 for k,i in enumerate(input().split())]
ans = 10**9
a = np.array(a,dtype = 'int64')
median = int(np.median(a))

print(np.sum(np.abs(a-median)))

Submission status: Accepted

Solution code:
import numpy as np

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

diff = A - (np.arange(N) + 1)
diff.sort()

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

print(np.sum(np.abs(diff - median)))

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline


def log(*args):
    print(*args, file=sys.stderr)


def main():
    np.set_printoptions(threshold=20)
    N = int(input())
    l = list(map(int, input().rstrip().split()))
    for i, v in enumerate(l):
        l[i] = v - (i + 1)
    l.sort()
    now = 0
    for v in l:
        now += abs(v - (l[0] - 1))
    right_count = N
    left_count = 0
    ans = now
    before = l[0] - 1
    for v in l:
        now -= right_count * (v - before)
        now += left_count * (v - before)
        right_count -= 1
        left_count += 1
        ans = min(now, ans)
        before = v
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

a_sub_i.sort()

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))
for i in range(N):
    A[i] -= (i+1)
A = sorted(A)
k = N // 2 
b = A[k]
ans = 0
for i in range(N):
    ans += abs(A[i]-b)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import statistics
import math
n = int(input())
a = list(int(x)-i-1 for i,x in enumerate(input().split()))
b = statistics.median(a)
print(math.floor(sum(abs(j-b) for j in a)))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
import numpy as np
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    n = int(readline())
    a = np.array(readline().split(), np.int64)
    a -= np.arange(1, n + 1)
    median = np.median(a).astype(np.int64)

    print(np.abs(a - median).sum())



if __name__ == '__main__':
    main()

Submission status: Accepted

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

    
# print(med)
ans = 0
for i in range(N):
    ans += abs(a[i]-(med))
print(ans)

Submission status: Accepted

Solution code:
import copy

n = int(input())

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

asort = copy.copy(a)
asort.sort()

if n % 2 == 1:
    b = asort[(n//2)]
else:
    b = (asort[(n//2)-1] + asort[(n//2)]) // 2 + (asort[(n//2)-1] + asort[(n//2)]) % 2

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N = I()
A = LI()
for i in range(N):
    A[i] -= i
A.sort()
print(sum(abs(A[i]-A[N//2]) for i in range(N)))

Submission status: Accepted

Solution code:
import statistics
N = int(input())
L = input().split()
A = sorted(int(L[X])-(X+1) for X in range(0,N))
B = int(statistics.median(A))
Disp = sum(abs(A[X]-B) for X in range(0,N))
print(Disp)

Submission status: Accepted

Solution code:
from numpy import *
N = int(input())
A = array(list(map(int,input().split())))
B = array(sorted([A[n]-(n+1) for n in range(N)]))
print(sum(abs(B-int(median(B)))))

Submission status: Accepted

Solution code:
from numpy import *
N = int(input())
A = list(map(int,input().split()))
B = array(sorted([A[n]-(n+1) for n in range(N)]))
print(sum(abs(B-int(median(B)))))

Submission status: Accepted

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
if (n==1):
    print(0)
    exit()
for i in range(n):
    a[i] -= i+1
a.sort()
ans1 = 0
ans2 = 0
x = a[n//2]
y = a[n//2-1]
for i in range(n):
    ans1 += abs(a[i]-x)
    ans2 += abs(a[i]-y)
print(min(ans1,ans2))

Submission status: Accepted

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

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

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

aa = sorted(aa)
b1 = aa[n//2]
b2 = aa[n//2 + 1]
ans = min(
    sum([abs(a - b1) for a in aa]),
    sum([abs(a - b2) for a in aa])
)
print(ans)

Submission status: Accepted

Solution code:

import math
N = int(input())

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


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

ans = []

if N % 2 == 1:
    b = B[N // 2]
    ans.append(sum([abs(x - b) for x in B]))
else:
    b_left = (B[N // 2 - 1] + B[N // 2]) // 2
    b_right = math.ceil((B[N // 2 - 1] + B[N // 2]) / 2)
    ans.append(sum([abs(x - b_left) for x in B]))
    ans.append(sum([abs(x - b_right) for x in B]))

print(min(ans))

Submission status: Accepted

Solution code:
from math import ceil
n = int(input())
arr = list(map(int, input().split()))
B = []
for i in range(n):
    B.append(arr[i] - (i+1))
B.sort()
b1 = B[n//2]
b2 = B[n//2]
if n > 1:
	b2 = B[int(ceil(n/2))]
ans1, ans2 = 0, 0
for i in range(n):
    ans1 += abs(arr[i]-(b1+i+1))
    ans2 += abs(arr[i]-(b2+i+1))
print (min(ans1, ans2))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    a[i]-=(i+1)
# print(a)
a.sort()
# print(a)
s = 0
for i in a:
    s += abs(i)
if abs(a[(n-1)//2]) > abs(a[n//2]):
    t = a[(n-1)//2]
else:
    t = a[n//2]
ans = 0
for i in a:
    ans += abs(i-t)
# print(t)
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()
ans = 0
b = a[n//2]
for i in range(n):
    ans += abs(a[i]-b)
if n%2 == 0:
    ans2 = 0
    b2 = a[n//2 - 1]
    for i in range(n):
        ans2 += abs(a[i]-b2)

if n%2 != 0:
    print(ans)
else:
    print(min(ans,ans2))

Submission status: Accepted

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

for i in range(n):
    lst[i]-=(i+1)
lst.sort()
b=lst[n//2]
ans=0
for i in range(n):
    ans+=abs(b-lst[i])
print(ans)

Submission status: Accepted

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

import math

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

ans = []

if N%2 == 1:
    b = B[N//2]
    ans.append(sum([abs(x - b) for x in B]))
else:
    b_left = (B[N//2 - 1] + B[N//2])//2
    b_right = math.ceil((B[N//2 - 1] + B[N//2])/2)
    ans.append(sum([abs(x - b_left) for x in B]))
    ans.append(sum([abs(x - b_right) for x in B]))

print(min(ans))

Submission status: Accepted

Solution code:
n = int(raw_input())
ais = map(int, raw_input().split()) 
bis = sorted([ai - i - 1 for i,ai in enumerate(ais)])
if len(bis) % 2:
	b = bis[len(bis)/2]
else:
	b = (bis[len(bis)/2 -1] + bis[len(bis)/2]) /2
	

q = 0
for i in range(len(ais)):
	u = i+1
	q += abs(ais[i] - (b+u))
print q

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import numpy as np
import math
import copy
input = sys.stdin.readline
 
N = int(input())
A = np.array(list(map(int,input().split())))
if N ==1:
    ans = 0
else:
    r = np.array(list(range(1,N+1)))
    B = np.array(sorted(A-r))
    ans = float('inf')
    for i in range(max(N//2-1,0),min(N//2+2,N)):
        c = list(map(abs,(B - B[i])))
        ans = min(ans,sum(c))
print(ans)

Submission status: Accepted

Solution code:

from statistics import median

n = input()
a_lst = list(map(int, input().split(" ")))

each_b = []
for (i, a) in enumerate(a_lst):
    each_b.append(a - (i + 1))

good_b = median(each_b)

total = 0
for (i, a) in enumerate(a_lst):
    total += abs(a - (good_b + i + 1))

print(int(total))

Submission status: Accepted

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

l=[]
for i in a:
    l.append(i-count)
    count+=1
import numpy
l=numpy.array(l)
b=numpy.median(l)
ans=0
for i in l:
    ans+=abs(i-b)
print(int(ans))

Submission status: Accepted

Solution code:
import statistics


def solve():
    N = int(input())
    A = list(map(int, input().split()))
    A_i = [A[i] - i - 1 for i in range(N)]
    b = statistics.median_high(A_i)
    print(sum(abs(a - b) for a in A_i))



if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= i + 1
us, vs = 0, sum(a)
uc, vc = 0, n
a.sort()
ans = vs - a[0] * n
for i in range(n):
    us += a[i]
    uc += 1
    vs -= a[i]
    vc -= 1
    b = a[i]
    ans = min(ans, uc * b - us + vs - vc * b)
print(ans)

Submission status: Accepted

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

A_=A.copy()
for n in range(N):
    A_[n] = A_[n]-(n+1)
A_.sort()
# A_s=A_[0]
# A_e=A_[-1]
# A_mean=(A_s+A_e)/2
A_median=A_[int(len(A_)/2)-10:int(len(A_)/2)+10]

def cul_ans(i):
    A_abs_=[]
    for a in A_:
        A_abs_.append(abs(a-i))
    return A_abs_

ans=10**20
for i in A_median:
    if ans>sum(cul_ans(i)):
        ans=sum(cul_ans(i))
print(ans)

Submission status: Accepted

Solution code:
# C - Linear Approximation

N = int(input())
A = list(int(a) for a in input().split())


A_diff = []
b = 0
for i, a in enumerate(A, 1):
    tmp = a - i
    A_diff.append(tmp)

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def solve(N, A):

    def sad(x):
        s = 0
        for i in range(N):
            s += abs(A[i] - (x + i + 1))
        return s

    min_n = np.min(A) - 10**9
    max_n = np.max(A) + 10**9

    while max_n - min_n != 1:
        tn = (min_n + max_n) // 2
        if sad(tn) < sad(tn + 1):
            max_n = tn
        else:
            min_n = tn

    return sad(max_n)


def main():

    N = in_n()
    A = np.array(readline().split(), np.int64)

    print(solve(N, A))


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', '(i8,i8[:],)')(solve)
    cc.compile()


if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    from my_module import solve
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


@njit('(i8,i8[:],i8,)', cache=True)
def sad(N, A, x):
    s = 0
    for i in range(N):
        s += abs(A[i] - (x + i + 1))
    return s


@njit('(i8,i8[:],)', cache=True)
def solve(N, A):

    min_n = np.min(A) - 10**9
    max_n = np.max(A) + 10**9

    while max_n - min_n != 1:
        tn = (min_n + max_n) // 2
        if sad(N, A, tn) < sad(N, A, tn + 1):
            max_n = tn
        else:
            min_n = tn

    return max_n


def main():

    N = in_n()
    A = np.array(readline().split(), np.int64)

    b = solve(N, A)
    print(sad(N, A, b))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():

    N = in_n()
    A = in_nl()

    def sad(x):
        s = 0
        for i in range(N):
            s += abs(A[i] - (x + i + 1))
        return s

    def binary_search(min_n, max_n):

        while max_n - min_n != 1:
            tn = (min_n + max_n) // 2
            if sad(tn) < sad(tn + 1):
                max_n = tn
            else:
                min_n = tn

        return max_n

    b = binary_search(min(A) - 10**9, max(A) + 10**9)
    print(sad(b))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def solve():
    B = [0]*N
    for i in range(N):
        B[i] = a[i] - (i+1)
    B.sort()
    b = B[N//2]
#    print(b)
    scr = 0
    for l in range(N):
        scr += abs(B[l] - b)
    print(scr)

if __name__ == "__main__":
    N = int(input())
    a = list(map(int, input().split()))  
    solve()

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

Submission status: Accepted

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

res = 0
for v in b:
    res += abs(v - median)
print(res)

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))
#print(B)
b= (sorted(B)[N//2])
#print(b)
ans = 0
for i in range(N):
    ans += abs(B[i]-b)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def main():
    N = ii()
    A = list(mi())
    for i in range(N):
        A[i] -= i+1
    median = sorted(A)[N//2]
    print(sum(abs(A[i]-median) for i in range(N)))


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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a_list = list(map(int,input().split()))
ans_list = []
for i in range(len(a_list)):
    ans_list.append(a_list[i] - i - 1)
import numpy as np
if len(ans_list)% 2 == 0:
    ans_list1 = sorted(ans_list)
    number1 = ans_list1[n//2]
    number2 = ans_list1[n//2 + 1]
    
    ans1 = 0
    ans2 = 0
    for i in ans_list:
        ans1 += abs(i - number1)
        ans2 += abs(i - number2)
    print(min(ans1 , ans2))
else:
    cary = ans_list
    number = int(np.median(cary))
    ans = 0
    for i in ans_list:
        ans += abs(i - number)
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split(' '))))
i = np.arange(1, N + 1)

b = int(np.median(sorted(A - i)))

print(np.sum(np.abs(A - (i + b))))

Submission status: Accepted

Solution code:
from functools import lru_cache
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split(' '))))
i = np.arange(1, N + 1)

right = 10 ** 10
left = -1 * right


@lru_cache(maxsize=None)
def cost(b):
    return np.sum(np.abs(A - (i + b)))


while True:
    mid = (left + right) // 2
    c_left = cost(left)
    c_right = cost(right)
    if left == mid or right == mid:
        print(min(c_left, c_right))
        break
    elif c_left < c_right:
        right = mid
    else:
        left = mid