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
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# https://atcoder.jp/contests/arc100/tasks/arc100_a

N = read_a_int()
A = read_ints()
# Ai-iをBiとする
# Σ|Bi - b|を最小化するはBiの中央値(ということを経験的に知っている)(二部探索してみればいいこと)

B = []
for i, a in enu(A, start=1):
    B.append(a - i)
import numpy as np
b = np.median(B)
ans = 0
print(int(np.abs(np.array(B) - b).sum()))

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

med = median(a)
ans = 0

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

print(int(ans))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

N = int(input())

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

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

tmp = A[N // 2]

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

print (ans)

Submission status: Accepted

Solution code:
n = int(input())
ll = list(map(int,input().split()))
li = [l-i for i,l in enumerate(ll)]
import statistics
median = statistics.median(li)
ans = 0
for l in li:
    ans+= abs(l-median)
print(int(ans))

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
c = [a[i]-i-1 for i in range(n)]
c.sort()
mn = s = sum(c[1:])-(n-1)*c[0]
for i in range(n-1):
    s += (2*i+2-n)*(c[i+1]-c[i])
    mn = min(mn,s)
print(mn)

Submission status: Accepted

Solution code:
def main():
    N, *A = map(int, open(0).read().split())
    B = [A[i] - i - 1 for i in range(N)]
    B.sort()
    b1 = B[(N-1)//2]
    b2 = B[N//2]
    ans1 = ans2 = 0
    for i in range(N):
        a = A[i] - i - 1
        ans1 += abs(a - b1)
        ans2 += abs(a - b2)
    print(min(ans1, ans2))

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, *a = map(int, read().split())
a = sorted(aa - i for i, aa in enumerate(a))
print(sum(a[n // 2:]) - sum(a[:(n + 1) // 2]))

Submission status: Accepted

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

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

b = statistics.median(x)

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

print(int(ans))

Submission status: Accepted

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

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

x.sort()
x_ = []
b = 0
if x.count(0) <= n//2:
    for i in range(n):
        if x[i] != 0:
             x_.append(x[i])

    b = statistics.median(x_)

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

print(int(ans))

Submission status: Accepted

Solution code:
import math
n=int(input())
res = [0]*n
A=[int(i) for i in input().split()]
for i in range(n):
    res[i]=(A[i]-(i+1))
res.sort()

if n%2==1:
    ans = sum([abs(i-res[n//2]) for i in res])
else:
    b0 = (res[n//2-1]+res[n//2])//2
    b1 = (res[n//2-1]+res[n//2])
    ans = min(sum([abs(a-b0) for a in res]), sum([abs(a-b1) for a in res]))
print(ans)

Submission status: Accepted

Solution code:
import math
n=int(input())
res = [0]*n
A=[int(i) for i in input().split()]
for i in range(n):
    res[i]=(A[i]-(i+1))
res.sort()

if n%2==1:
    ans = sum([abs(i-res[n//2]) for i in res])
else:
    b0 = (res[n//2-1]+res[n//2])//2
    b1 = math.ceil(res[n//2-1]+res[n//2])
    ans = min(sum([abs(a-b0) for a in res]), sum([abs(a-b1) for a in res]))
print(ans)

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

b = B[n//2]

total = 0

for i in B:
    total += abs(i - b)
print(total)

Submission status: Accepted

Solution code:
import math
N = int(input())
A = sorted([int(v)-i for i, v in enumerate(input().split(), start=1)])

if N % 2 == 1:
    ans = sum([abs(a-A[N//2]) for a in A])
else:
    b0 = (A[N//2-1]+A[N//2])//2
    b1 = math.ceil(A[N//2-1]+A[N//2])
    ans = min(sum([abs(a-b0) for a in A]), sum([abs(a-b1) for a in A]))

print(ans)

Submission status: Accepted

Solution code:
# 2020/05/04
# AtCoder Beginner Contest 102 - C

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

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

ami.sort()
medi = ami[n // 2]

wk_val = 0
for j in range(n):
    wk_val = wk_val + abs(a[j]-(medi+j+1))

ans = wk_val

# Output
print(ans)

Submission status: Accepted

Solution code:
def main(n,a):
  a=sorted([a[i]-i for i in range(n)])
  m0=a[n//2]
  m1=a[n//2-1]
  ans0,ans1=0,0
  for i in range(n):
    ans0+=abs(a[i]-m0)
    ans1+=abs(a[i]-m1)
  print(min(ans0,ans1))
if __name__=='__main__':
  import sys
  input = sys.stdin.readline
  n=int(input())
  a=list(map(int,input().split()))
  main(n,a)

Submission status: Accepted

Solution code:
import statistics as stat
import math
N = int(input())
A = list(map(int, input().split()))
linear = [i+1 for i in range(N)]
B = [x-y for (x, y) in zip(A, linear)]
med = stat.median(B)
med_up = math.ceil(med)
med_low = math.floor(med)
count_up = 0
count_low = 0
for i in range(N):
    count_up += abs(B[i] - med_up)
    count_low += abs(B[i] - med_low)
print(min(count_up, count_low))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


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

    A = [a - (i + 1) for i, a in enumerate(A)]
    A.sort()
    b = A[(N + 1) // 2 - 1]

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

    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
INF = 114514191981036436433-4
bl = []

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

ans = sum(c)
cur = sum(c)

for i in range(1,n):
    e = c[i] - c[i-1]
    cur = cur + i * e - (n-i) * e
    ans = min(cur,ans)
    
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
arr=limii()
for i in range(n):
    arr[i]-=i+1

arr.sort()

def med(x):
    h = int(n/2)
    if n%2==0:
        return (arr[h-1]+arr[h])//2
    else:
        return arr[int((n-1)/2)]

ans=10**100
if n%2 ==0:
    ans1=0
    ans2=0
    m=med(arr)
    for i in range(n):
        ans1+=abs(arr[i]-m)
        ans2+=abs(arr[i]-(m+1))
    ans=min(ans1,ans2)
else:
    m=med(arr)
    ans1=0
    for i in range(n):
        ans1+=abs(arr[i]-m)
    ans=ans1
print(ans)

Submission status: Accepted

Solution code:
_,a=open(0);S=sorted(int(x)-i for i,x in enumerate(a.split()));print(sum(abs(S[len(S)//2]-s)for s in S))

Submission status: Accepted

Solution code:
_,a=open(0)
S=sorted(int(x)-i for i,x in enumerate(a.split()))
print(sum(abs(S[len(S)//2]-s)for s in S))

Submission status: Accepted

Solution code:
input();S=sorted(int(x)-i-1 for i,x in enumerate(input().split()))
print(sum(abs(S[len(S)//2]-s)for s in S))

Submission status: Accepted

Solution code:
N=int(input())
B=sorted(int(x)-i-1 for i,x in enumerate(input().split()))
def sad(x):
    return sum(abs(b-x)for b in B)
print(sad(B[N//2]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
a = list(map(int, readline().split()))
a = sorted(x - i for i, x in enumerate(a))
low = (len(a) + 1) // 2 - 1
high = len(a) // 2
print(sum(a[high:]) - sum(a[:low + 1]))

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()
b1 = a[n // 2]
b2 = a[(n // 2 ) - 1]
r1=0
r2=0
for i in range(n):
    r1+=abs(a[i]-b1)
    r2+=abs(a[i]-b2)
print(min(r1,r2))

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

Submission status: Accepted

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

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

median = statistics.median(bi)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
import math

def main():
    N = int(input())
    A = [int(a) - i for i, a in enumerate(input().split(), 1)]
    A.sort()

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

    
main()

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

A_i = [A[i] - i - 1 for i in range(N)]
A_i.sort()
if N % 2 == 1:
    b = A_i[N // 2]
    ans = 0
    for a in A_i:
        ans += abs(a - b)

    print(ans)
else:
    b1 = A_i[N // 2]
    b2 = A_i[N // 2 - 1]
    ans1 = 0
    ans2 = 0
    for a in A_i:
        ans1 += abs(a - b1)
        ans2 += abs(a - b2)
    print(min(ans1, ans2))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    N = Scanner.int()
    A = Scanner.map_int()
    A = [a - (i + 1) for i, a in enumerate(A)]
    A.sort()
    if N % 2 == 1:
        m = A[N // 2]
        print(sum([abs(a - m) for a in A]))
    else:
        m = A[N // 2 - 1]
        ans = sum([abs(a - m) for a in A])
        m = A[N // 2]
        ans = min(ans, sum([abs(a - m) for a in A]))
        print(ans)


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] -= (i+1)

A.sort()

med = [A[n//2]]
if n % 2 == 0:
    med.append(A[n//2 - 1])

ans = 1000000000000000000
for m in med:
    cnt = 0
    for a in A:
        cnt += abs(a-m)
    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import statistics

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

b = statistics.median(A)
ans = int(sum([abs(a-b) for a in A]))
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()
dis = A[-(-N // 2) - 1]
ans = 0
for i in range(N):
    ans += abs(A[i] - dis)
print(ans)

Submission status: Accepted

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

Bn = sorted([An[i] - (i + 1) for i in range(N)])

if N % 2 ==1:
  median = Bn[N//2]
  error = 0
  for n in range(N):
    error += abs(Bn[n] - median)
  print(error)
else:
  median1 = (Bn[N//2] + Bn[N//2-1])//2
  median2 = (Bn[N//2] + Bn[N//2-1] + 1) //2
  error1 = 0
  error2 = 0
  for n in range(N):
    error1 += abs(Bn[n] - median1)
    error2 += abs(Bn[n] - median2)
  print(min(error1, error2))

Submission status: Accepted

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

from math import floor

def main():
  n = int(input())
  la = list(map(int, input().split()))
  la = [a-i for i, a in enumerate(la, 1)]
  la.sort()
  if len(la) == 1:
    print(0)
  else:
    ix = (len(la)-1) // 2
    print(min([sum(map(lambda x: abs(x-la[ix+i]), la)) for i in range(2)]))

if __name__=='__main__':
  main()

Submission status: Accepted

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

B.sort()
if (N % 2 == 1):
    b = B[N//2]
else:
    b = round((B[N//2]+B[N//2-1])/2)

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

print(ans)

Submission status: Accepted

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

res = 0
x = B[N//2]

for i in range(N):
    res += max(x - B[i], -x + B[i])

print(res)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8

n = int(input().rstrip())

numbers = list(map(int, input().rstrip().split(" ")))

tmp = list(sorted([ [numbers[i] - i, i] for i in range(n)]))


ans = 1000000000 * n

target = tmp[int(n/2)][0]
if n % 2 == 0:
    target = int((tmp[int(n/2)][0]+tmp[int(n/2)-1][0])/2)

ans = [abs(numbers[i] - (target + i)) for i in range(n)]
print(sum(ans))

Submission status: Accepted

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

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

if N % 2 == 1:
    ans = 0
    for i in A:
        ans += abs(i - A[N//2])
else:
    ans = 0
    ansk = 0
    for i in A:
        ans += abs(i - A[N//2])
        ansk += abs(i - A[N//2-1])
    ans = min(ans, ansk)

print(ans)

Submission status: Accepted

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

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

if N % 2 == 1:
    ans = 0
    for i in A:
        ans += abs(i - A[N//2])
else:
    ans = 0
    ansk = 0
    a = (A[N//2] + A[N//2-1]) // 2
    for i in A:
        ans += abs(i - a)
        ansk += abs(i - a-1)
    ans = min(ans, ansk)

print(ans)

Submission status: Accepted

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

A = sorted([a[i] - i for i in range(n)])
b = A[n//2]
ans=0
for i in range(n):
    ans += abs(a[i] - (b+i))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import statistics

def solve():
    N = int(input())
    A = list(map(int,input().split()))
    B = list(A[i]-(i+1) for i in range(N))
    B.sort()
    b = int(statistics.median(B))
    ##print(b)
    ans = 0
    for i in range(1,N+1):
        ans += abs(A[i-1]-(b+i))
    print(ans)
    ##ans2 = sum([A[i-1]-(b+i) for i in range(1,N+1)])
    ##print(ans2)

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

A = sorted([A[i] - i - 1 for i in range(N)])
ans = sum(abs(A[i] - A[N // 2]) for i in range(N))

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

def geta(b):
    un=0
    for i in range(n):
        un+=abs(sub[i]-b)
    return un

med = sub[n//2]
ans=10**20
for i in range(med-1,med+1):
    num = geta(i)
    if ans > num:
        ans=num
print(ans)

Submission status: Accepted

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

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

def geta(b):
    un=0
    for i in range(n):
        un+=abs(sub[i]-b)
    return un

med = sub[n//2]
ans=geta(med)
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

A.sort()

if N%2==1:
    s=0
    for i in range(0,N):
        s=s+abs(A[i]-A[(N-1)//2])
    print(s)
else:
    s=0
    for i in range(0,N):
        s=s+abs(A[i]-A[N//2])
    print(s)

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()
b = (A[N//2-1]+A[N//2])//2 if N%2==0 else A[N//2]
print(sum([abs(a-b) for a in A]))

Submission status: Accepted

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


def sadness(b):
  sad = 0
  for i, e in enumerate(a):
    i += 1
    sad += abs(e - (b + i))
  return sad


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

d.sort()

if len(d) % 2 == 1:
  print(sadness(d[len(d) // 2]))
else:
  print(min(sadness(d[len(d) // 2]), sadness(d[len(d) // 2 + 1])))

Submission status: Accepted

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


def sadness(b):
  sad = 0
  for i, e in enumerate(a):
    i += 1
    sad += abs(e - (b + i))
  return sad


left, right = -10**9, 10**9 + 1
while right - left > 1:
  mid = (left + right) // 2

  if sadness(mid) > sadness(mid + 1):
    left = mid
  else:
    right = mid

# for b in range(-20, 20):
#   print(b,sadness(b))

print(min(sadness(left), sadness(right)))

Submission status: Accepted

Solution code:
from statistics import median
n=int(input())
a=list(map(int,input().split()))
mid=0
l=[]
for i in range(n):
    l+=[a[i]-i-1]

mid=median(l) if n%2!=0 else sorted(l)[n//2]
ans=0
for i in range(n):
    ans+=abs(a[i]-(mid+i+1))

print(int(ans))

Submission status: Accepted

Solution code:
from statistics import median
n=int(input())
a=list(map(int,input().split()))
mid=0
l=[]
for i in range(n):
    l+=[a[i]-i-1]

mid=median(l)
ans=0
for i in range(n):
    ans+=abs(a[i]-(mid+i+1))

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

a_sum=[a[0]]
a_minus_sum=[-a[0]]

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

ans=min(a_sum[-1]-a[0]*n,a_minus_sum[-1]+a[-1]*n)

for g in range(1,n-1):
    ans=min(a[g]*(-n+2*g+1)+a_sum[-1]-a_sum[g]+a_minus_sum[g-1],ans)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7


def main():
    # sys.stdin = open("sample.txt")
    N = Scanner.int()
    A = Scanner.map_int()
    B = [0] * N
    for i in range(N):
        B[i] = A[i] - (i+1)
    B.sort()

    a, b = B[N//2-1], B[N//2]
    ans = 0
    tmp = 0
    for i in range(N):
        ans += abs(A[i] - (a + i + 1))
        tmp += abs(A[i] - (b + i + 1))
    ans = min(ans, tmp)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections 

N = int(input())
A = list(map(int,input().split()))
A = sorted([j - (i + 1) for i,j in enumerate(A)])

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

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

Submission status: Accepted

Solution code:
def solve():
    N, *A = map(int, open(0).read().split())

    B = [0] * N
    for i, a in enumerate(A):
        B[i] = a - (i + 1)
    B.sort()

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

    ans = 0
    for i, a in enumerate(A):
        ans += abs(a - (b + i + 1))
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def solve():
    N, *A = map(int, open(0).read().split())

    B = [0] * N
    for i, a in enumerate(A):
        B[i] = a - (i + 1)
    B.sort()

    b = 0
    if N % 2 == 1:
        b = B[N // 2]
    else:
        b = round((B[N // 2] + B[N // 2 - 1]) // 2 + 0.1)

    ans = 0
    for i, a in enumerate(A):
        ans += abs(a - (b + i + 1))
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = list(map(int, readline().split()))
    for i in range(n):
        a[i] -= i + 1
    a.sort()
    t = 0
    for v in a:
        t += abs(a[n // 2] - v)
    print(t)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())))
a = [v - i - 1 for i, v in enumerate(a)]
b = sorted(a)[n // 2]
print(np.sum([abs(a - b)]))

Submission status: Accepted

Solution code:
import statistics
N = int(input())
A = list(map(int,input().split()))
A2 = sorted([A[i]-i-1 for i in range(N)])
med = int(statistics.median(A2))
med2 = med+1
sum1 = 0
sum2 = 0
for i in range(N):
    sum1 += abs(A2[i]-med)
    sum2 += abs(A2[i]-med2)
print(min(sum1,sum2))

Submission status: Accepted

Solution code:
def examC():
    N = I()
    A = LI()
    Ad = [0]*N
    for i in range(N):
        Ad[i] = A[i]-(i+1)
    Ad.sort()
#    print(Ad)
    b = Ad[N//2]
    ans = 0
    for a in Ad:
        ans +=abs(a-b)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = 10**18

if __name__ == '__main__':
    examC()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
from statistics import median

N = int(input())
A = list(map(int, input().split()))
list_n = list(range(1, (N+1), 1))
A_tmp = np.array(A)
list_n_tmp = np.array(list_n)
list_diff = A_tmp - list_n_tmp
b = median(list_diff)
Xtmp = 0

for n in range(0, N, 1):
    Xtmp += abs(A[n] - (b + n + 1))

print(int(Xtmp))