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

Solution (Python):
N = int(input())
nums = input().split(" ")
nums2 = [int(x)-i-1 for i,x in enumerate(nums)]
nums2.sort()
length = len(nums2)
numpre = 0
same = 1
if length == 1:
  value = nums2[0]
 
for n,m in zip(nums2[:-1],nums2[1:]):
  if n == m:
    same += 1
  else:
    impact = same + numpre
    if impact > length-impact:
      value = n
      break
    numpre += same
    same = 1
  value = m
 
answer = 0
for i in nums2:
  answer += abs(i-value)
print(answer)

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

Solution (Python):
import numpy as np

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

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

b=np.median(AA)
ans=0

for a in AA:
    ans+=abs(a-b)
print(int(ans))

Solution (Python):

str_n = input()
n = int(str_n)
str_a = input()
arr_a = str_a.split(' ')

arr_ia = []
for i, item in enumerate(arr_a):
    arr_ia.append(int(item)-(i+1))

arr_ia.sort()
med = arr_ia[int(len(arr_ia)/2)]

score = 0
for n in arr_ia:
    score += abs(n-med)
    
print(score)

Solution (Python):
def run(n, a):
    a = [a[i]-i-1 for i in range(len(a))]
    a.sort()
    m = a[int((n-1)/2)]
    ret = 0
    for ai in a:
        ret += abs(ai - m)
    return ret


def read_line():
    n = int(input())
    a = list(map(int, input().split()))
    return (n, a)


def main():
    n, a = read_line()
    print(run(n, a))


if __name__ == '__main__':
    main()

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

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

ans = 0

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

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


b = sorted(a)
i = n // 2
what = b[i]
print(sum([abs(t - what) for t in b]))

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

b = [a[i]-i-1 for i in range(n)]
b.sort()
m = int(n//2)
c=[abs(b[i]-b[m]) for i in range(n)]
print(sum(c))

Solution (Python):
import statistics
N = int(input())
A = [int(x) for x in input().split(' ')]
def score(C, b):
    s = 0
    for i, Ci in enumerate(C):
        s += abs(Ci - b)
    return int(s)

C = [Ai - (i+1) for i, Ai in enumerate(A)]
b = statistics.median(C)
b1 = int(b)
b2 = int(b) + 1
s1 = score(C, b1)
s2 = score(C, b2)
print(min(s1, s2))

Solution (Python):
def getMedian(data):
    N = len(data)
    data.sort()
    if N % 2 == 0:
        median1 = N / 2
        median2 = N / 2 + 1
        median1 = int(median1) - 1
        median2 = int(median2) - 1
        return int((data[median1] + data[median2]) / 2)
    else:
        median = (N + 1) / 2
        median = int(median) - 1
        return int(data[median])


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

median = getMedian(B)

ans = 0

for b in B:
    ans += abs(b - median)

print(ans)

Solution (Python):
import math, statistics
n=int(input())
l=list(map(int, input().split()))
for i in range(n):
    l[i]-=(i+1)
b=statistics.median(l)
sad=0
for i in l:
    sad+=abs(i-b)
print(int(sad))

Solution (Python):
def calc(b,A,N):
    sadness = 0
    for i in range(N):
        sadness += abs(A[i] - (b + i))
    return sadness

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

k = []
for i in range(N):
    k.append(A[i] - i)

k = sorted(k)

sadness = 0
if N % 2 == 1:
    sadness = calc(k[N//2],A,N)
else:
    sadness = min(calc(k[N//2],A,N),calc(k[(N//2)+1],A,N))

print(sadness)

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

a_max = max(a)
a_min = min(a) - n

t = (a_min + a_max) // 2

while (a_min <= a_max):
    plus_minus = 0
    for i,data in enumerate(a):
        if data < t + i + 1:
            plus_minus -= 1
        elif data > t + i + 1:
            plus_minus += 1

    if (plus_minus == 0):
        break
    elif (plus_minus > 0):
        a_min = t + 1
    elif (plus_minus < 0):
        a_max = t - 1
    t = (a_min + a_max) // 2

kanasisa = 0
for i,data in enumerate(a):
    kanasisa += abs(data - (t + i + 1))

print(kanasisa)

Solution (Python):
import math
def inpl(): return list(map(int, input().split()))
N = int(input())
A = inpl()

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

if N%2 == 1:
    medR = A[N//2]
    medL = A[N//2]
else:
    medR = math.ceil((A[N//2-1]+A[N//2])/2)
    medL = (A[N//2-1]+A[N//2])//2
    
ansR, ansL = 0, 0
for i in A:
    ansR += abs(i-medR)
    ansL += abs(i-medL)

print(min(ansR,ansL))

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

tmp = []

for idx, e in enumerate(A):
    tmp.append(e - (idx + 1))

tmp.sort()

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

res = 0
for idx, e in enumerate(A):
    res += abs(e - (idx + 1) - b)

print(res)

Solution (Python):
import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())))
a = a - np.arange(n)
a = np.sort(a)
a = a - a[int(n/2)]
print(sum(abs(a)))

Solution (Python):
N = int(input())
A_list = [int(elem) for elem in input().split(' ')]
assert len(A_list) == N

modified_A_list = [A - i for i, A in enumerate(A_list, start=1)]

minus_A_list = sorted([A for A in modified_A_list if A < 0])[::-1]
zero_A_list = [A for A in modified_A_list if A == 0]
plus_A_list = sorted([A for A in modified_A_list if A > 0])


len_minus = len(minus_A_list)
len_zero = len(zero_A_list)
len_plus = len(plus_A_list)
assert len_minus + len_zero + len_plus == N
current_sum = abs(sum(minus_A_list)) + sum(plus_A_list)


if len_minus > len_plus + len_zero:
    i = 0
    old_num = 0
    while i < len(minus_A_list):
        current_num = minus_A_list[i]
        current_sum -= abs(current_num - old_num) * (len_minus - len_plus - len_zero)
        
        num_current_val = 0
        while i < len(minus_A_list) and (minus_A_list[i] == current_num):
            i += 1
            num_current_val += 1
        len_minus -= num_current_val
        len_zero_old = len_zero
        len_zero += num_current_val - len_zero_old
        len_plus += len_zero_old
        old_num = current_num
        if len_minus <= len_plus + len_zero:
            break

elif len_plus > len_minus + len_zero:
    i = 0
    old_num = 0
    while i < len(plus_A_list):
        current_num = plus_A_list[i]
        current_sum -= (current_num - old_num) * (len_plus - len_minus - len_zero)
        
        num_current_val = 0
        while i < len(plus_A_list) and plus_A_list[i] == current_num:
            i += 1
            num_current_val += 1
        len_plus -= num_current_val
        len_zero_old = len_zero
        len_zero += num_current_val - len_zero_old
        len_minus += len_zero_old
        old_num = current_num
        if len_plus <= len_minus + len_zero:
            break

print(current_sum)

Solution (Python):
from statistics import *



n = int(input())
list = input().split()

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

b = int(median(list))

for i in range(n):
    list[i] = abs(list[i] - b)

print(sum(list))

Solution (Python):
from statistics import median
import math
N = int(input())
*A, = map(int, input().split())
B = [A[i]-i for i in range(N)]
b = median(B)
bm = math.floor(b)
K = [x - bm for x in B]
KZ = [abs(x) for x in K]
Z = sum(KZ)
for i in range(20):
    C = [abs(x-i+10) for x in K]
    Z = min([sum(C),Z])
print(int(Z))

Solution (Python):
from decimal import *
N = int(input())
a = list(map(int, input().split()))
c = a.copy()
for i in range(len(a)):
    c[i] = a[i] - i - 1

c.sort()
if len(a) % 2 == 1:
    b = c[len(a) // 2]
else:
    b = (c[len(a) // 2] + c[len(a) // 2 - 1]) / 2

greef1 = 0
for i in range(len(a)):
    greef1 += abs(a[i] - i - 1 - b)
print(int(greef1))

Solution (Python):
def main():
    N = int(input())
    A = []
    data = input().split()
    for i in range(N):
        A.append(int(data[i]))
    C = [A[i] - i - 1 for i in range(N)]
    C.sort()
    m = N // 2
    x = C[m]
    left = sum([x - C[i] for i in range(m)])
    right = sum([C[i] - x for i in range(m + 1, N)])
    print(left + right)
    
if __name__ == "__main__":
    main()

Solution (Python):
import math
import statistics

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

b = [a[i]-(i+1) for i in range(n)]
median = statistics.median(b)

med1 = math.floor(median)
med2 = med1+1

t = sum([abs(i-med1) for i in b])
u = sum([abs(i-med2) for i in b])

print(min(t,u))

Solution (Python):
def main():
	N = int(input())
	seq = list(map(int, input().split()))
	seq = [seq[i] - i - 1 for i in range(N)]
	se = sorted(list(set(seq)))
	def helper(b):
		return sum([abs(seq[i] - b) for i in range(N)])
	L = 0
	R = len(se)
	while True:
		ind = (L + R) // 2
		temp = helper(se[ind])
		if helper(se[ind - 1]) > temp and temp > helper(se[ind + 1]):
			L = ind
		elif helper(se[ind - 1]) < temp:
			R = ind
		else:
			print(temp)
			return 0
main()

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

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

if n%2 ==0:
    kas = c[int(n/2)]
else:
    kas = c[int((n+1)/2)-1]



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

Solution (Python):
import numpy as np

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

if N % 2 == 0:
    C = int(N / 2)
else:
    C = int((N+1)/2)


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

A1 = np.array(A)

B = np.sort(A1)

if B[C-1] > 0:
    d = B[C-1]
    B2 = B - d
    print(sum(np.abs(B2)))
else:
    d = -B[C-1]
    B2 = B + d
    print(sum(np.abs(B2)))

Solution (Python):
N = int(raw_input())
A = map(int, raw_input().split())
d = []
for i in range(N):
  d.append(A[i]-(i+1))
if N%2==0:
  B = sorted(d)[N//2-1:N//2+1]
else:
  B = [sorted(d)[N//2]]
r = []
for b in B:
  s = 0
  for i in range(N):
    s += abs(A[i]-(b+i+1))
  r.append(s)
print min(r)

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

a.sort()
b = a[n//2]
a = list(map(lambda x: abs(x-b), a))
print(sum(a))

Solution (Python):
import sys

N = int(raw_input())
A = [int(x)-(i+1) for i,x in enumerate(raw_input().strip().split())]
A.sort()
medians = []
if len(A)%2==1:
    medians.append(A[len(A)/2])
else:
    medians.append(A[len(A)/2])
    medians.append(A[len(A)/2 -1])

result = sys.maxint
for m in medians:
    temp = sum(abs(a-m) for a in A)
    result = min(result, temp)

print result

Solution (Python):
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]

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

print(sum)

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

A.sort()


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

print(S)

Solution (Python):
if __name__=="__main__":
  N = int(input())
  A = list(map(int, input().split()))
  B = [A[i]-(i+1) for i in range(N)] 
  sortedB = sorted(B)
  optB = sortedB[int(N/2)]
  print(sum([abs(value-optB) for value in sortedB], 0))

Solution (Python):
n=int(input())
a=[int(i) for i in input().split()]
c=0
d=[]
for i in range(n):
    d.append(a[i]-i-1)
d.sort()

if n%2==1:
    b=d[int((n+1)/2)-1]
else:
    b=int(((d[int(n/2-1)]+d[int(n/2)]))/2)
for i in range(n):
    c=c+abs(a[i]-b-i-1)

print(c)

Solution (Python):
from inspect import currentframe

def chkprint(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

from functools import reduce
from math import floor, ceil

N = int(input())
A = list(map(lambda s: int(s[1])-s[0]-1, enumerate(input().split())))

A.sort()

if N%2 == 0:
  m0 = N//2
  m1 = m0 - 1
  a0 = floor((A[m0] + A[m1])/2)
  a1 = ceil((A[m0] + A[m1])/2)
  
  

  print(min(reduce(lambda s, x: s + abs(x - a0), A, 0), reduce(lambda s, x: s + abs(x - a1), A, 0)))
else:
  m = N//2
  a = A[m]
  
  print(reduce(lambda s, x: s + abs(x - a), A, 0))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a = [x-i-1 for i,x in enumerate(a)]

a = sorted(a)

med1 = a[len(a)//2]
med2 = a[len(a)//2 - 1]



sum1 = sum([abs(x - med1) for x in a])
sum2 = sum([abs(x - med2) for x in a])
print(min(sum1, sum2))

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
for i in range(n):
	a[i] = a[i] - i - 1
a.sort()


c = n // 2
b = a[c]

sum = 0

for i in range(n):
	if i <= c:
		sum += b - a[i]
	else:
		sum += a[i] - b

print(sum)

Solution (Python):
def main():
    n = int(input())
    ai = [int(i) for i in input().split()]

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

    ai.sort()

    b = ai[n//2]
    m = sum([abs(i - b) for i in ai])
    print(m)
        
    
if __name__ == '__main__':
    main()

Solution (Python):
if __name__ == '__main__':
    n = int(input())

    a = [int(i) for i in input().split()]
    for i in range(n):
        a[i] -= i;

    a.sort()

    m = n // 2

    ans = 0
    for i in a:
        ans += abs(i - a[m])

    print(ans)

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

Solution (Python):
from statistics import median

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

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

median = round(median(A))

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

print(ans)

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

c = [a[i] - (i+1) for i in range(0, n)]
c.sort()
b = c[int(n/2)]
print(sum((abs(c[i] - b) for i in range(0, n))))

Solution (Python):
import numpy as np
n = int(input())
a = list(map(int,input().split()))
r = np.arange(n) + 1
d = a - r
b = int(np.ceil(np.median(d)))
print(np.sum(np.abs(d - b)))

Solution (Python):
n=int(input())
a0=input().split()
a=[]
for i in range(n):
	a.append(int(a0[i])-i)
a.sort()
j=0
for i in range(n):
	j+=abs(a[i]-a[n//2])
print(j)

Solution (Python):
import numpy as np
import math

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

B = A - np.arange(1, N + 1)
m = np.median(B)
print(int(np.abs(B - m).sum()))

Solution (Python):
from statistics import median

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

ys = [x-i-1 for i, x in enumerate(xs)]
m = int(median(ys))

print(sum(abs(y-m) for y in ys))

Solution (Python):
N = int(input())
A = [int(_) for _ in input().split()]



xs = sorted(a - i - 1 for i, a in enumerate(A))

c = xs[len(xs)//2]

r = 0
for x in xs:
    r += abs(x - c)

print(r)