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 statistics
n=int(input())
a=list(map(int,input().split()))
for i in range(len(a)):
    a[i]-=i
x=0
m=statistics.median(a)
for i in a:
    x+=abs(i-m) 
print(int(x))

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

a = [i - 1 - ind for ind, i in enumerate(a)]
a.sort()
b = a[len(a)//2]
ans = sum([abs(i - b) for i in a])
print(ans)

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

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

Solution (Python):
N=int(input())
A=[int(i) for i in input().split(' ')]
for i in range(len(A)):
  A[i]-=i+1
A.sort()
if len(A)%2==1:
  b=A[(len(A)-1)//2]
else:
  b=A[(len(A))//2-1]
s=0
for i in range(len(A)):
  s+=abs(A[i]-b)
print(s)

Solution (Python):
import numpy as np

N = int(input())
A = list(map(int, input().split()))
A = np.array([A[i] - i for i in range(N)])
b = np.median(A)
sadness = np.sum(np.abs(A - b))
print(int(sadness))

Solution (Python):
def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    B = [a[i]-i-1 for i in range(len(a))]
    B.sort()
    ans = 0
    for i,aa in enumerate(a):
        ans+=abs(aa-(i+1)-B[len(B)//2])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math

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

B = sorted(A2)

b = B[int(N/2)]


A3 = [abs(a - b) for a in A2]

print(sum(A3))


sys.exit(0)

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

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

middle = alist[N//2]
al = [abs(i-middle) for i in alist]
print(sum(al))

Solution (Python):
import math
n = int(input())
lis = list(map(int,input().split()))
if n == 1:
  print("0")
  exit()
for i in range(n):lis[-(i+1)] += i
lis.sort()
cou = 0
co = 0
num = lis[math.ceil(n/2)]
nu = lis[math.floor(n/2)]
for i in range(n):
  cou += abs(lis[i]-num)
  co += abs(lis[i]-nu)
print(min(cou,co))

Solution (Python):
n = int(input())
list_a = list(map(int, input().split()))
list_123 = []
for i in range(n):
    list_123.append(i+1)
list_dif = [0]*n
for i in range(n):
    list_dif[i] = list_a[i] - list_123[i]
list_dif_sorted = sorted(list_dif)
med = list_dif_sorted[n//2]
ans = 0
for i in range(n):
    ans += abs(list_dif[i] - med)
print(ans)

Solution (Python):


def main():
    n = int(input())
    ai = list(map(int, input().split()))
    assert len(ai) == n

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

    ai = sorted(ai)
    b = ai[(n - 1) // 2]

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

    print(mi)

main()

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

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

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

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

print(sum(map(lambda x:abs(x-b),A)))

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

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

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

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

print(sum([abs(A - b) for A in As]))

Solution (Python):

n = int(input())
a = []
for i,x in enumerate(input().split()):
    x = int(x)
    a.append(x-(i+1))
a = sorted(a)

if n%2==0:
    b = a[n//2-1]
else:
    b = a[n//2+1-1]

ret = 0
for x in a:
    ret += abs(x-b)
print(ret)

Solution (Python):
import numpy

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

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

mid = int(numpy.median(A))


def f(m):
    ret = 0
    for a in A:
        ret += abs(a - m)
    return ret


print(f(mid))

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N = int(input())
aa = inpl()
for i in range(N):
	aa[i] -= i+1

aa.sort()

if N%2 == 1:
	mid = aa[N//2]
else:
	mid = (aa[N//2]+aa[N//2-1])//2

ans = 0
for a in aa:
	ans += abs(mid-a)

print(ans)

Solution (Python):
N = int(raw_input())
nums = list(map(int,raw_input().split()))
lo = -pow(10,9)
hi = pow(10,9)

def f(cur):
    res = 0
    for i in range(N):
        res += abs(nums[i]-(cur+i+1))
    return res

ans = pow(10,15)

while lo<=hi:
    mid = (lo+hi)/2
    t1,t2 = f(mid),f(mid+1)
    ans = min(ans,t1,t2)
    if t1>t2:
        lo = mid+1
    else:
        hi = mid-1

print ans

Solution (Python):
n=int(input())
list=[int(x) for x in input().split()]
suma=0
asum=0
for k in range(n):
    list[k]-=k
list.sort()
suma=list[(1+n)//2-1]
for k in list:
    asum+=abs(suma-k)
print(asum)

Solution (Python):
from statistics import median

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

aa = list(map(lambda e: e[1] - (e[0] + 1), enumerate(a)))
minb = median(aa)


ans = int(sum(map(lambda ea: abs(ea - minb), aa)))

print(ans)

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

Solution (Python):
from sys import stdin
import numpy as np

N = stdin.readline().rstrip()
A = np.array([int(x) for x in stdin.readline().split()], dtype=int)
B = np.sort(A - np.arange(1, len(A) + 1))
b = B[len(B) // 2]
print(np.abs(B - b).sum())

Solution (Python):
N = int(input())
M = N // 2
X = list(map(int, input().split()))
A = sorted([X[i] - (i + 1) for i in range(N)])
if N == 1:
    print(0)
else:
    print(sum(A[-M:]) - sum(A[:M]))

Solution (Python):
import math
def main():
  N = int(input())
  t = input().split(" ")
  a = []
  for i in range(N):
    ii = int(t[i])
    a.append(ii-i-1)
  a.sort()
  if N % 2 == 0:
    t = (a[N//2-1] + a[N//2])//2
  else:
    t = a[(N-1)//2]
  b = 0
  c = 0
  for i in range(N):
  	b += abs(a[i] - t)
  	c += abs(a[i] - t - 1)
  if c < b:
    print(c)
  else:
    print(b)
main()

Solution (Python):
N = int(input())
As = sorted([int(a)-i for i, a in enumerate(input().strip().split(' '))])

temp1 = 0
temp2 = sum(As)
for i, a in enumerate(As):
    temp1 += As[i]
    temp2 -= As[i]
    r = As[i] * (i+1) - temp1 +\
    temp2 - As[i] * (N-1-i)
    result = min(result, r) if i != 0 else r
print(result)

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

B = []

for i, a in zip(range(1, n+1), A):
    B.append(a-i)

B.sort()
m = B[n//2]

ans = 0

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

print(ans)

Solution (Python):


import statistics


in_cnt = int(input())
in_data = [int(i) for i in input().split()]

corrent_data = [0 for i in range(in_cnt)]
for idx in range(in_cnt):
	corrent_data[idx] = in_data[idx] - idx - 1

med_low = statistics.median_low(corrent_data)

ans=0
for idx in range(in_cnt):
	ans += abs( med_low - corrent_data[idx] )

print(ans)

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

from statistics import median
A = [a - i - 1 for i, a in enumerate(A)]
m = int(median(A))

print(sum(abs(a - m) for a in A))

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

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

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

median = sorted([x-i-1 for i, x in enumerate(data)])[n // 2]

ans = sum([abs(x-(median + i+1)) for i, x in enumerate(data)])
print(ans)

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

def main():
    N, A = read()
    B = [0 for _ in range(N)]
    for i in range(N):
        B[i] = A[i] - (i+1)
    B.sort()
    if N % 2 == 1:
        b = B[int((N-1)/2)]
    else:
        bl = B[int(N/2) - 1]
        br = B[int(N/2)]
        b = int((bl + br) / 2)

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


main()

Solution (Python):
from statistics import median

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

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

med = int(median(A))
    
ans = 0
for i in A:
    ans += abs(i-med)

print(ans)

Solution (Python):
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
n=i1()
a=i2()
for i in range(n):
 a[i]-=i+1
a=sorted(a)
b=n//2
if n%2:
   c=a[b]
   for i in range(n):
     a[i]=abs(a[i]-c)
else:
   b=(a[b]+a[b-1])//2
   for i in range(n):
     a[i]=abs(a[i]-b)
print(sum(a))

Solution (Python):
import statistics
import math

N = int(input())
a = input().split()
ans = 0
for i in range(0,N):
	a[i] = int(a[i])-i
med = int(statistics.median(a))
for i in range(0,N):
	ans += abs(a[i]-med)
print(int(ans))

Solution (Python):
n = int(input())
A = [int(i) for i in input().split(" ")]
b = 0
B = [A[i] - (i+1) for i in range(n)]
B.sort()
b = B[n//2]
sc = 0

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

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


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

def hoge(b):
    v = 0
    for x in a:
        v += abs(x-b)
    return v

print(hoge(c))

Solution (Python):
i=int
k=input
N = i(k())
l = list(map(i,k().split()))
for j in range(N):
 l[j] -= (j+1)
l.sort()
print(sum(list(map(lambda x: abs(x - l[N//2]),l))))

Solution (Python):
N = int(input())
lis = list(map(int,input().split()))
for i in range(len(lis)):
  lis[i] -= (i+1)
lis.sort()
m = N // 2
c = lis[m]
print(sum(list(map(lambda x: abs(x - c), lis))))

Solution (Python):
'''input
7
1 1 1 1 2 3 4
'''
n = input()
arr = map(int,raw_input().split())
for i in range(n):
	arr[i] = (arr[i]-(i+1))
arr.sort()
mean = float(arr[n//2])
ans = 10**30
for i in range(int(mean)-30,int(mean)+30):
	q = 0
	for j in range(n):
		q += abs(arr[j]-i)
	ans = min(q,ans)
print ans

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

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

Solution (Python):
while True:
    try:
        n = int(input())
        num = list(map(int, input().split()))
        for ind in range(len(num)):
            num[ind] -= ind+1
        num.sort()
        print(sum(abs(i-num[len(num)//2])for i in num))
    except:
        break

Solution (Python):
n = int(input())
nums = list(map(int,input().split()))
ans = 0
B = []

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

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

for j in range(n):
    ans += abs(nums[j] - (j + 1 + b))

print(ans)

Solution (Python):
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 = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-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)

def main():
    n = I()
    a = LI()
    t = sorted([a[i]-i-1 for i in range(n)])
    b = t[n//2]
    r = 0
    for i in range(n):
        r += abs(a[i]-(b+i+1))

    return r



print(main())

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

A = [A[i] - (i + 1) for i in range(len(A))]
A = sorted(A)
b = A[N // 2]
ans = [abs(a - b) for a in A]
print(sum(ans))

Solution (Python):
n = int(input())
a=[int(x)-i for i,x in enumerate(input().split())]
a.sort()
print(sum([abs(e-a[n//2]) for e in a]))

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[(N//2)]
	ans = list(map(lambda x:abs(x-b),A))
	print(sum(ans))
else:
	b1 = (A[N//2-1] + A[(N//2)])//2
	ans1 = list(map(lambda x:abs(x-b1),A))
	b2 = b1 + 1
	ans2 = list(map(lambda x:abs(x-b2),A))
	print(min(sum(ans1),sum(ans2)))

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

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

Solution (Python):
import statistics

def f(a, n):
    a2 = [ai - (i+1) for (i,ai) in enumerate(a)]
    b = int(statistics.median(a2))
    
    sadness = sum(abs(ai - b) for ai in a2)
    
    b += 1
    sadness2 = sum(abs(ai - b) for ai in a2)

    
    return min(sadness, sadness2)
    
n = int(input())
a = [int(i) for i in input().split()]
print(f(a, n))

Solution (Python):
import numpy as np

N=int(input())
A=input().split(" ")
for i in range(N):
	A[i]=int(A[i])

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

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

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

A.sort()

Ans = 0
mi = len(A)//2 
for i in range(N):
    Ans += abs(A[i]-A[mi])

print(Ans)

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

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

sortA = sorted(A)

if(N>1):
    b1 = sortA[(N-1)//2]
    b2 = sortA[(N-1)//2+1]

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

    print(min(ans1, ans2))
else:
    print(0)

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

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

a.sort()
b = [0]
for i in a:
    b.append(b[-1] + i)
hi = len(a)
lo = 0


def score(index):
    return abs(abs((index + 1) * a[index] - b[index+1]) + abs(b[-1] - b[index+1] - (len(a) - index - 1) * a[index]))


for i in range(10000):
    lft = (hi + 2 * lo) // 3
    rgt = (2 * hi + lo) // 3
    ltmp = score(lft)
    rtmp = score(rgt)
    if ltmp <= rtmp:
        lo = lft
    else:
        hi = rgt

print(min([score(i) for i in range(len(a))]))

Solution (Python):
import numpy as np

N = int(input())

B = np.array([0]*N)

l = input().split()

for i in range(N):
    B[i] = int(l[i]) - (i+1)
    
B = np.sort(B)

if N % 2 == 1:
    b_mid = B[int(N/2)]
else:
    mid = int(N/2) - 1
    b_mid = int( (B[mid] + B[mid+1])/2 )

dif = B - b_mid

print(np.sum(abs(dif)))

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

def sadness(index):
	return sum([abs(a[i] - a[index]) for i in range(n)])

if n % 2 == 1:
	print(sadness((n - 1) // 2))

else:
	print(min(sadness(n // 2), sadness(n // 2 - 1)))

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

mem = [a-i-1 for i,a in enumerate(src)]
center = sorted(mem)[N//2]

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

Solution (Python):

n = int(input())
nums = sorted([num - i for i, num in enumerate(list(map(int,input().split())), 1)])


sums = [None for i in range(n)]
sums[0] = nums[0]
allv = sum(nums)

minv = nums[0] * (2 - n) - 2 * sums[0] + allv
for i in range(n-1):
    sums[i+1] = sums[i] + nums[i+1]
    p = nums[i] * (2*(i+1) - n) -2 * sums[i] + allv
    minv = min(minv,p)

print(minv)

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())
aaa = list(map(int, input().split()))
aam = [a - i - 1 for i, a in enumerate(aaa)]
aam.sort()
b = aam[n // 2]
print(sum(abs(am - b) for am in aam))

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

for i in range(n):
  a[i] -= (i+1)
a.sort()
m1 = a[n//2]
m2 = a[n//2-1]
ans1 = sum([abs(ele-m1) for ele in a])
ans2 = sum([abs(ele-m2) for ele in a])
print(min(ans1, ans2))

Solution (Python):
from statistics import median

N = int(input())
A = list(map(int, input().split()))
for i in range(N):
    A[i] -= i+1
 
A.sort()
b = median(A)
sad = 0
for i in range(N):
    sad += abs(A[i]-b)
print(int(sad))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A_dash = []
for i, A_i in enumerate(A):
    A_dash.append(A_i-(i+1))
A_dash.sort()

med = A_dash[N//2]

ans = 0
for i, A_i in enumerate(A_dash):
    ans += abs(A_i - (med))

print(ans)

Solution (Python):
import functools
N = int(input())
A = [int(x) for x in input().split()]
Ai = sorted([A[i] - i - 1 for i in range(N)])
if N % 2:
  med = N // 2
  ans = functools.reduce(lambda x, y: x + y, [abs(a - Ai[med]) for a in Ai])
else:
  med = N // 2
  ans1 = functools.reduce(lambda x, y: x + y, [abs(a - Ai[med]) for a in Ai])
  ans2 = functools.reduce(lambda x, y: x + y, [abs(a - Ai[med - 1]) for a in Ai])
  ans = min(ans1, ans2)
print(ans)

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

for i in range(a):
	su += abs(b[i] - c)

print(su)

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

Solution (Python):
import numpy as np
n = int(input())
if n == 1:
    a = input()
    print(0)
else:
    a = np.array(list(map(int, input().split())))
    check = np.arange(1, n+1)
    c = sorted(list(a - check))
    b1 = c[int(n/2)]
    b2 = c[int(n/2)+1]
    count1 = 0
    count2 = 0
    for i in range(1, n+1):
        count1 += abs(a[i-1] - i - b1)
        count2 += abs(a[i-1] - i - b2)
    print(min(count1, count2))

Solution (Python):
def bisect(l, r):
    while l < r:
        m = (l + r) // 2
        s1 = sum(abs(am - m) for am in aam)
        s2 = sum(abs(am - m - 1) for am in aam)
        if s1 < s2:
            r = m
        else:
            l = m + 1
    return l


n = int(input())
aaa = list(map(int, input().split()))
aam = [a - i - 1 for i, a in enumerate(aaa)]
aas = sum(aam)
b = bisect(int(-1e9), int(1e9))
print(sum(abs(am - b) for am in aam))

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    p, z, m = [], 0, []
    for i in range(n):
        t = a[i] - (i + 1)
        if t > 0:
            p.append(t)
        elif t == 0:
            z += 1
        else:
            m.append(-t)
    if sum(m) > sum(p):
        p, m = m[:], p[:]

    p.sort()
    ps, ms = sum(p), sum(m)
    pl, ml = len(p), len(m)
    x = 0
    ans = ms + ps
    for t in p:
        t, x = t - x, t
        ps -= pl * t
        pl -= 1
        if t > 0:
            ml += z
            ms += ml * t
            z = 1
            a = ms + ps
            if a < ans:
                ans = a
        else:
            z += 1
    print(ans)


main()

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
AA = sorted([ a - i - 1 for i,a in enumerate(A) ])
C = []
for i,a in enumerate(AA):
    if i == 0:
        C.append(a)
    else:
        C.append(C[-1] + a)
ans = ""

for i,b in enumerate(AA):
    sample = 0
    num = i-1
    if num == -1:
        sample = C[-1]  - b * (N - 2 * (num + 1))
    else:
        sample = C[-1] - 2 * C[num] - b * (N - 2 * (num + 1))
    if ans == "":
        ans = sample
    if ans > sample:
        ans = sample
if ans == "":
    ans = 0
print(ans)

Solution (Python):
from math import ceil,floor
n=int(input())
if n==1:
  print(0)
  exit()
a=[int(i) for i in input().split()]
for i in range(n):
  a[i]-=(i+1)
a.sort()

b1=a[ceil(n/2)]
b2=a[floor(n/2)]

def c1(x):
    return abs(x-b1)
def c2(x):
    return abs(x-b2)
print(min(sum(list(map(c1,a))),sum(list(map(c2,a)))))

Solution (Python):
import numpy as np

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

list = []

for b in range(0, N):
    list.append(A[b] - b)

md = int(np.median(list))

bb = 0
for b in range(0, N):
    bb += abs(list[b] - md)

print(bb)

Solution (Python):
from statistics import median

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

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

ave = int(median(a))

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

print(sad)

Solution (Python):
import sys
N = int(sys.stdin.readline())
As = list(map(int, sys.stdin.readline().split()))
bs = []
for i, a in enumerate(As):
    bs.append(a-(i+1))
bs.sort()

cumsum = [0]
s = 0
for b in bs:
    s += b
    cumsum.append(s)

def func(j):
    b = -bs[j]

    s_l = cumsum[j+1] - cumsum[0] 
    s_r = cumsum[N] - cumsum[j+1] 

    res = abs(s_l+b*(j+1)) + abs(s_r+b*(N-(j+1)))
    return res

res = float('inf')
for j, b in enumerate(bs):
    res = min(res, func(j))
print(res)

Solution (Python):
import statistics
import math

n = int(input())
a = [int(i) - (index+1) for index, i in enumerate(input().split())]

abs_total = 0
for i in a:
  abs_total += abs(i)

median = statistics.median(a) 


if n % 2 == 0 and median.is_integer() is False:
  median_high = statistics.median_high(a)
  median_low = statistics.median_low(a)

  abs_high = 0
  abs_low = 0
  for i in a:
    abs_high += abs(i-median_high)
    abs_low += abs(i-median_low)

  if abs_high < abs_low:
    print(int(abs_high))
  else:
    print(int(abs_low))
else:
  abs_total = 0
  for i in a:
    abs_total += abs(i-median)
  print(int(abs_total))

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

d=sorted(b2)

if a%2==1:
    b3=[abs(i-d[len(d)//2]) for i in b2]
else: 
    if d[len(d)//2]<0:
        if d[len(d)//2+1]<0:
            b3=[abs(i-d[len(d)//2+1]) for i in b2]
    else:
        b3=[abs(i-d[len(d)//2]) for i in b2]

print(sum(b3))

Solution (Python):
N = int(input())
data = list(map(int, input().split()))
for i in range(N):
    data[i] -= (i + 1)
ave = sum(data) / N
if ave > 0:
    key = int(ave + 1)
    key1 = int(ave)
else:
    key = int(ave - 1)
    key1 = int(ave)
data.sort()
sumdata = 0
sumdata2 = 0
key = data[int(N / 2) - 1]
key2 = data[int(N / 2)]
for i in data:
    sumdata += abs(i - key)
    sumdata2 += abs(i - key2)



print(min([sumdata, sumdata2]))

Solution (Python):
import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
n = np.array([i for i in range(A.size)][::-1])
A = A+n
ave = np.median(A)
round = lambda x:int(x*2+1)//2
ave = round(ave)
A = A-ave
A = np.abs(A)
print(A.sum())

Solution (Python):

def mi():
	return map(int, input().split())

n = list(mi())[0]
a = list(mi())
for i in range(len(a)):
	a[i]-=i+1
s = 0

import statistics
b = a.copy()
for i in range(n):
	b[i] = abs(a[i])

a1 = statistics.median(a)
a2 = statistics.median(b)

s = 0
s1 = 0
for i in range(n):
	s+=abs(a[i]-a1)
	s1+=abs(a[i]-a2)
s = min(s,s1)
print (int(s))

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

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

sortA = sorted(A)

if(N>1):
    b1 = sortA[(N-1)//2]
    b2 = sortA[(N-1)//2+1]

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

    print(min(ans1, ans2))
else:
    print(0)

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

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

a.sort()

d1 = a[len(a) // 2]
print(sum([abs(i - d1) for i in a]))

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):

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

    
    def sk(b):
        s = 0
        for i, a in enumerate(A):
            s += abs(a-(b+i+1))
        return s

    
    

    s = -int(1e+10)
    e = int(1e+10)
    ssk = sk(s)
    esk = sk(e)
    
    
    while abs(s - e) > 1:
        m = (s+e)//2
        msk = sk(m)
        
        if ssk < esk:
            esk = msk
            e = m
        else:
            ssk = msk
            s = m
    
    return min(sk(s), sk(e))


def main():
    N = read_int()
    A = read_int_n() 
    print(slv(N, A))


if __name__ == '__main__':
    main()

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

Solution (Python):
import math
import numpy as np

n = int(input())
a_list = list(map(int, input().split()))
a_list2 = sorted([a - (i + 1) for i, a in enumerate(a_list)])

s_cand = []
b_cand = [math.floor(sum(a_list2) / n), math.ceil(sum(a_list2) / n), int(np.median(a_list2))]

for b in b_cand:
    s = 0
    for a in a_list2:
        s += int(abs(a - b))
    s_cand.append(s)
    
print(min(s_cand))

Solution (Python):

import statistics
import math
n = int(input())
A = list(map(int, input().split()))

aa = []

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

b = int(statistics.median(aa))

ans = 0

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

print(ans)

Solution (Python):
import numpy as np

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


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

np_A = np.array(A)
b = -np.median(np_A)

np_A += b.astype("i")
res = np.abs(np_A).sum()
print(res)

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

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

b = statistics.median(c)
ret0 = 0
ret1 = 0
ret2 = 0
for i in range(n):
    ret0 += abs(a[i] - b - i)
    ret1 += abs(a[i] - b - i - 1)
    ret2 += abs(a[i] - b - i - 2)

print(int(min(ret0, ret1,ret2)))

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


if N % 2 == 1:
    X = A[N // 2]
    ans = 0
    for a in A:
        ans += abs(a - X)
    print(ans)
else:
    X = (A[N // 2] + A[N // 2 -1]) / 2
    X1 = ceil(X)
    X2 = floor(X)
    ans1, ans2 = 0, 0
    for a in A:
        ans1 += abs(a - X1)
        ans2 += abs(a - X2)

    print(int(min(ans1, ans2)))

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

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

a.sort()

center = n // 2

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

print(ans)

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

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

minSad = float('inf')
for i in range(1, n + 1):
    b = a[i]
    tempL = b * i - (aSum[i] - aSum[0])
    tempR = (aSum[n] - aSum[i]) - b * (n - i) 
    minSad = min(minSad, tempL + tempR)

print(minSad)

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

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

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

Solution (Python):
import numpy as np

def ii():
    return int(input())


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


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


def main():
    N = ii()
    A = lii()
    for i in range(N):
        A[i] -= (i + 1)

    A = np.array(sorted(A))
    offset = A[0]
    A = A - offset
    s1 = A.sum()
    mins = s1
    s2 = 0
    nowv = 0

    for i, v in enumerate(A):
        if nowv < v:
            s1 -= (v - nowv) * (N - i)
            s2 += (v - nowv) * i
            nowv = v
            if s1 + s2 < mins:
                mins = s1 + s2

    return mins

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

Solution (Python):

import numpy as np
N = int(input())
A = list(map(int, input().split()))
A = sorted([a-(i+1) for i, a in enumerate(A)])
m = A[N//2]
ans = 0
for a in A:
    ans += abs(a-m)
print(ans)

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)