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):
import math
import sys
import queue
from collections import Counter
from itertools import accumulate
from fractions import gcd
from functools import reduce

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

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

mod = 1000000007

"""


    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())


    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

if __name__ == "__main__":
    N = int(sys.stdin.readline())
    L = list(map(int, sys.stdin.readline().split()))
    L2 = [L[i] - (i + 1) for i in range(N)]
    L2.sort()
    if N % 2 == 0:
        b = L2[(N // 2) - 1]
    else:
        b = L2[(N // 2)]

    print(sum(abs(l - b) for l in L2))

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

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



A = sorted(A)

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

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

print(ans)

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

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

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

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

print(ans)

Solution (Python):

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

Solution (Python):
import sys
from collections import deque
from functools import reduce
import copy


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    nums = string_to_int(inputs[0])
    N = len(nums)
    for i in range(N):
        nums[i] -= (i+1)
    nums.sort()
    total = reduce(lambda x, y: x + y, nums, 0)
    half = N // 2
    sub = nums[half]
    total = reduce(lambda acc, x: acc + abs(x - sub), nums, 0)
    return total


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    input()
    ret = solve(inputs(1))
    print(ret)

Solution (Python):
def main():
    N = int(input())
    A = input().split()
    B = [int(A[i])-(i+1) for i in range(len(A))]
    B = sorted(B)

    m = len(B)
    prefix = [0]
    for i in range(m):
        prefix.append(prefix[-1]+B[i])

    min_v = float('inf')
    for i in range(m):
        b = B[i]
        v = -b*(N-2*i)
        v += prefix[-1] - prefix[i]*2
        min_v = min(min_v, v)
    return min_v

if __name__ == '__main__':
    print(main())

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A_ = []
result = 0

for i, a in enumerate(A):
    A_.append(a - i - 1)

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

for a_ in A_:
    result += abs(a_ - b)

print(result)

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

if n%2==1:
    b=a[int(n*0.5)]
    ans=sum([abs(x-b) for x in a])
else:
    b1=a[int(n*0.5)]
    b2=a[int(n*0.5)-1]
    ans1=sum([abs(x-b1) for x in a])
    ans2=sum([abs(x-b2) for x in a])
    ans=min(ans1, ans2)

print(ans)

Solution (Python):


import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

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

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

if __name__ == '__main__':
    main()

Solution (Python):


import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

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

    if n % 2 == 0:
        b = (al[(n-1)//2] + al[n//2])//2
    else:
        b = al[(n-1)//2]
    ans = sum([abs(a - b) for a in al])
    print(ans)

if __name__ == '__main__':
    main()

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

dist = []

for i in range(N):
    dist.append(A[i] - (i + 1))

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

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

print(ans)

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]
B = [a - i - 1 for i, a in enumerate(A)]
C = sorted(B)
m = C[N // 2]
D = [c - m for c in C]
print(sum([abs(d) for d in D]))

Solution (Python):
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = sorted([ai - (i + 1) for i, ai in enumerate(a)])
    b_center = b[n // 2]
    return sum([abs(bi - b_center) for bi in b])


if __name__ == "__main__":
    print(solve())

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

m = [0]*n

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

m.sort()
if n%2 == 0:
  p = n//2-1
else:
  p = (n-1)//2

ans = 0
for j in range(n):
  ans += abs(m[j] - m[p])

print(ans)

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

Solution (Python):
from statistics import median

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [0] * N

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

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

    print(sumB)


main()

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

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


a.sort()

if(n%2 == 1):
  b = a[int(n/2)]

else:
  t = 0
  for i in a:
    t += abs(i)
  ave = t/n

  p = int(n/2)
  if(abs(a[p] - ave) <= abs(a[p-1] -ave)):
    b = a[p]
  else:
    b = a[p-1]

k = list(map(lambda x:abs(x-b),a))

print(sum(k))

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

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

A.sort()

import math

if N % 2 == 1:
    a = A[N // 2]
else:
    a = (A[(N // 2) - 1]+ A[(N // 2)]) // 2




ans = sum([abs(x - a) for x in A])
print(ans)

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

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


def f(b):
    return sum([abs(a-b)for a in aa])

print(f(aa[n//2]))

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

Solution (Python):
from statistics import median

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

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

def calc_score(b):
    score = 0
    for a in A_star:
        score += abs(a - b)
    return score

print(calc_score(int(median(A_star))))

Solution (Python):
from statistics import median

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

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

def calc_score(b):
    score = 0
    for a in A_star:
        score += abs(a - b)
    return score

def decide_direction(b):
    score0 = calc_score(b)
    score1 = calc_score(b + 1)
    if score0 > score1:
        return 1
    else:
        return -1

b = int(median(A_star))
direction = decide_direction(b)
pre_score = calc_score(b)

while True:
    b += direction
    score = calc_score(b)
    if score >= pre_score:
        print(pre_score)
        break
    else:
        pre_score = score

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
B=[a-i for i,a in enumerate(A)]
b=sorted(B)[N//2]
print(sum([abs(bb-b) for bb in B]))

Solution (Python):
import statistics

N = int(input())
lst = list(map(int, input().split()))
update_lst = [lst[i] - (i+1) for i in range(len(lst))]
median = statistics.median(update_lst)
ans = [abs(i - median) for i in update_lst]
print(int(sum(ans)))

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

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

A.sort()


















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

Solution (Python):
from math import floor,ceil
N = int(input())
a_list = list(map(int,input().split()))

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

a_list.sort()

b = a_list[N//2]

diff = 0
for a in a_list:
    diff += abs(b-a)
print(diff)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
total = 0
for i in range(n):
    a[i] = a[i] - (i + 1)
if n == 1:
    print(0)
    exit()
a.sort()
if n % 2 == 0:
    ave = a[int(n/2)]
    for i in range(n):
        total += abs(a[i] - ave)
    print(total)
else:
    total2 = 0
    ave = a[int(n/2)]
    for i in range(n):
        total += abs(a[i] - ave)
    ave = a[int((n + 1)/2)]
    for i in range(n):
        total2 += abs(a[i] - ave)
    if total2 >= total:
        print(total)
    else:
        print(total2)

Solution (Python):
import itertools
import collections

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

n = getint()
a = getints()

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

a = list(sorted(a))
mid = a[n//2]

res = 0
for i in range(n):
    res += abs(a[i]-mid)

print(res)

Solution (Python):

import numpy as np
import statistics
import collections
N = int(input())
A = list(map(int, input().split()))
B = np.array(range(1, N+1))
A = np.array(A)
C = A - B
b = np.median(C)
print(int(np.sum(abs(C - b))))

Solution (Python):
N = int(input())
A = list(map(int, 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(a - b)
print(ans)

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

B.sort()

if len(A)%2==1:
    for i in range(N):
        total+=abs(A[i]-(B[len(B)//2]+i+1))
        
else:
    for i in range(N):
        total+=abs(A[i]-(B[len(B)//2]+i+1))
print(total)

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

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

val = []

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

val.sort()



idx = []
cnt = 1
for i in range(n-1):
    if val[i] == val[i+1]:
        
        if i == n-2:
            idx.append((val[i+1],i+2))
        continue
    else:
        if i == n-2:
            idx.append((val[i],i+1))
            idx.append((val[i+1],i+2))
        else:
           idx.append((val[i],i+1)) 
        
        
ans_val = 0
ans2_val = 0
ans3_val = 0

flag2 = False
flag3 = False

for i in range(len(idx)):
    if idx[i][1] >= (n+1) // 2:
        ans_val = idx[i][0]
        """
        
        if i-1 >= 0:
            flag2 = True
            ans2_val = idx[i-1][0]
        
        if i+1 <= len(idx)-1:
            flag3 = True
            ans3_val = idx[i+1][0]
        """
        break



     
ans = 0
ans2 = 10**20
ans3 = 10**20
for i in range(n):
    ans += abs(a[i]-ans_val-i)
    if flag2 == True:
        ans2 += abs(a[i]-ans2_val-i)
    if flag3 == True:
        ans3 += abs(a[i]-ans3_val-i)
    


print(ans)

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

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

Solution (Python):
from sys import stdin
import statistics
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
data = [0] * len(A)

for ind, i in enumerate(A):
    data[ind] = i - (ind+1)

med = statistics.median(data)

ans = 0

for  j in data:
    ans += abs(j - med)
    
print(int(ans))

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

l = [l[x]-(x+1) for x in range(n)]
l.sort()

b = l[n//2]

l = [abs(l[x]-b) for x in range(n)]

print(sum(l))

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
B=[]
for k in range(N):
  B.append(A[k]-k-1)
B=sorted(B)
if N%2==0:
  b=(B[N//2]+B[-1+N//2])//2
else:
  b=B[N//2]
ans=0
for k in range(N):
    ans+=abs(A[k]-b-k-1)
print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
B = [it - (idx + 1) for idx, it in enumerate(A)]
S = []

B.sort()
if N%2 == 1:
    b = B[(N-1)//2]
else:
    b = (B[(N-1)//2] + B[(N-1)//2 + 1]) // 2
    
S = sum([abs(i-b) for i in B])
    
print(S)

Solution (Python):
n=input()
num=list(map(int,input().split()))
sorted_num=sorted([num[i]-i for i in range(len(num))])

b=sorted_num[len(sorted_num)//2]
print(sum([abs(b-i) for i in sorted_num]))

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

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

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

print(ans)

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

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

lst.sort()
if n%2 == 0:
    k = n//2
    b = (lst[k] + lst[k-1])/2
else:
    k = (n-1)//2
    b = lst[k]

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

print(int(ans))

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

b = np.median((A - np.arange(1, N+1)))
ans = np.abs(A - b - np.arange(1, N+1)).sum()

print(int(ans))

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

b = np.median((A - np.arange(1, N+1)))
ans = np.inf
for i in [b-1, b, b+1]:
    ans = min(np.abs(A - i - np.arange(1, N+1)).sum(), ans)

print(int(ans))

Solution (Python):
n,*l=map(int,open(0).read().split())
a=sorted([l[i]-i-1for i in range(n)])
f=lambda x:sum(abs(l[i]-i-1-x)for i in range(n))
print(min(f(a[n//2]),f(a[n//2+(n>1)])))

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

lst = list()
for i, a in enumerate(A):
    lst.append(a - i - 1)

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

ans = sum([abs(e - b) for e in lst])
print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
B = [A[i]-i-1 for i in range(N)]
B.sort()
C = sorted(B,reverse = True)
s = 0
for i in range(N):
    if B[i] > C[i]:
        s += B[i]-C[i]
print(s)

Solution (Python):
n = int(input())
a = sorted(list(map(lambda s: int(s[1]) - s[0], zip(range(n), input().split()))))
print(sum(abs(s - a[n // 2]) for s in a))

Solution (Python):
import statistics
n=int(input())
l=list(map(int,input().split()))
l=[l[i]-(i+1) for i in range(n)]
a=statistics.median_low(l)
b=0
if n%2==0:b=statistics.median_high(l)
print(min(sum([abs(i-a) for i in l]),sum([abs(i-b) for i in l])))

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

Solution (Python):
import numpy as np

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

arr.sort()

mean=int(sum(arr)/n)
mid1=arr[n//2]
mid2=arr[(n-1)//2]

ans = [0,0,0]

for i in range(n):
    ans[0] += abs(arr[i]-mean)
    ans[1] += abs(arr[i]-mid1)
    ans[2] += abs(arr[i]-mid2)

print(int(min(ans)))

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

for i in range(n):
    li[i] -= i

import statistics
import math
a = math.floor(statistics.median(li))
b = math.ceil(statistics.median(li))

num_a,num_b = 0,0
for i in range(n):
    num_a += abs(li[i]-(a))
    num_b += abs(li[i]-(b))
print(min(num_a,num_b))

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

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

soretedAlist = sorted(A_list)




result =0
for a in soretedAlist:
    result += abs(a - soretedAlist[N//2])
print(result)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
tmp = sorted([A[i-1]-i for i in range(1,N+1)])
B = tmp[N//2]
print(sum([abs(t-B) for t in tmp]))

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

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


buff = math.ceil(sum(A)/N)
buff2 = sum(A)//N
buff3 = sum(A)//N-1
A.sort()
buff3 = A[N//2]
ans = 0
for i in range(N):
    ans += abs(A[i]-buff)

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

ans3 = 0
for i in range(N):
    ans3 += abs(A[i]-buff3)
print(min(ans, min(ans2, ans3)))

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

res = 0
if N%2 == 1:
    b = S[(N-1)//2]
    for i in range(N):
        res += abs(B[i]-b)
else:
    medint1 = N//2
    medint2 = N//2-1
    med1 = S[medint1]
    med2 = S[medint2]
    t1 = 0
    t2 = 0
    for i in range(N):
        t1 += abs(B[i]-med1)
        t2 += abs(B[i]-med2)
    res = min(t1,t2)
print(res)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= i+1
b = sorted(a)
center1 = b[n//2]
center2 = 0
if not n == 1:
    center2 = b[n//2+1]
buf1 = 0
buf2 = 0
for i in range(n):
    buf1 += abs(b[i]-center1)
    buf2 += abs(b[i]-center2)
print(int(min(buf1, buf2)))

Solution (Python):
from functools import reduce
import math
import collections

def main():
    
    
    
    

    
    
    
    
    
    

    
    

    
    
    
    
    
    
    
    
    
    INF = float("inf")

    
    MOD = 10**9+7
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    N = int(input())
    A = list(int(_) for _ in input().split())
    A_fixed = []
    for i in range(N):
        A_fixed.append(A[i]-i-1)
    cnt = 0
    A_fixed.sort()
    b = A_fixed[N//2]
    for i in range(N):
        cnt += abs(b-A_fixed[i])
    
    
    print(cnt)    
    
if __name__ == '__main__':
    main()

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

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

Solution (Python):
import math

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:
  median_l = B[N//2-1]
  median_r = B[N//2]
  ans_l = 0
  ans_r = 0
  for i in range(N):
    ans_l += abs(A[i]-(median_l+i+1))
    ans_r += abs(A[i]-(median_r+i+1))
  print(min(ans_l, ans_r))
else:
  median = B[N//2]
  ans = 0
  for i in range(N):
    ans += abs(A[i]-(median+i+1))
  print(ans)

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

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

Solution (Python):


N = int(input())
A = list(int(s) for s in input().split())
ami = [A[i] - i - 1 for i in range(N)]
ami.sort()
b = ami[N // 2]
print(sum(abs(v - b) for v in ami))

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

A.sort()

if N % 2 != 0:
    T = A[N//2]
else:
    T = (A[N//2-1] + A[N//2])//2

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

Solution (Python):
from math import floor, ceil
N = int(input())
A = []
for i,a in enumerate(input().split()):
  A.append(int(a)-(i+1))
A.sort()
if N % 2 :
    print(-1*sum(A[:N//2]) + sum(A[N//2+1:]))
else:
    print(-1*sum(A[:N//2]) + sum(A[N//2:]))

Solution (Python):
import math

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

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

def sad(A,a):
    sadness=0
    for i in range(N):
        sadness+=abs(A[i]-A[a])
    return sadness

if N%2==0:
    ans=min(sad(A,a),sad(A,a+1))
else:
    ans=sad(A,a)
print(ans)

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

total = 0
for i in range( n):
    total += (dat[i] - (i+1))
    dat_d.append(dat[i] - (i+1))







dat_d.sort()

f = dat_d[n//2]

total = 0
for i in range( n):
    total += abs(dat_d[i] - f)

print(total)

Solution (Python):
N = int(input())
A = [int(s) for s in input().split()]
ami = [A[i] - i - 1 for i in range(N)]
ami.sort()
b = ami[N // 2]
print(sum(abs(v - b) for v in ami))

Solution (Python):


N = int(input())
A = [int(x) for x in input().split()]
A_prime = [0]*N
for i in range(N):
    A_prime[i] = A[i] - i-1
A_prime = sorted(A_prime)
center = A_prime[N//2]

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

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]
for i in range(N):
    A[i] -= (i+1)
A.sort()
if N%2 == 0:
    b = A[int(N*0.5)]
else:
    b = A[int((N-1)*0.5)]
ans = 0
for j in range(N):
    ans += abs(A[j]-b)
print(int(ans))

Solution (Python):
N = int(input())
A = map(int, input().split())
modified_A = []
for i, a in enumerate(A):
    modified_A.append(a - i - 1)

modified_A = sorted(modified_A)

min_sorrow = 1000000000000000
passed_A = 0
sum_A = sum(modified_A)
for i, a in enumerate(modified_A):
    passed_A += a
    sorrow = (2 * (i+1) - N) * a + sum_A - 2 * passed_A
    
    if sorrow < min_sorrow:
        min_sorrow = sorrow
print(min_sorrow)

Solution (Python):


import sys
def input(): return sys.stdin.readline().rstrip()
import heapq
INF = float("inf")
def mi(): return map(int, input().split())
def ii(): return int(input())


def custom_round(number, ndigits=0):
  if type(number) == int: 
    return number
  d_point = len(str(number).split('.')[1]) 
  if ndigits >= d_point:
    return number
  c = (10 ** d_point) * 2
    
  return round((number * c + 1) / c, ndigits)
    

N = ii()
As = list(mi())

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

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

ans = 0
for a in As:
  ans += abs(median - a)
  
print(ans)

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

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

arr = sorted(arr)
diff = 0
for j in range(N//2):
    diff+=abs(arr[N-j-1]-arr[j])
    
print(diff)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a_mi = sorted([a[i] - i - 1 for i in range(n)])
if n % 2 == 0:
    ans1 = [abs(i - a_mi[int(n / 2)]) for i in a_mi]
    ans2 = [abs(i - a_mi[int(n / 2) + 1]) for i in a_mi]
    print(min(sum(ans1), sum(ans2)))
else:
    print(sum([abs(i - a_mi[int((n - 1) / 2)]) for i in a_mi]))

Solution (Python):
N=int(input())

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

if N==1:
    print(0)
    exit()
elif N==2:
    B=[A[0]-1,A[1]-2]
    b=sum(B)//2
else:
    B=[]
    for i in range(N):
        B.append(A[i]-(1+i))
    
    B.sort()
    
    b=B[N//2]

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

Solution (Python):
from operator import sub

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

b = list(map(sub, a, range(1, N + 1)))
b.sort()
mb = b[N // 2]
print(sum(map(lambda x: abs(x - mb), b)))

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

Solution (Python):
import statistics
N = int(input())
a = [int(i) for i in input().split()]
ans = 0

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

b = statistics.median(a)
for i in range(N):
  ans += abs(a[i]-b)
print(int(ans))

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

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

sort_b = sorted(b)
num = sort_b[n // 2]

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

print(ans)

Solution (Python):
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:
    b=B[N//2]
else:
    b=(B[N//2]+B[N//2-1])//2
ans=0
for k in B:
    ans+=abs(k-b)
print(ans)

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

A.sort()
i = n/2
a = A[math.floor(i)]
b = A[math.ceil(i)] if i>1 else a
ans,ans1=0,0
for i in A:
    ans += abs(i-a)
    ans1 += abs(i-b)
print(min(ans,ans1))

Solution (Python):

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

Solution (Python):

def main():
    n = int(input())
    A = tuple(map(int, input().rstrip().split()))
    A = sorted(j - i for i, j in enumerate(A, start=1))
    b = A[n // 2]
    ans = sum(abs(a - b) for a in A)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from statistics import median


def main():
    n = int(input())
    A = tuple(map(int, input().rstrip().split()))
    A = tuple(j - i for i, j in enumerate(A, start=1))
    b = median(A)
    ans = sum(abs(a - b) for a in A)
    print(int(ans))


if __name__ == "__main__":
    main()

Solution (Python):



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

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

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

Solution (Python):
import numpy as np
import statistics as stats

n=int(input())
x=list(map(int,input().split()))
x1=list(range(1,n+1))
x2=list(map(lambda a,b: a-b, x,x1))
b=round(stats.median(x2))
x3=[b]*n
x4=list(map(lambda a,b: a-b, x2,x3))
x5=np.abs(x4)
res=sum(x5)
print(res)

Solution (Python):
n = int(input())
lst_a = list(map(int, input().split()))
lst_x = [a - i - 1 for i, a in enumerate(lst_a)]
lst_x.sort()
b = lst_x[n // 2]
ans = sum(abs(x - b) for x in lst_x)
print(ans)

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)
ans = float('inf')
l = 0
r = sum(c)
for i in range(N):
    b = c[i]
    l += c[i]
    r -= c[i]
    tmp = b*((i+1) - (N - i - 1)) + r - l
    if tmp < ans:
        ans = tmp
print(ans)

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

Solution (Python):
from collections import Counter
from statistics import median
N = int(input())
a_lis = list(map(int, input().split()))

new_lis = [item - i - 1 for i, item in enumerate(a_lis)]

mode = median(new_lis)

count = 0
for i in range(N):
    count += abs(a_lis[i] - mode - i - 1)
    
print(int(count))

Solution (Python):
n = int(input())
l = list(map(int, input().split()))
k = []
for i in range(len(l)):
    k.append(l[i] - i - 1)
k.sort()
if len(k) % 2 == 0:
    middle = len(k) // 2
    median = (k[middle - 1] + k[middle]) / 2
else:
    middle = len(k) // 2
    median = (k[middle])
ans = 0
for j in range(n):
    ans += abs(l[j] - (median + j + 1))
print(int(ans))

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
B=sorted([A[j]-j-1 for j in range(N)])

def median(seq):
    s = sorted(seq)
    if len(s) % 2 == 0:          
        return (s[len(s) // 2] + s[(len(s) // 2) - 1]) / 2
    else:
        return s[len(s) // 2]    

b=median(B)

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

print(int(ans))

Solution (Python):
import numpy as np

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

b = [a[i] - i for i in range(N)]
median = np.median(b)

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

print(ans)

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
B=sorted([A[j]-j-1 for j in range(N)])

def median(seq):
    s = sorted(seq)
    if len(s) % 2 == 0:          
        return (s[len(s) // 2] + s[(len(s) // 2) - 1]) / 2
    else:
        return s[len(s) // 2]    

b=median(B)

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

print(int(ans))

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

b = []
for i, a in enumerate(A):
	b += [a - i]
b.sort()



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

if 0 == N % 2:
	b1, b2 = b[N // 2 - 1], b[N // 2]
	print(min(solve(b1), solve(b2)))
else:
	b1 = b[N // 2]
	print(solve(b1))

Solution (Python):
N=int(input())
a=list(map(int,input().split()))
a=[a[i]-i for i in range(N)]
from statistics import median
m=int(median(a))
print(sum([abs(b-m) for b in a]))

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

Solution (Python):

N = int(input())

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

ans = 0


for i in range(N):

    A[i] -= i + 1

A.sort()



if N % 2 != 0:

    kz = A[ N // 2 ]

elif A[N // 2] - A[N // 2 - 1] > 1:
    kz = A[ N // 2 ] - 1

else:
    kz = A[ N // 2 ]


for i in A:

    i -= kz

    if i < 0:
        ans -= i
    else:
        ans += i

print (ans)

Solution (Python):
n = int(input())
a_list = [int(s) - i for i, s in enumerate(input().split())]

a_list.sort()
center = a_list[len(a_list) // 2]

ans = 0
for a in a_list:
    ans += abs(a - center)
print(ans)

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

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

chuoh=0
count=0
count2=0
if n%2==1:
    chuoh=b[int(n/2)]
    for i in range(n):
        count+=abs(a[i]-chuoh-i-1)
else:
    chuoh=b[int(n/2)]
    for i in range(n):
        count+=abs(a[i]-chuoh-i-1)
    chuoh=b[int(n/2)-1]
    for i in range(n):
        count2+=abs(a[i]-chuoh-i-1)
    count=min(count, count2)

print(count)