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:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    for i in range(N):
        A[i] -= i + 1
    A.sort()
    tmp = A[0]
    for i in range(N):
        A[i] -= tmp
    l = -1
    r = N
    cur = sum(A)
    #print(A)
    while r - l > 1:
        m = (l + r) // 2
        val = A[m]
        tmp = 0
        for a in A:
            tmp += abs(a - val)
        if tmp <= cur:
            l = m
            cur = tmp
        else:
            r = m
    val = A[l]
    ret = 0
    for a in A:
        ret += abs(a - val)

    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = input()
A = list(map(int, input().split()))
 
l = sorted([ x - (idx+1) for x,idx in enumerate(A)])
#print(l)
 
import statistics
median = statistics.median(l)
#print(median)
 
ans = 0
for x in l:
  ans += abs(x - median)
  
print(int(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


###############################################################################


def main():
    n = intin()
    alist = intina()
    alist = [a - (i + 1) for i, a in enumerate(alist)]

    alist.sort()
    b = alist[n // 2]

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




if __name__ == '__main__':
    main()

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

b_index = N // 2
A.sort()

def regret(A, b):
    result = 0
    for a in A:
        result += abs(a-b)
    return result

ans = regret(A, A[b_index])
if b_index + 1 < N:
    ans = min(ans, regret(A, A[b_index+1]))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import statistics

n = int(input())
inputs = [int(i) for i in input().split()]
a = np.array(inputs)

z = a - np.array(range(1, n + 1))
nums = list(set(inputs))

print(int(sum(abs(z - np.ones(len(a)) * statistics.median(z)))))

Submission status: Accepted

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

# ずらす
for i in range(N):
    A[i] = A[i] - (i+1)

A = sorted(A)
m = float('inf')
bs = []

# 探索対象
if N//2-1<N:
    bs.append(A[N//2-1])
if N//2<N:
    bs.append(A[N//2])
if N//2+1<N:
    bs.append(A[N//2+1])

for b in bs:
    diff = sum(list(map(lambda x: abs(x-b),A)))
    m = min(m,diff)

print(m)

Submission status: Accepted

Solution code:
N=int(input())//2
number = 0
result = 0
a_list = []
for i in input().split():
	a_list.append(int(i)-number)
	number+=1
a_list.sort()
for i in a_list:
	result+=abs(i-a_list[N])
print(result)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
for i in range(len(A)):
  A[i] -= (i+1)
A.sort()
b = A[N//2]
print(sum( abs(a - b) 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, radians
from heapq import heappop, heappush, heapify, heappushpop
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

# for i in A:
# 	if x-i-1 < 0:
# 		minus.append(x-i-1)
# 	elif x-i-1 == 0:
# 		zero.append(0)
# 	else:
# 		plus.append(-(x-i-1))
# if len(zero) + minus and len(zero) > plus:
# 	print(sum(plus)+sum(minus))
# else:
# 	len(minus) > len(zero) and 
B = [x-i-1 for i, x in enumerate(A)]
B.sort()
# print(B)
B = [abs(x-B[len(B)//2]) for x in B]
# print(B)
print(sum(B))
# print(sum(B)-abs(B[len(B)//2])*N)

Submission status: Accepted

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

list_c = [list[i]-(i+1) for i in range(N)]
list_c.sort()

med = list_c[len(list_c)//2]

ans = 0

for i in range(N):
    ans += abs(list[i]-(med+(i+1)))

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, A: "List[int]"):
    A = sorted([a - i for i, a in enumerate(A, 1)])
    b = A[len(A) // 2]
    return sum([abs(a - b) for a in A])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    result = solve(N, A)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(n):
    listb.append(lista[i]-(1*i +1))
    
listb.sort()
med = listb[n//2]
ans = 0
for i in range(n):
    ans += abs(listb[i]-med)

    
print(ans)

Submission status: Accepted

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

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

mid = x[len(x)//2]
ans = 0
for i in range(1, N+1):
    ans += abs(A[i-1]-(mid+i))
print(ans)

Submission status: Accepted

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

x = [A[i-1]-i for i in range(1, N+1)]
x.sort()
if len(x)%2==1:
    mid = x[len(x)//2]
    ans = 0
    for i in range(1, N+1):
        ans += abs(A[i-1]-(mid+i))
    print(ans)
else:
    mid1 = x[len(x)//2-1]
    mid2 = x[len(x)//2]
    ans1 = ans2 = 0
    for i in range(1, N+1):
        ans1 += abs(A[i-1]-(mid1+i))
        ans2 += abs(A[i-1]-(mid2+i))
    print(min(ans1, ans2))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
N = int(input())
A = [int(v)-(i+1) for i,v in enumerate(input().split())]
A.sort()
num = A[N//2]
ret = 0
for i in A:
    ret += abs(i-num)

print(ret)

Submission status: Accepted

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

m = diff[len(diff)//2]
ans = 0

for i,l in enumerate(list):
    ans += abs(list[i]-(i+1+m))

print(ans)

Submission status: Accepted

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

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

	print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


	mid1 = A[N//2]
	mid2 = A[N//2]
	if N >= 2:
		mid2 = A[N//2 + 1]

	ans1 = 0
	ans2 = 0
	for i in range(N):
		ans1 += abs(A[i] - mid1)
		ans2 += abs(A[i] - mid2)

	print(min(ans1, ans2))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from statistics import median

N=int(input())
A=[int(v)-k for k,v in enumerate(input().split())]
b=int(median(A))
print(sum([abs(a-b) for a in A]))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

B.sort()

b = B[N//2]

count = 0
for i in B:
    count += abs(i-b)

print(count)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import statistics


N = int(input())
A = list(map(int, input().split()))
sum_a = 0
B = [0]*len(A)
for i in range(N):
    B[i] = A[i] - i
B.sort()
sum_b = 0
b = statistics.median_low(B)
for i in range(N):
    sum_b += abs(B[i]-b)
print(sum_b)

Submission status: Accepted

Solution code:
def ans(n):
    tmp=0
    for i in range(N):
        tmp+=abs(a[i]-a[n-1])
    return tmp


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

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



print(ans(N//2) if N%2==0 else ans(N//2+1))

Submission status: Accepted

Solution code:
def ans(n):
    tmp=0
    for i in range(N):
        tmp+=abs(a[i]-a[n-1])
    return tmp


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

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

print(ans(N//2) if N%2==0 else ans(N//2+1))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
import itertools
INF = float("inf")


def solve(N: int, A: "List[int]"):
    A = [a-i-1 for i, a in enumerate(A)]
    A.sort()
    s = sum(A)-N*A[0]
    for i in range(len(A)):
        if i == 0:
            continue
        buf = (2*i+1-N-1)*(A[i]-A[i-1])
        if buf <= 0:
            s += buf
        else:
            break
    print(s)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
for i in range(N):
    A[i] -= i + 1
A.sort()
sunuke = A[N // 2]
ans = 0
for a in A:
    ans += abs(a-sunuke)
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()
if N % 2 == 0:
	center_num = A[int(N / 2)]
else:
	center_num = A[int((N - 1) / 2)]
ans = 0
for j in A:
	ans += abs(j - center_num)

print(ans)

Submission status: Accepted

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

minus = 0
plus = 0
for c in b:
    if c <0:
        minus +=1
    elif c >0:
        plus +=1

m1 = b[N//2]
m2 = b[0] if N==1 else b[N//2+1]
out = min(sum([abs(c-m1) for c in b]),sum([abs(c-m2) for c in b]))
print(out)

Submission status: Accepted

Solution code:
N = int(input())
a_list = [int(i) for i in input().split()]
b_list = [0 for i in range(N)]
for i in range(N):
    b_list[i] = a_list[i] - (i + 1)
b_list.sort()
b1,b2 = b_list[N//2-1], b_list[N//2]
c1,c2 = 0,0
for i in range(N):
    c1 += abs(a_list[i] - (b1 + i + 1))
for i in range(N):
    c2 += abs(a_list[i] - (b2 + i + 1))
print(min(c1,c2))

Submission status: Accepted

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

Submission status: Accepted

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

import statistics
b = int(statistics.median(a))
ans = sum([abs(i-b) for i in a])
print(ans)

Submission status: Accepted

Solution code:
import math
import statistics


N = int(input())
A = [int(i) for i in input().split()]
b = math.ceil(statistics.median([a-n for a,n in zip(A,range(1,N+1))]))
ans = [abs(a - b - n) for a,n in zip(A,range(1, N+1))]
print(sum(ans))

Submission status: Accepted

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

b = int(0.5 * (A_[len(A_)//2] + A_[len(A_)//2 - (len(A_)+1)%2]))

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

Submission status: Accepted

Solution code:
from numpy import median

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

Submission status: Accepted

Solution code:
from numpy import median

N = int(input())
A = list(map(int, input().split()))
A = [a - i - 1 for i, a in enumerate(A)]
A = sorted(A)
b = int(median(A))
print(sum([abs(i - b) for i in A]))

Submission status: Accepted

Solution code:
import numpy as np


def f(_b, _a):
    return sum([abs(i - _b) for i in _a])


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

Submission status: Accepted

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

import statistics

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

b = []

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

bf = int(statistics.median(b))

ans = 0

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

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

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce
import fractions
import math
import sys
import statistics
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]  # LIST INT
def LF(): return [float(x) for x in sys.stdin.readline().split()]  # LIST FLOAT
def LS(): return sys.stdin.readline().split()  # LIST STRING
def MI(): return map(int, sys.stdin.readline().split())  # MAP INT
def II(): return int(sys.stdin.readline())  # INPUT INT
def IS(): return input()  # INPUT STRING
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):  # greatest common divisor
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):  # least common multiple
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))


N = II()
a = LI()
ai = [a[i-1] - i for i in range(1, N+1)]
b = round(statistics.median(ai))
print(sum([abs(b - ai[i]) for i in range(len(ai))]))

Submission status: Accepted

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

res = 10 ** 100
if n % 2 == 0:
	p = n // 2 - 1
	q = n // 2
	for cand in [p, q]:
		tmp = 0
		for i in a:
			tmp += abs(i - a[cand])
		res = min(res, tmp)
else:
	tmp = 0
	for i in a:
		tmp += abs(i - a[n // 2])
	res = min(res, tmp)
	
print(res)

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)])
mid = A[N//2]
print(sum([abs(a-mid) for a in A]))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
 
import statistics
 
N = int(input())
A = list(map(int, input().rstrip().split(' ')))
 
A_dash = sorted([x - i - 1 for i, x in enumerate(A)])
med = int(statistics.median(A_dash))

print(sum([abs(x - med) for x in A_dash]))

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

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


inf = float('inf')


# globals
N = 0
A = []
X = []


def set_inputs():
    global N, A
    N = get_int()
    A = get_li()
    return


def f(n):
    return sum(abs(x-n) for x in X)


def main():
    global X
    setrecursionlimit(100000)
    set_inputs()
    X = [a - (i + 1) for i, a in enumerate(A)]
    X.sort()
    b = X[0]
    i = 1
    passed = 0
    same = 1
    coming = N - 1
    ans = f(b)
    tmp = ans
    while i < N:
        if X[i] == b:
            same += 1
            coming -= 1
            i += 1
            continue
        diff = X[i] - b
        tmp = tmp + (passed + same - coming) * diff
        ans = min(ans, tmp)
        b = X[i]
        passed += same
        same = 1
        coming -= 1
        i += 1
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
a=[a[i]-(i+1) for i in range(n)]
a.sort()
if n%2==0:
    print(sum(a[n//2:])-sum(a[0:n//2]))
else:
    print(sum(a[n//2+1:])-sum(a[0:n//2]))

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
a=[a[i]-(i+1) for i in range(n)]
a.sort()
if n%2==0:
    print(sum(a[n//2:])-sum(a[0:n//2]))
else:
    print(sum(a[n//2+1:])-sum(a[0:n//2]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[0]
c=[0]
d=[0]
e=[0]
count=0
count2=0
count3=0
count4=0
for i in range(n):
  a[i]-=i
a.sort()
for i in range(n-1):
  count+=a[i+1]-a[i]
  count3+=a[n-i-1]-a[n-i-2]
  b.append(count)
  d.append(count3)
for i in range(n-1):
  count2+=b[i+1]
  count4+=d[i+1]
  c.append(count2)
  e.append(count4)
ans=10**18
for i in range(n):
  ans=min(ans,c[-1]-c[i]-b[i]*(n-i-1)+e[-1]-e[n-i-1]-d[n-i-1]*i)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in 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:
def main():
    n = int(input())
    a = [int(s) for s in input().split()]
    print(solve(a))

def solve(a):
    n = len(a)
    b = [a[i] - i for i in range(n)]
    b.sort()

    c = b[n // 2]

    return sum(abs(bi - c) for bi in b)

main()

Submission status: Accepted

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

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(sum([abs(x - B[N//2]) for x in B]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
A=[int(x) for x in input().split()]
for i in range(N):
  A[i]=A[i]-1-i
A.sort()
if N==1:
  print(0)
else:
  b=A[N//2]
  c=A[(N//2)+1]
  ans1,ans2=0,0
  for i in range(N):
    ans1+=abs(A[i]-b)
    ans2+=abs(A[i]-c)
  print(min(ans1,ans2))

Submission status: Accepted

Solution code:
N = int(input())
a = [ int(x) for x in input().split() ]
b = [ a[i] - (i+1) for i in range(N) ]
b.sort()

print( sum([abs(x-b[N//2]) for x in b] ) )

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a=[-(i+1)+j for i,j in enumerate(a)]
a.sort()
if len(a)%2==0:
    tmp=len(a)//2
    b=(a[tmp]+a[tmp-1])//2
else:
    tmp=len(a)//2
    b=a[tmp]
print(sum(map(lambda x:abs(x-b),a)))

Submission status: Accepted

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

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

a = sorted(a)
med = a[n//2]

b1, b2, b3 = 0, 0, 0
for i in range(n):
  b1 += abs(a[i] - med - 1)
  b2 += abs(a[i] - med)
  b3 += abs(a[i] - med + 1)
  
print(min([b1, b2, b3]))

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()
C=[abs(B[i]-B[int((N-1)/2)]) for i in range(N)]
print(sum(C))

Submission status: Accepted

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

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

M.sort()

if N%2==0:
  p=int((M[int(N/2)-1]+M[int(N/2)])/2)
else:
  p=M[int((N+1)/2)-1] 

sum=0
for i in range(N):
  sum=sum+abs(M[i]-p)

  
print(sum)

Submission status: Accepted

Solution code:
import statistics
n = int(input())
x = [int(i) for i in input().split()]
x = [x_ - i for i, x_ in enumerate(x)]
median = statistics.median(x)
x = [abs(x_ - median) for x_ in x]
ans = int(sum(x))
print(ans)

Submission status: Accepted

Solution code:
from statistics import median as m;n=input();d=[i-h-1 for h,i in enumerate(list(map(int,input().split())))];k=int(m(d));print(sum([abs(i-k) for i in d]))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
for i in range(n):
  a[i] -= i
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())
H = list(map(int,input().split()))
h = []
for i in range(n):
    h.append(H[i]-(i+1))
h.sort()
M = h[n//2]
s = 0
for i in h:
    s += abs(i-M)
print(s)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split(" ")]
a = [a[i] - (i + 1) for i in range(0, n)]
a = sorted(a)

if n % 2 == 0:
    print(-1 * sum(a[0:n//2]) + sum(a[n//2:]))
else:
    print(-1 * sum(a[0:n//2]) + sum(a[n//2 + 1:]))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
for i in range(len(a)):
    a[i] -= i + 1
a.sort()
res = 10 ** 30
if n % 2 == 0:
    il = [n//2-1, n//2]
else:
    il = [n//2]
for i in il:
    total = 0
    for j in range(len(a)):
        total += abs(a[i] - a[j])
    res = min(res, total)
print(res)

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

test = False
if test:
    N = 2*10**5
    A = [i*2 for i in range(N)]
else:
    N = I()
    A = LI()

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

import statistics
b = statistics.median(A)
#  print('b', b)
result = 0
for a in A:
    result += abs(a-b)
print(int(result))

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)
s=0

for i in range(N):
    s=s+abs(C[i]-C[(N-1)//2])

print(s)

Submission status: Accepted

Solution code:
#from collections import Counter
import math
N=int(input())
A=list(map(int,input().split()))
l=[]
n=1
for i in A:
    l.append(i-n)
    n+=1
l.sort()
#中央値
#切り捨て
c=int(math.floor(N/2))

ans_l=[]
ans=0
for j in l:
    ans+=abs(j-l[c])

print(ans)

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

Submission status: Accepted

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

Bi = []
for i in range(N):
    Bi.append(Ai[i] - (i + 1))
Bi.sort()
b = Bi[len(Bi) // 2]
ans = 0
for i in range(N):
    ans += abs(Ai[i] - (b + i + 1))
print(ans)

Submission status: Accepted

Solution code:
import statistics
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:
    m=statistics.median(b)
    b=list(map(lambda x:abs(x-m),b))
    ans=0
    for i in range(n):
        ans+=b[i]
else:
    m1=b[n//2]
    m2=b[n//2+1]
    k=list(map(lambda x:abs(x-m1),b))
    l=list(map(lambda x:abs(x-m2),b))
    ans1=0
    ans2=0
    for i in range(n):
        ans1+=k[i]
        ans2+=l[i]
    ans=min(ans1,ans2)
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()
if N%2:
    b=B[N//2]
else:
    b=(B[N//2-1]+B[N//2])//2
ans=sum([abs(a-b) for a in 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()
if n == 1:
    print(0)
    exit()
p = a[n//2]
q = a[n//2 - 1]
res = 0
for e in a:
    res += abs(e-p)
ans = 0
for e in a:
    ans += abs(e-q)
print(min(res,ans))

Submission status: Accepted

Solution code:
# 中央値が最適値(数直線で考える)
N = int(input())
A = [int(i) for i in input().split()]
for i in range(len(A)):
    A[i] -= i+1
A.sort()
b = A[N // 2]
print(sum([abs(a-b) for a in A]))

Submission status: Accepted

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

b = []

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

b = sorted(b)

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

sum_num = 0
for b_ in b:
    sum_num += abs(b_-x)

print(sum_num)

Submission status: Accepted

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

ans = sum([abs(BB-b) for BB in B])
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

l = [l[i]-(i+1) for i in range(len(l))]

l.sort()

b = l[len(l)//2]
res = 0

for c in l:
    res += abs(c-b)
print(res)