Problem:


Score : 300 points

Problem Statement

Snuke has an integer sequence A of length N.

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

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

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

Find the minimum possible sadness of Snuke.

Constraints

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

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the minimum possible sadness of Snuke.

Sample Input 1

5
2 2 3 5 5

Sample Output 1

2

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

Sample Input 2

9
1 2 3 4 5 6 7 8 9

Sample Output 2

0

Sample Input 3

6
6 5 4 3 2 1

Sample Output 3

18

Sample Input 4

7
1 1 1 1 2 3 4

Sample Output 4

6



Sample input:
5
2 2 3 5 5


Sample output:
2

Submission status: Accepted

Solution code:
from 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)

left = -(10 ** 10)
right = (10 ** 10)


@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

Submission status: Accepted

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

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

a.sort()
b = a[0 - -n//2 - 1]

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

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:
import statistics
N = int(input())
A = [int(a)-i-1 for i,a in enumerate(input().split(),1)]
b = statistics.median_low(A)
c = statistics.median_high(A)
d = sum(map(lambda x:abs(x-b),A))
e = sum(map(lambda x:abs(x-c),A))
print(min(d,e))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


def zz():
    return list(map(int, input().split()))


def z():
    return int(input())


def S():
    return input()


def C(line):
    return [input() for _ in range(line)]


N = z()
A = zz()


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


for i in range(N):
    A[i] -= (i+1)
A = sorted(A)
# print(A)
if(N % 2 == 0):
    b = (A[N//2] + A[N//2 - 1])//2
else:
    b = A[N//2]
# print(b)

print(get_sadness(A, b))

Submission status: Accepted

Solution code:
import sys
from itertools import combinations
def input(): return sys.stdin.readline().strip()


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
m=sorted([a-i for i,a in enumerate(l, start=1)])
b1,b2=m[n//2],m[n//2-1]
print(min(sum([abs(a-b1) for a in m]),sum([abs(a-b2) for a in m])))

Submission status: Accepted

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

tmp = sorted([v-i for i, v in enumerate(nums, 1)])

b = tmp[len(tmp)//2]

ans = sum([abs(v-(b+i)) for i, v in enumerate(nums, 1)])
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
#n,m=map(int,input().split())
#t=int(input())
al=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

difl=[al[i-1]-i for i in range(1,n+1)]

def sadness(b):
    res=0
    for dif in difl:
        res+=abs(dif-b)
    return res
difsort=sorted(difl)
if n%2==0:
    ind1=n//2
    ind2=n//2-1
    ans=min(sadness(difsort[ind1]),sadness(difsort[ind2]))
else:
    ind=n//2
    ans=sadness(difsort[ind])
print(ans)

Submission status: Accepted

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

blist = []

for i in range(N):
    blist.append(alist[i]-i-1)

blist.sort()
mid = blist[N//2]

print(sum([abs(b-mid) for b in blist]))

Submission status: Accepted

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

blist = []
for i in range(N):
    blist.append(alist[i]-i-1)

blist.sort()
mid = blist[len(blist)//2]

ans = 0

for i in range(N):
    ans += abs(blist[i]-mid)

print(ans)

Submission status: Accepted

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

Bs = []

for i in range(N):
    Bs.append(As[i]-i-1)

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

ans = 0

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

print(ans)

Submission status: Accepted

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

new_al = []
for i,a in enumerate(al):
    new_al.append(a-i-1)

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

ans = 0
for a in new_al:
    ans += abs(a-med)

print(int(ans))

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)
b = int(np.median(a))
print(int(np.sum(np.abs(a - b))))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
l = [a[i]-i-1 for i in range(n)] # ai - iのリスト
b = sorted(l)[n//2] # bは中央値になる
ans = 0
for i in range(n):
    ans += abs(l[i]-b)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))
    A = sorted([a - (i + 1) for i, a in enumerate(A)])
    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=[(int(num)-i,i) for i,num in enumerate(input().split(),1)]
b=(sorted(A)[N//2][0])
ans=0
for i in range(N):
    ans += abs(b-A[i][0])
print(ans)

Submission status: Accepted

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

A.sort()
b = int(statistics.median(A))
sad = sum(abs(A[i-1]-b) for i in range(1,n+1))
print(sad)

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:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
A = LIST()

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

print(sum([abs(x - A[len(A)//2]) for x in A]))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
A = LIST()

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

b = a[len(a)//2]

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

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
a = np.array([int(i) for i in input().split()])
b = np.arange(1,n+1, dtype=int)
a -= b 
a -= int(np.median(a))
print(sum(np.abs(a)))

Submission status: Accepted

Solution code:
import numpy
s = list(map(int, input().split()))
n=s[0]
s = list(map(int, input().split()))
for i in range(n):
    s[i]=s[i]-i-1
s=numpy.array(s)
i=numpy.median(s)
a=numpy.sum(numpy.abs(s-i))
print(int(a))

Submission status: Accepted

Solution code:
import statistics
N = int(input())
*A, = map(int, input().split())
B = [a - (i+1) for i, a in enumerate(A)]
B.sort()
# b = statistics.median(B)
b = B[len(B) // 2]
ans = 0
for i, a in enumerate(A):
    ans += abs(a - (b + (i+1)))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
lst = [(a-e-1) for e,a in enumerate(list(map(int,input().split())))]
b = int(np.median(lst))
ans = 0
for a in lst:
    ans += abs(a-b)
print(ans)

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==0:
  b=(l[n//2-1]+l[n//2])//2
else:
  b=l[n//2]
ans=0
for i in range(n):
  ans+=abs(l[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()
c = a[n//2]
if n % 2 == 0:
    c = int((a[n//2] + a[n//2-1]) // 2 + 0.5)
ans = 0
for i in range(n):
    ans += abs(a[i] - c)
print(ans)

Submission status: Accepted

Solution code:
import math

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


def calc(b):
    total = 0
    for i in range(1, N+1):
        ai = A[i-1]
        total += abs(ai - i - b)
    return total


B = list(sorted([A[i-1]-i for i in range(1, N+1)]))
if N % 2 == 0:
    # 偶数の時は中央値=平均値
    median = (B[(N-1)//2] + B[N//2]) / 2
    b1 = math.floor(median)
    b2 = math.ceil(median)
    print(min(calc(b1), calc(b2)))
else:
    b = B[N//2]
    print(calc(b))

Submission status: Accepted

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

if N == 1:
  print(0)
  exit()
B = sorted(B, reverse=True)
cs = B[:]
for i in range(N-1):
  cs[i+1] += cs[i]

ans = float('inf')
tmp = 0
for b in B:
  tmp += abs(b)
ans = min(ans, tmp)

for i in range(1, N):
  b = B[i]
  left = b*(i)-cs[i-1]
  right = -1*(b*(N-i-1)-(cs[-1]-cs[i]))
  ans = min(ans, abs(left)+abs(right))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
B = list(a-i-1 for i,a in zip(range(n), map(int,input().split())))
B.sort()
r = B[n//2] # median right
ans = 0
for bi in B: ans += abs(bi-r)
print(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 = sorted(a)
b1 = math.floor(sum(a)/n)
b2 = math.ceil(sum(a)/n)
b3 = b1-1
b4 = b2+1
b5 = a[n//2]
b6 = a[n//2-1]

ans1 = 0
ans2 = 0
ans3 = 0
ans4 = 0
ans5 = 0
ans6 = 0
for i in range(n):
  ans1 += abs(a[i]-b1)
  ans2 += abs(a[i]-b2)
  ans3 += abs(a[i]-b3)
  ans4 += abs(a[i]-b4)
  ans5 += abs(a[i]-b5)
  ans6 += abs(a[i]-b6)
print(min(ans5, ans6))

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 = sorted(a)
b1 = math.floor(sum(a)/n)
b2 = math.ceil(sum(a)/n)
b3 = b1-1
b4 = b2+1
b5 = a[n//2]
b6 = a[n//2-1]

ans1 = 0
ans2 = 0
ans3 = 0
ans4 = 0
ans5 = 0
ans6 = 0
for i in range(n):
  ans1 += abs(a[i]-b1)
  ans2 += abs(a[i]-b2)
  ans3 += abs(a[i]-b3)
  ans4 += abs(a[i]-b4)
  ans5 += abs(a[i]-b5)
  ans6 += abs(a[i]-b6)
print(min(int(ans1), int(ans2), int(ans3), int(ans4), ans5, ans6))

Submission status: Accepted

Solution code:
n = int(input())
B = list(a-i-1 for i,a in zip(range(n), map(int,input().split())))
B.sort()
ans = sum(B[n//2 + (n%2) :]) - sum(B[: n//2]) # sum(median left) - sum(median right)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
B = list(a-i for i,a in zip(range(1,n+1), map(int,input().split())))
B.sort()
l = r = B[n//2] # median left, right
if n%2 == 0: l -= 1 # left fix
ans_l, ans_r = 0, 0
for bi in B:
    ans_l += abs(bi-l)
    ans_r += abs(bi-r)
print(min([ans_l, ans_r]))

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()
r = B[n//2] # median right
l = B[n//2] if n%2 else B[n//2-1] # median left
# print(n,A)
# print(B)
# print(l,r)
ans_l = 0
ans_r = 0
for bi in B:
    ans_l += abs(bi-l)
    ans_r += abs(bi-r)
print(min([ans_l, ans_r]))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
b = [x[1] - x[0] for x in enumerate(A,1)]
b.sort()
if N % 2 == 1:
    median = b[N//2]
else:
    median = (b[(N//2)-1]+b[N//2]) // 2
c = [abs(x-median) for x in b]
print(sum(c))

Submission status: Accepted

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

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)]
m = median(b)
c = [abs(b[i] - m) for i in range(n)]
print(int(sum(c)))

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()
#print(b)
#ans = 10 ** 10
bi = b[n//2]
s = 0
for i in range(n):
    s += abs(a[i] - (i + 1 + bi))
#print(((n-1)//2+j)%n, s)
#ans = min(ans, s)
print(s)

"""
for j in range(3):
    bi = b[(n//2+j)%n]
    s = 0
    for i in range(n):
        s += abs(a[i] - (bi + i + 1))
    #print(((n-1)//2+j)%n, s)
    ans = min(ans, s)
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()
idx= n//2
bi = b[idx]
ans = 0
for i in range(n):
    ans += abs(a[i] - (i + 1 + bi))
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()
#print(a)
m,now=sum(a)-2*a[0]+2*a[0]-a[0]*n,sum(a)-2*a[0]+2*a[0]-a[0]*n
for i in range(1,n):
    now=now-(2*(i)*a[i-1]-n*a[i-1])+(-2*a[i]+2*(i+1)*a[i]-n*a[i])
    m=min(now,m)
    #print(now)
print(m)

Submission status: Accepted

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

box = [0]*n
ans = 0
for i in range(n):
    box[i] = a[i] - (i+1)
box.sort()

idx = n//2

b = box[idx]

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

Submission status: Accepted

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

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = IL()

AA = [A[i]-i for i in range(N)]
if N%2 == 0:
  AA.sort()
  ANS1 = [abs(AA[i]-AA[N//2-1])  for i in range(N)]
  ANS2 = [abs(AA[i]-AA[N//2])  for i in range(N)]
  print(min(sum(ANS1),sum(ANS2)))
else:
  AA.sort()
  ANS = [abs(AA[i]-AA[N//2])  for i in range(N)]
  print(sum(ANS))

Submission status: Accepted

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

b=[x-i-1 for i,x in enumerate(a)]
"""
b=[]
for///:
    y.append///
"""
m=int(median(b))
print(sum(abs(y-m) for y in b))

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=sorted(b)
mid=b[n//2]
ans=0
for i in range(n):
    ans+=abs(b[i]-mid)
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()
if N%2==1:
    W = B[N//2]
    out = 0
    for i in range(N):
        out += abs(B[i]-W)
else:
    X = B[N//2-1]
    Y = B[N//2]
    Z = X+Y
    if Z%2==0:
        W = Z//2
        out = 0
        for i in range(N):
            out += abs(B[i]-W)
    else:
        W1 = Z//2
        out1 = 0
        for i in range(N):
            out1 += abs(B[i]-W1)
        W2 = Z//2
        out2 = 0
        for i in range(N):
            out2 += abs(B[i]-W2)
        out = min(out1,out2)
print(out)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array(lr(), dtype=np.int32)
A -= np.arange(1, N+1)
answer = np.abs(A - int(np.median(A))).sum()
print(answer)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array(lr())
A -= np.arange(1, N+1)
A.sort()

def check(i):
    ret = np.abs(A - A[i]).sum()
    return ret

answer = min(check(0), check(-1))
left = 0; right = N-1
l_mid = (left*2 + right) // 3
r_mid = (left + right*2) // 3
while abs(right-left) > 2:
    l_mid = (left*2 + right) // 3
    r_mid = (left + right*2) // 3
    if check(l_mid) < check(r_mid):
        right = r_mid
    else:
        left = l_mid

cand = min(check(l_mid), check(r_mid))
answer = min(answer, cand)
print(answer)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
b = [0]*n
for i in range(n):
    sa = a[i] - (i+1)
    b[i] = sa
b.sort()
idx = int(n/2) 

p = b[idx]
ans = 0
for i in range(n):
    ans += abs(i+1+p-a[i])
print(ans)

Submission status: Accepted

Solution code:
import statistics
def resolve():
	n = int(input())
	a = list(map(int, input().split()))
	seq = []
	for i in range(1, n+1):
		seq.append(i-a[i-1])
	seq = sorted(seq)
	m = int(statistics.median(seq))
	ans = 0
	for i in seq:
		ans += abs(i-m)
	print(ans)
resolve()

Submission status: Accepted

Solution code:
N = int(input())
A = tuple(map(int, input().split()))
B = [a-(i+1) for i, a in enumerate(A)]
B = sorted(B)
b = B[len(B) // 2]
s = 0
for b_ in B:
    s += abs(b_ - b)
print(s)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
ami = [a[i]-(i+1) for i in range(n)]
ami.sort()
# print(ami)
ans = 0
if n % 2 == 1:
    for i in range(n):
        ans += abs(ami[i]-ami[n//2])
else:
    cnt1 = 0
    cnt2 = 0
    for i in range(n):
        cnt1 += abs(ami[i]-ami[n//2])
        cnt2 += abs(ami[i]-ami[n//2-1])
    ans = min(cnt1,cnt2)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

n = I()
A = LI()
B = [A[i]-i-1 for i in range(n)]
B.sort()
mid = B[n//2]
mid2 = B[(n-1)//2]
def sad(b, n):
    ret = 0
    for i in range(n):
        ret += abs(B[i]-b)
    return ret

ans = min(sad(mid, n), sad(mid2, n))
print(ans)

Submission status: Accepted

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A = [A[i] - i - 1 for i in range(N)]
    A.sort()
    diff = A[(N-1)//2]
    print(sum([abs(a-diff) for a in A]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=LI()
for i in range(n):
    lis[i]-=i+1
lis.sort()
c=lis[(n-1)//2] if n%2==1 else lis[n//2]
ans=0
for i in range(n):
    ans+=abs(lis[i]-c)
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    A = [a - (i + 1) for i, a in enumerate(A)]
    # argmin -> median of A
    A.sort()
    ans = 0
    for i in range(N // 2):
        ans += A[- (i + 1)] - A[i]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, *a = map(int, open(0).read().split())
s = [a - i - 1 for i, a in enumerate(a)]
b = sorted(s)[n // 2]
print(sum(abs(s - b) for s in s))

Submission status: Accepted

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

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

a.sort()

b = a[n // 2]

ret = 0

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

print(ret)

Submission status: Accepted

Solution code:
import sys
import numpy as np


def main():
  readline = sys.stdin.readline
  
  n = int(readline().rstrip())
  a = np.array(
    tuple(int(a_i) for a_i in readline().rstrip().split())
  )
  
  b = int(np.median(a - np.arange(1, n + 1)))
  
  print(np.sum(np.abs(a - np.arange(1, n + 1) - b)))
  

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import statistics
n = int(input())
A = [int(i) for i in input().split()]
A_list = []
ans_l,ans_h = 0,0
Min = 10**9

for i in range(n):
    A_list.append(A[i]-(i+1))

b_lowkey = statistics.median_low(A_list)
b_highkey = statistics.median_high(A_list)

for i in range(n):
    ans_l += abs(A_list[i]-b_lowkey)
    ans_h += abs(A_list[i]-b_highkey)
print(min(ans_l,ans_h))

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
B=[A[i]-(i+1) for i in range(n)]
C=sorted(B)
b=C[n//2]
import functools
x=functools.reduce(lambda x,y:abs(x)+abs(y),[C[i]-b for i in range(n)])
print(x)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.array(tuple(map(int, input().split())), dtype=np.int64) - np.arange(N) - 1
median = np.median(A)
print(int(min(np.abs(A - median + 0.5).sum(), np.abs(A - median - 0.5).sum())) if int(median * 2) & 1 else int(np.abs(A - median).sum()))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.array(tuple(map(int, input().split())), dtype=np.int64) - np.arange(N) - 1
median = np.median(A)
if int(median * 2) & 1:
    print(int(min(np.abs(A - median + 0.5).sum(), np.abs(A - median - 0.5).sum())))
else:
    print(int(np.abs(A - median).sum()))

Submission status: Accepted

Solution code:
from math import ceil, floor

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

temp_list = sorted([a - i for a, i in zip(a_list, range(1, n + 1))])

def calc(num):
    return sum([abs(temp - num) for temp in temp_list])

i = n // 2
if n % 2 == 0:
    med = (temp_list[i - 1] + temp_list[i]) / 2
    print(min(calc(floor(med)), calc(ceil(med))))
else:
    med = temp_list[i]
    print(calc(med))

Submission status: Accepted

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

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

A_diff = np.array([a - i for i, a in enumerate(A, 1)])
my_median = np.median(A_diff)

print(int(np.sum(np.abs(A_diff * -1 + my_median))))

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(reverse = True)
b = A[(N-1)//2]
for i in range(N):
  A[i] = abs(A[i]-b)
print(sum(A))

Submission status: Accepted

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

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

A.sort()
b=A[N//2]
ans = sum( abs(A[i] - b ) for i in range(N))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
alta = []
for i in range(N):
    alta.append(A[i] - (i + 1))
# 最小値を0に揃えないとバグる
plus = min(alta)
for i in range(N):
    alta[i] -= plus

def f(x):
    sum = 0
    for i in alta:
        sum += abs(x - i)
    return sum

# 極値があるので三分探索使う
left, right = 0, max(alta)
# 答えが整数になる問題の場合このrightとleftの幅を3未満にするとバグる
while abs(right - left) > 3:
    mid1 = (right * 2 + left) // 3 + 1
    mid2 = (right + left * 2) // 3
    if f(mid1) >= f(mid2):
        # 上限を下げる（最小値をとるxはもうちょい下めの数だな）
        right = mid1
    else:
        # 下限を上げる（最小値をとるxはもうちょい上めの数だな）
        left = mid2
ans = float('inf')
for i in range(left, right + 1):
    ans = min(ans, f(i))
print(ans)