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

Solution (Python):
import statistics

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

value = 0

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

x.sort()

for _ in x:
    value += abs(_ - x[n // 2])

print(value)

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 len(B)%2:
    ans = 0
    for i in range(n):
        ans += abs(B[i]-B[len(B)//2])
else:
    ans = float("inf")
    tmp = 0
    for i in range(n):
        tmp += abs(B[i]-B[len(B)//2-1])
    ans = min(ans, tmp)
    tmp = 0
    for i in range(n):
        tmp += abs(B[i]-B[len(B)//2])
    ans = min(ans, tmp)

print(ans)

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

Solution (Python):
import sys



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


def input_int():
    return int(input())


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


def main():
    n = input_int()
    A = input_int_list()
    for i in range(n):
        A[i] = A[i] - (i + 1)

    A.sort()

    if n % 2 == 0:
        mid = (A[(n - 1) // 2] + A[((n - 1) // 2) + 1]) // 2
    else:
        mid = A[(n - 1) // 2]

    tmp0 = 0
    tmp1 = 0

    for a in A:
        tmp0 += abs(a - mid)
        tmp1 += abs(a - mid - 1)

    print(min(tmp0, tmp1))

    return


if __name__ == "__main__":
    main()

Solution (Python):
import sys

N = int(input())
A = list(map(int, sys.stdin.readline().rsplit()))

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

A.sort()
b = A[(N - int(N % 2 == 0)) // 2]

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

print(res)

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]

ans = 0
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()))





a = np.array(A)
b = a - np.arange(1,N+1)
c = np.median(b)
d = abs(b-c).sum()
print(int(d))

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

import numpy as np
a = np.array(a)
x = np.median(a)
r = 0
for i in range(n):
    r += abs(a[i]-x)
print(int(r))

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

if n==1:
    b1=L[0]
    b2=L[0]
elif n==2:
    b1=L[0]
    b2=L[1]
else:
    b1=L[n//2]
    b2=L[n//2-1]
ans=0
cnt1=0
cnt2=0
for i in range(n):
    cnt1+=abs(L[i]-b1)
    cnt2+=abs(L[i]-b2)
print(min(cnt1,cnt2))

Solution (Python):
import math

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

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

A.sort()

if N % 2 == 0:
    b = (A[N//2-1] + A[N//2]) / 2
    bfl = math.floor(b)
    bce = math.ceil(b)
    ansfl = 0
    ansce = 0

    for i in range(N):
        ansfl += abs(A[i] - bfl)
        ansce += abs(A[i] - bce)

    ans = min(ansfl, ansce)

else:
    ans = 0
    b = A[N//2]

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

print(ans)

Solution (Python):
import statistics
import math

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

A_list_min = 10**9+1
A_list_sum = 0
for i in range(N):
    A_list[i] = A_list[i] - (i+1)

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

Solution (Python):
import math

def main():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(N):
        A[i] -= (i+1)
    
    A.sort()
    if N%2 == 0:
        b = (A[N//2] + A[N//2 - 1])/2
        bfl = math.floor(b)
        bce = math.ceil(b)
        ansfl = 0; ansce = 0
        for i in range(N):
            ansfl += abs(A[i] - bfl)
            ansce += abs(A[i] - bce)
        ans = min(ansfl, ansce)
    else:
        ans = 0
        b = A[N//2]
        for i in range(N):
            ans += abs(A[i] - b)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from statistics import median_high
n=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(n):
    b.append(a[i]-i-1)
b.sort()
d=median_high(b)
ans=0
for i in range(n):
    ans+=abs(b[i]-d)
print(ans)

Solution (Python):
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))



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

Solution (Python):
import statistics
import math

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

for i in range(n):
    A[i] = A[i]-i-1
A.sort()
m = statistics.median(A)

f = math.floor(m)
c = math.ceil(m)
sum_f = 0
sum_c = 0

for i in range(n):
    sum_f += abs(A[i]-f)
    sum_c += abs(A[i]-c)
    
print(min(sum_f, sum_c))

Solution (Python):
from collections import defaultdict
d = defaultdict(int)
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
  a[i]-=i+1
  d[a[i]]+=1
ans=0
b = min(a)
for i in a:
  ans+=i-b
a = sorted(set(a))
c = 0
i = 0
while i<len(a)-1:
  c+=d[a[i]]
  if c-(n-c)>0:
    print(ans)
    exit()
  ans+=(c-(n-c))*(a[i+1]-a[i])
  i+=1
print(ans)

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

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
  A[i]-= i+1
A.sort()
total = sum(A)
mean1 = total//N
mean2 = total//N + 1
med1 = A[N//2]

ans1 = 0
ans2 = 0
ans3 = 0
ans4 = 0 
for a in A:
  ans1+=abs(a-mean1)
  ans2+=abs(a-mean2)
  ans3+=abs(a-med1)
  
print(min([ans1,ans2,ans3]))

Solution (Python):
import numpy as np

N = int(input())
A = np.array(list(map(int,input().split())))
A -= np.arange(1,N+1)
print(sum(abs(A-int(np.median(A)))))

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

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

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

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

print(ans)

Solution (Python):
import numpy as np
n = int(input())
a = np.fromstring(input(), dtype=np.int64, sep=' ')
for i in range(n):
    a[i] = a[i] - i - 1
x = int(np.median(a))
r = 0
for i in range(n):
    r += abs(a[i]-x)
print(r)

Solution (Python):
n = int(input())
a = [int(j)-int(i)-1 for i, j in enumerate(input().split())]
a.sort()
num = n/2
if num.is_integer():
    num = num-1
val = a[int(num)]
ans = sum([abs(i-val) for i in a])
print(ans)

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

from collections import defaultdict
sys.setrecursionlimit(10**7)


import bisect






INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7


def run():
    N, *A = map(int, read().split())
    B = [a-k for k, a in enumerate(A, 1)]
    B.sort()
    Bsum = []
    v = 0
    for b in B:
        v += b
        Bsum.append(v)

    min_val = INF
    for k in range(N):
        c = B[k]
        
        score = 0
        score -= Bsum[k]
        score += Bsum[-1] - Bsum[k]
        score += -N * c + 2 * c * (k+1)
        
        min_val = min(min_val, score)

    print(min_val)


if __name__ == "__main__":
    run()

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

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

Solution (Python):
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n, *a = map(int, read().split())

    a2 = list([ea - i - 1 for i, ea in enumerate(a)])
    a2.sort()
    n2 = n // 2
    r1 = sum([abs(ea2 - a2[n2]) for ea2 in a2])
    r2 = sum([abs(ea2 - a2[n2-1]) for ea2 in a2])
    print(min(r1, r2))


if __name__ == '__main__':
    main()

Solution (Python):
import statistics

def main():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(N):
        A[i] -= i + 1
    B = statistics.median_low(A)
    ans = 0
    for a in A:
        ans += abs(a - B)

    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  


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

x = (A[N//2]+A[(N-1)//2])//2
print(sum(abs(A[i]-x) for i in range(N)))

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

memo = []

for key,val in enumerate(A):
    memo.append(val-key-1)
memo.sort()

ans = 0
for key,val in enumerate(A):
    ans += abs(val-key-1-memo[N//2])
print(ans)

Solution (Python):
def LI():
    return list(map(int, input().split()))


N = int(input())
A = LI()
x = []
for i in range(N):
    x.append(A[i]-(i+1))

x.sort()
B = x[N//2]

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

Solution (Python):
from numpy import*
n=int(input())
a=array(list(map(int,input().split())))
b=a-arange(1,n+1)
c=median(b)
d=abs(b-c).sum()
print(int(d))

Solution (Python):
import statistics
n,*a=map(int,open(0).read().split())
b=[q-i for i,q in enumerate(a,1)]
c=statistics.median(b)
ans=sum(map(abs,[p-c for p in b]))
print(int(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=sorted(b)
if n%2==1:
    ave = b[(n-1)//2]
else:
    ave = (b[n//2] + b[(n//2)-1])//2


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

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)

ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(readline())


def ints(): return np.fromstring(readline(), sep=' ', dtype=np.int64)


def read_matrix(H, W):
    '''return np.ndarray shape=(H,W) matrix'''
    lines = []
    for _ in range(H):
        lines.append(read())
    lines = ' '.join(lines)  
    return np.fromstring(lines, sep=' ', dtype=np.int64).reshape(H, W)


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


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


MOD = 10**9 + 7
INF = 2**31  


from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  
from functools import reduce
from math import gcd


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


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

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

Solution (Python):
import numpy as np

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

arr = np.arange(n) + 1
diff = a - arr

diff.sort()

diff = diff - np.median(diff)

print(int(np.abs(diff).sum()))

Solution (Python):
import sys
 
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
 
A_dash = []
for i in range(N):
    A_dash.append(A[i] - (i + 1))
 
A_dash.sort()
ans = -float("inf")
if N % 2 == 1:
    tmp = 0
    b = A_dash[N // 2]
    for i in range(N):
        tmp += abs(A_dash[i] - b)
    print(tmp)
else:
    tmp1 = 0
    b = A_dash[N // 2 - 1]
    for i in range(N):
        tmp1 += abs(A_dash[i] - b)
    
    tmp2 = 0
    b = A_dash[N // 2]
    for i in range(N):
        tmp2 += abs(A_dash[i] - b)
    print(min(tmp1, tmp2))

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  


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

x = A[N//2]
y = A[(N-1)//2]
z = (x+y)//2

print(sum(abs(A[i]-z) for i in range(N)))

Solution (Python):
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().rstrip().split())
inl = lambda: list(map(int, input().split()))
out = lambda x, s='\n': print(s.join(map(str, x)))

n = ini()
a = inl()
j = 1
for i in range(n):
    a[i] -= j
    j += 1
a = sorted(a)
x = a[n//2]
ans = 0
for i in range(n):
    ans += abs(a[i] - x)
print(ans)

Solution (Python):

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

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

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

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

print(total)

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

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

memo = []

for key,val in enumerate(A):
    memo.append(val-key-1)

memo.sort()

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

ans  = 0
for key,val in enumerate(A):
    ans += abs(val-(b+key+1))

print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())

As = [a-i for i, a in enumerate(As, 1)]
As.sort()
middle = As[N//2]
print(sum([abs(a-middle) for a in As]))

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  


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


def f(x):
    return sum(abs(A[i]-x) for i in range(N))


print(f((A[(N-1)//2]+A[N//2])//2))

Solution (Python):
import sys

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

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

A_dash.sort()
ans = -float("inf")
if N % 2 == 1:
    tmp = 0
    b = A_dash[N // 2]
    for i in range(N):
        tmp += abs(A_dash[i] - b)
    print(tmp)
else:
    tmp1 = 0
    b = A_dash[N // 2 - 1]
    for i in range(N):
        tmp1 += abs(A_dash[i] - b)
    
    tmp2 = 0
    b = A_dash[N // 2]
    for i in range(N):
        tmp2 += abs(A_dash[i] - b)
    print(min(tmp1, tmp2))

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

A.sort()
dic = {}
for x in A:
  if x not in dic:
    dic[x] = 1
  else:
    dic[x] += 1
S = list(dic.keys())
now = 0
for x in A:
  now += abs(A[0]-x)

prev = A[0]
left = dic[S[0]]; right = N- left
for i in range(1,len(S)):
  dif = (left-right)*(S[i]-S[i-1])
  if dif < 0:
    now += dif
  left += dic[S[i]]
  right -= dic[S[i]]
print(now)

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  


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


def f(x):
    return sum(abs(A[i]-x) for i in range(N))


print(f((A[(N-1)//2]+A[N//2])//2))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A = [a-i-1 for i, a in enumerate(A)]
A.sort()
if N%2:
  med = A[(N-1)//2]
  A = [abs(a-med) for a in A]
  print(sum(A))
  exit()
else:
  med1 = (A[N//2-1]+A[N//2])//2
  med2 = med1 + 1
  A1 = [abs(a-med1) for a in A]
  A2 = [abs(a-med2) for a in A]
  print(min(sum(A1), sum(A2)))
  exit()

Solution (Python):
import numpy as np
N = int(input())
A = list(map(int,input().split()))
B = [0]*N
ans =0 
for i,j in enumerate(A):
    B[i] = j-(i+1)
B=sorted(B)
b=np.median(np.array(B))
for i,j in enumerate(A):
    ans+= abs(j-(int(b)+i+1))
print(ans)

Solution (Python):
n=int(input())
A=[int(i) for i in input().split()]
A=[A[i]-i for i in range(n)]
A.sort()
if n%2==0:
    mid2=A[n//2]+A[n//2-1]
else:
    mid2=A[n//2]*2

B=[i*2 for i in A]
ans=0
for i in range(n):
    ans+=abs(B[i]-mid2)
print(ans//2)

Solution (Python):
from statistics import median_low

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

a = [ai - i for i, ai in enumerate(a)]
med = median_low(a)
print(sum(abs(ai - med) for ai in a))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
inf = 10**16

def func(b):
    return sum([abs(a[i]-(b+i+1)) for i in range(n)])


low = -inf
high = inf

while abs(high-low) > 0.01:
    c1 = (low*2 + high)/3
    c2 = (low + high*2)/3

    if func(c1) > func(c2):
        low = c1
    else:
        high = c2
mid = (high+low)/2
ans = min(func(int(mid)), func(int(mid+1)), func(int(mid-1)))
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
a = [(item-i-1) for i,item in enumerate(a)]
a.sort()
m = a[(n-1)//2]
ans = sum(abs(item-m) for item in a)
print(ans)

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

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

a_i=[]
pl=0
mi=0
mi_cnt=0
pl_cnt=0
for i in range(n):
  a_i.append((a[i]-(i+1)))
  if a[i]-(i+1)<0:
    mi+=a[i]-(i+1)
    mi_cnt+=1
  else:
    pl+=a[i]-(i+1)
    pl_cnt+=1

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

ans=0
for i in a_i:
  ans+=abs(i-k)
print(ans)

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==0:
  tmp=(a[n//2]+a[n//2-1])//2
else:
  tmp=(a[n//2])
  
ans=0
for aa in a:
  ans+=abs(aa-tmp)


print(ans)

Solution (Python):

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

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

X = sorted(X)

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

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

print(int(out))

Solution (Python):

import math
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()
if n==1:
    m=B[0]
    m2=B[0]
else:
    m = B[n//2]
    m2=B[n//2+1]
tmp1=0
tmp2=0

for i in range(n):
    tmp1 += abs(A[i]-(i+1)-m)
    tmp2 += abs(A[i]-(i+1)-m2)
print(min(tmp1, tmp2))

Solution (Python):
n,*a = map(int,open(0).read().split())
a = sorted([a[i] -i for i in range(n)])
print(sum([abs(i - a[n//2]) for i in a]))

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

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

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

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

Solution (Python):

def main():
	n = int(input())
	arr = list(map(int , input().split()))
	for i in range(0 , n):
		arr[i]=arr[i]-(i+1)
	ans=0
	md=0
	arr.sort()
	if n%2==0:
		md = (arr[n//2-1]+arr[(n//2)])//2
	else:
		md = arr[n//2]
	for i in range(0,n):
		ans = ans +abs(arr[i]-md)
	print(ans)
if __name__=="__main__":
	main()

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics

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

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

def f(k):
    return sum(map(lambda x: abs(x-k), a))

c = statistics.median(a)
print(int(f(c)))

Solution (Python):

        
def main():
    import sys
    from bisect import bisect_left, bisect_right
    def input(): return sys.stdin.readline().rstrip()

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




                
if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
N = int(input())
num = list(map(int,input().split()))
for i in range(1, N+1):
    num[i-1] -= i
numbers = np.array(num)
b = int(round(np.median(numbers)))
numbers-= b
number = np.abs(numbers)
print(number.sum())

Solution (Python):





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









ok, ng = -10**9, 10**9 + 1


def calc(b):
    ret = 0
    for i, v in enumerate(a):
        ret += abs(v - (b + i + 1))
    return ret



c = 0
while c < 100:
    c += 1
    c1 = (2 * ok + ng) // 3
    c2 = (ok + 2 * ng) // 3
    b1, b2 = calc(c1), calc(c2)
    if b1 > b2:
        ok = c1 + 1  
    else:
        ng = c2

print(calc(ok))

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
a = LIST()
for i in range(n):
    a[i] -= i + 1
a.sort()
b = a[n//2]
ans = 0
for x in a:
    ans += abs(x - b)
print(ans)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()


def resolve():
    N = I()
    A = LI()

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

    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):


import math

N = int(input())
A = [int(n) for n in input().split()]
for i in range(len(A)):
    A[i] -= (i+1)
A.sort()

med = 0
if N % 2 == 0:
    m1 = N // 2
    m2 = m1 - 1
    med = round((A[m1] + A[m2]) / 2)
else:
    m1 = (N+1) // 2
    med = A[m1-1]

sad = sum([abs(a-med) for a in A])

print(sad)

Solution (Python):
def solve():
  ans = 0
  N = int(input())
  A = list(map(int, input().split()))
  for i in range(N):
    A[i] -= i+1
  B = sorted(A)
  p = B[N//2]
  for i in range(N):
    A[i] = abs(A[i]-p)
  ans = sum(A)
  return ans
print(solve())

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

Solution (Python):
import sys

input = sys.stdin.readline


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

    A = [a - i for i, a in enumerate(A, start=1)]
    A.sort()

    b = A[(N + 1) // 2 - 1]
    ans = sum(map(lambda x: abs(x - b), A))
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import statistics
n = int(input())
a = []
for i,j in enumerate(map(int,input().split())):
  a.append(j-i-1)
b,s = statistics.median(a),0
for i in a:
  s+=abs(i-b)
print(int(s))

Solution (Python):
n = int(input())
a = [ai - i for i, ai in enumerate(map(int, input().split()), 1)]
a.sort()
med = a[len(a)//2]
print(sum(abs(ai - med) for ai in a))

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
  a[i]-=i
a=sorted(a)
m=a[n//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()))
A = [a-i-1 for i,a in enumerate(A)]
A.sort()
mA = int(median(A))
print(min([sum([abs(a-mA-1) for a in A]), sum([abs(a-mA) for a in A]), sum([abs(a-mA+1) for a in A])]))

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

A = np.array(A)

k = int(np.median(A))

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

print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
  a[i]-=i+1
b=a[:]
b.sort()
mid1=0
mid2=0
if n%2==1:
  ans=0
  mid1=b[n//2]
  for bb in b:
    ans+=abs(bb-mid1)
  print(ans)
else:
  mid1=b[n//2]
  mid2=b[n//2-1]
  ans1,ans2=0,0
  for bb in b:
    ans1+=abs(bb-mid1)
    ans2+=abs(bb-mid2)
  print(min(ans1,ans2))

Solution (Python):
def main():
    N = int(input())
    A = list(map(int,input().split()))
    for i in range(N):
        A[i] -= i+1
    
    def f(b):
        res = 0
        for a in A:
            res += abs(a-b)
        return res
    
    INF = 10**9+10
    l = -INF
    r = +INF

    while l < r-2:
        m1 = (r-l)*2//3+l
        m2 = (r-l)//3+l
        tmp1 = f(m1)
        tmp2 = f(m2)

        if tmp2 < tmp1:
            r = m1
        else:
            l = m2
    print(f((l+r)//2))

main()

Solution (Python):

def main():
    from math import floor,ceil
    N = int(input())
    A = list(map(int,input().split()))
    for i in range(N):
        A[i] -= i+1
    
    def f(b):
        res = 0
        for a in A:
            res += abs(a-b)
        return res
    INF = 10**9+10
    l = -INF
    r = INF
    min_saddness = 10**15
    while l < r-2:
        m1 = (r-l)*2//3+l
        m2 = (r-l)//3+l
        tmp1 = f(m1)
        tmp2 = f(m2)

        if tmp2 < tmp1:
            r = m1
        else:
            l = m2
    print(f((l+r)//2))

main()

Solution (Python):
n = int(input())
A = [int(x) for x in input().split()]
A_ = sorted([a - i for i, a in enumerate(A, 1)])
i = len(A) // 2
b = A_[i]
ans = sum([abs(a - b) for a in A_])
print(ans)

Solution (Python):
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split()))) - np.array(list(range(1, N+1)))
A = A.astype(np.int64)
m = np.median(A)
m = m.astype(np.int64)
A -= m
ans = sum(np.abs(A))
print(ans.astype(np.int64))

Solution (Python):
import statistics

if __name__ == "__main__":
    N = int(input())
    A = [float(x) for x in input().split(" ")]
    A = [a - i - 1 for i, a in enumerate(A)]
    med = statistics.median(A)
    A = [abs(a - med) for a in A]
    print(int(sum(A)))

Solution (Python):

import sys

def solve(N: int, A: "List[int]"):
    A = sorted(a - i for i, a in enumerate(A))
    m = A[N//2]
    return sum(abs(a-m) 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))  
    A = [int(next(tokens)) for _ in range(N)]  
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

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