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()))
A_1 = [A[i] - (i+1) for i in range(n)]
m = int(statistics.median(A_1))
A_2 = [abs(m - A_1[i]) for i in range(n)]
print(sum(A_2))

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

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]
for j in range(N):
  A[j] = abs(A[j]-b)

print(sum(A))

Solution (Python):


import statistics


def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N = int(input())
    A = list(map(int, input().split()))

    return N, A


def main(N: int, A: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): 整数列の長さ(1 <= N <= 2 × 10^5)
        A (list): 整数列(1 <= A_i <= 10^9)
    """
    
    B = [A[i] - (i + 1) for i in range(N)]
    b = statistics.median_high(B)
    ans = sum([abs(B[i] - b) for i in range(N)])

    
    print(ans)


if __name__ == "__main__":
    
    N, A = get_input()

    
    main(N, A)

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

Solution (Python):


import statistics


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


A = [A[i] - (i + 1) for i in range(N)]
b = statistics.median_high(A)
ans = sum([abs(A[i] - b) for i in range(N)])


print(ans)

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

Solution (Python):
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n = i_input()
    a = i_list()
    a = [k-(i+1) for i,k in enumerate(a)]

    a.sort()
    import statistics

    ans = int(statistics.median(a))
    trial = 0
    for i in a:
        trial += abs(i - ans)
    print(trial)


if __name__=="__main__":
    main()

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==0:
  a=N/2
  b=int((B[int(a)]+B[int(a-1)])/2)
else:
  a=(N+1)/2
  b=B[int(a-1)]
for i in range(N):
  B[i]=abs(B[i]-b)
print(sum(B))

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
    A[i] = A[i]-i-1
A.sort()
import bisect
z = bisect.bisect_left(A,0)
ans = sum(A[z:])-sum(A[:z])
if z > N-z:
    p = 0
    while z>N-z:
        b = A[z-1]
        ans += (N - 2*z) * (p-b)
        p = b
        z = bisect.bisect_left(A,b)
elif N > 2*bisect.bisect_right(A,0):
    z = bisect.bisect_right(A,0)
    p = 0
    while N-z>z:
        b = A[z]
        ans += (2*z - N) * (b-p)
        p = b
        z = bisect.bisect_right(A,b)
print(ans)

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

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

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

Solution (Python):
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//2]
    print(sum([abs(a - b) for a in A]))


if __name__ == '__main__':
    main()

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:
    m = A[N//2]
else:
    m = (A[N//2] + A[N//2 - 1]) // 2

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

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]

print(b * (n//2) - sum(a[:n//2]) + sum(a[n//2:]) - b * (n - n//2))

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]

print(b * (n//2) - sum(a[:n//2]) + sum(a[n//2:]) - b * (n - n//2))

Solution (Python):
import statistics

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

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


mid=b
  
ans1=0

for j in range(n):
  ans1+=abs(a[j]-mid-(j+1))
  
print(ans1)

Solution (Python):
N = int(input())
lsA = [0]+list(map(int,input().split()))
lsA2 = [int(lsA[i]) - i for i in range(1,N+1)]
lsA2.sort()
if N % 2 == 1:
    b = lsA2[N//2]
else:
    b = (lsA2[N//2-1] + lsA2[N//2])//2
ans = 0
for i in range(N):
    ans += abs(lsA2[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-1)//2]

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

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

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

diff = sorted(diff)
if n % 2 == 1:
    x = diff[n // 2]
else:
    x = (diff[(n // 2) - 1] + diff[n // 2]) // 2

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

print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]=a[i]-(i+1)
import numpy as np
an=np.array(a)
b=int(np.median(an))
ans=0
for i in a:
    ans+=abs(i-b)
print(ans)

Solution (Python):
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]=a[i]-(i+1)
ac=Counter(a)
if len(a)%2==0:
    dist=len(a)//2
else:
    dist=len(a)//2+1
temp=0
for i,j in sorted(ac.items()):
    temp+=j
    if temp>=dist:
        ans=0
        for k in range(n):
            ans+=abs(a[k]-i)
        print(ans)
        
        exit()

Solution (Python):
def median(array):
    L = len(array)
    if L%2==0:
        return (array[L//2-1]+array[L//2])/2
    else:
        return array[L//2]

N = int(input())
A = []
for i, a in enumerate(map(int, input().split())):
    A.append(a-i)
A.sort()
b = median(A)
res = 0
for a in A:
    res += abs(a-b)
print(round(res))

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

if n %2 ==0:
    a = round(n/2)
    
    can = [bs[a],bs[a-1],math.floor((bs[a] +bs[a-1])/2),math.ceil((bs[a] +bs[a-1])/2)]
elif n ==1:
    can = [bs[0],bs[0]]
else:
    a = math.floor(n/2)
    
    can = [bs[a+1],bs[a-1],bs[a]]


result = 10**27
for k in can:
    ans =0
    for kn in bs:
        ans += abs(kn-k)
    
    result = min(result, ans)
    
print(result)

Solution (Python):
from functools import lru_cache
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
left = -10**9
right = 10**9

@lru_cache(maxsize=100000)
def cal(num):
  tmp = 0
  for i in range(n):
    tmp += abs(a[i]-(num+(i+1)))
  return tmp
 

while abs(right-left)>1:
  mid = (right+left)//2
  if cal(mid-1)<cal(mid+1):
    right = mid
  else:
    left = mid
print(min(cal(left),cal(right)))

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

for i in range(n):
    l[i] = l[i] - i-1
l.sort()
if n % 2 == 1:
    print(sum(list(map(lambda x: abs(x-l[((n//2))]),l))))
else:
    print(min(sum(list(map(lambda x: abs(x-l[(n//2)-1]),l))),sum(list(map(lambda x: abs(x-l[(n//2)]),l)))))

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

hu=0
sei=0
ans=0
ahu=[]
asei=[]

for i in range(1,n+1):
  a[i-1]-=i
  ans+=abs(a[i-1])
  if a[i-1]<0:
    hu+=1
    ahu.append(abs(a[i-1]))
  elif a[i-1]>0:
    asei.append(a[i-1])
    sei+=1
zero=n-sei-hu
now=0


asei.sort()
ahu.sort()

if sei < hu and sei+zero <hu:
  sei+=zero
  for i in range((hu-sei)//2+1):
    ans-=(ahu[i]-now)*(hu-sei-2*i)
    now=ahu[i]
    
elif sei > hu and sei > hu+zero:
  hu+=zero
  for i in range((sei-hu)//2+1):
    ans-=(asei[i]-now)*(sei-hu-2*i)
    now=asei[i]

print(ans)

Solution (Python):
import numpy as np

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

for i in range(N):
    an[i] = an[i] - (i+1)
    
b = int(np.median(an))

k = []
for i in range(N):
    y = abs(an[i] - b)
    k.append(y)
ans = sum(k)

print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]-=i+1
a=sorted(a)
def f(x):
    ans=0
    for i in range(n):
        ans+=abs(x-a[i])
    return ans

if n%2==0:
    m=n//2
else:
    m=(n+1)//2

print(f(a[m-1]))

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]-=i+1
a=sorted(a)
def f(x):
    ans=0
    for i in range(n):
        ans+=abs(x-a[i])
    return ans

if n%2==0:
    m=n//2
else:
    m=(n+1)//2

print(f(a[m-1]))

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

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 a in A:
    ans += abs(a - b)

print(ans)

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

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

A.sort()
med = A[N // 2]
A = [abs(A[i] - med) for i in range(N)]

print(sum(A))

Solution (Python):
import sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict


MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

import numpy as np
from numba import i8, njit


@njit(i8(i8, i8[:]), cache=True)
def binary_search(n, a):
    right = np.max(a) + 10 ** 9
    left = np.min(a) - 10 ** 9

    def calc(b):
        score = 0
        for i in range(n):
            score += abs(a[i] - (b + i + 1))
        return score

    while right - left > 1:
        middle = (right + left) // 2
        if calc(middle) < calc(middle+1):
            right = middle
        else:
            left = middle
    
    return calc(right)

def Main():
    n = read_int()
    a = np.array(read_int_list(), dtype=np.int64)
    
    print(binary_search(n, a))

if __name__ ==  '__main__':
    Main()

Solution (Python):
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
a=lmp()
for i in range(n):
    a[i]=a[i]-(i+1)
a=sorted(a)
if n%2==1:
    x=a[n//2]
else:
    x=(a[n//2]+a[n//2-1])//2
ans=0
for i in range(n):
    ans+=abs(a[i]-x)
print(ans)

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

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

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

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

print(ans)

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

li = sorted([a[i]-(i+1) for i in range(n)])
if n%2==0:
    ave = (li[n//2]+li[n//2-1])//2
else:
    ave = li[(n-1)//2]

import math
ave1 = math.floor(ave)
ave2 = math.ceil(ave)

ll = []
c = 0
for i in range(n):
    c += abs(a[i]-(ave1+i+1))
else:
    ll += [c]

c =0
for i in range(n):
    c += abs(a[i]-(ave2+i+1))
else:
    ll += [c]

print(min(ll))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, *a = map(int, read().split())

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

a.sort()

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

ans = 0
for v in a:
    ans += abs(b-v)
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()

m1 = b[n//2]
s1 = sum([abs(b[i] - m1) for i in range(n)])

if n % 2 == 1:
    m1 = b[n//2]
    s1 = sum([abs(b[i] - m1) for i in range(n)])
    print(s1)
else:
    m1 = b[n//2-1]
    m2 = b[n//2]
    if (m1 + m2) % 2 == 0:
        l1 = (m1 + m2) // 2
        s1 = sum([abs(b[i] - l1) for i in range(n)])
        print(s1)
    else:
        l1 = (m1 + m2) // 2
        l2 = l1 + 1
        s1 = sum([abs(b[i] - l1) for i in range(n)])
        s2 = sum([abs(b[i] - l2) for i in range(n)]) 

        print(min(s1, s2))

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
ahu=[]
asei=[]
hu=0
ans=0
for i in range(1,n+1):
  if a[i-1]-i<0:
    hu+=1
    ahu.append(abs(a[i-1]-i))
  else:
    asei.append(a[i-1]-i)
  ans+=abs(a[i-1]-i)  
sei=n-hu
asei.sort()
ahu.sort()



rui=0
if sei<hu:
  for i in range((hu-sei)//2+1):
    ans-=(hu-sei-2*i)*(ahu[i]-rui)
    rui=ahu[i]
  print(ans)
elif sei>hu:
  for i in range((sei-hu)//2+1):
    ans-=(sei-hu-2*i)*(asei[i]-rui)
    rui=asei[i]
  print(ans)
else:
  print(ans)

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

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

if n % 2 == 1:
  res = b[(n-1)//2]
else:
  res = (b[n//2-1] + b[n//2])//2
  
print(sum(map(abs, [b[i]-res for i in range(n)])))

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

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

pin=b[n//2]

ans=0

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

print(ans)

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

Solution (Python):
N = int(input())
A = [a - i - 1 for i, a in enumerate(list(map(lambda x: int(x), input().split(" "))))]
A.sort()
 
ini = int(N/2)
m_abs = ""
sumlist = 0
for i in range(ini, len(A)):
  tmp = 0
  if i == ini:
    sumlist = - sum(A[:i]) + sum(A[i:])
  else:
    sumlist -= 2 * A[i]
 
  if 2 * i - N > 0:
    tmp = sumlist + (2 * i - N) * A[i - 1]
  else:
    tmp = sumlist + (2 * i - N) * A[i]
  if not m_abs or m_abs > tmp:
    m_abs = tmp
  if m_abs and m_abs <= tmp:
    break
    
print(m_abs)

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

cnt = 1
for i in range(N):
    A[i] = A[i] - cnt
    cnt += 1
A.sort(reverse=True)
medA = statistics.median(A)

ans = 0
cnt = 1
for j in range(N):
    ans += abs(A[j] - medA)
    cnt += 1

print(int(ans))

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

a=[a[n]-(n+1) for n in range(N)]
a.sort()
result=sum(a[N//2:N])-sum(a[:N//2]) if N%2==0 else sum(a[N//2+1:N])-sum(a[:N//2])
print(result)

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

A = [A[i]-(i+1) for i in range(N)]
A.sort()
cumsum = [0]*N
cumsum[0] = A[0]
for i in range(1, N):
    cumsum[i] = cumsum[i-1] + A[i]
ans = 1e20
for i in range(N):
    tmp = -(cumsum[i]) + (cumsum[N-1]-cumsum[i]) + (i+1)*A[i] - (N-i-1)*A[i]
    ans = min(ans, tmp)
print(ans)

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

Solution (Python):
import sys


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n = ni()
    A = nl()
    A = sorted(list(map(lambda x: A[x] - (x + 1), range(n))))
    b = A[n // 2]
    print(sum(list(map(lambda x: abs(x - b), A))))


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
A=list(map(int,input().split()))
if n==1:print(0);exit()
A=[A[i]-i-1 for i in range(n)]
B=sorted(A)



if n%2==1:
    d=B[n//2]
    print(sum([abs(A[i]-d) for i in range(n)]))
    exit()

ans=0
d=(B[n//2-1]+B[n//2])//2
print(sum([abs(A[i]-d) for i in range(n)]))

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

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

    b = A[N // 2]
    ans = sum(abs(a - b) for a in A)

    print(ans)
    return


if __name__ == '__main__':
    main()

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

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

print(sum(map(abs,[b[i]-c for i in range(n)])))

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 = median(b)
ans = 0
for i in range(n):
    ans += abs(b[i]-B)
print(int(ans))

Solution (Python):
from statistics import median

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

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

b = int(median(A))
ans = 0

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

print(ans)

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

ai.sort()


med = ai[N // 2]

ans = 0
for i in range(N):
    tmp = abs(ai[i] - med)
    ans += tmp
print(ans)

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

al = list(map(int, input().split()))
sl = [i for i in range(n)]

c = [x - y for (x, y) in zip(al,sl)]
cs = sorted(c)

m = n//2
b = cs[m]
ssl = [i+b for i in range(n)]

cc = [x-y for (x,y) in zip(al,ssl)]
res = sum(list(map(lambda x:abs(x),cc)))
print(res)

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

Solution (Python):


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

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

a.sort()

b = a[n//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] = A[i] - i
A.sort()

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

print(answer)

Solution (Python):

from statistics import median

n = int(input())
ar = list(map(int, input().split()))
ans = 0
temp = sorted([ai - i for i, ai in enumerate(ar, 1)])
b = median(temp)

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

print(int(ans))

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

B = sorted(B)

if len(B) % 2 == 1:
  ans = B[int((len(B) - 1) / 2)]
else:
  ans = int((B[int(len(B) / 2)] + B[int(len(B) / 2) - 1]) / 2)

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

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

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

arr.sort()

ans = []

s = 0
b = arr[n//2]
for i in range(n):
    s += abs(a[i] - (b + (i+1)))
ans.append(s)

if n == 1:
    print(ans[0])
    exit()
    
s = 0
b = arr[n//2 + 1]
for i in range(n):
    s += abs(a[i] - (b + (i+1)))
ans.append(s)

print(min(ans))

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

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

 
B = [A[i]-i-1 for i in range(N)]
 
point = statistics.median(B)
point = math.floor(point)
 
ans_list = []
ans = 0
for b in range(point-2 , point+2):
  for i in range(N):
    X = B[i]-b
    ans += np.abs(X)
  ans_list.append(ans)
  ans = 0

min_ans_list = min(ans_list)
print(min_ans_list)

Solution (Python):
import statistics

NN = int(input())
AA = list(map(int,input().split()))
BB = [0]*NN
for nn in range(1,NN+1):
    BB[nn-1] = AA[nn-1] - nn

MBB = statistics.median(BB)

CC = list(map(lambda x: x - MBB, BB))

ACC = list(map(lambda x: abs(x),CC))
ANS = sum(ACC)
print(int(ANS))

Solution (Python):

import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left, bisect_right 
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

N = int(input())
A = list(map(int, input().split()))
nA = [a-i-1 for i, a in enu(A)]


nA.sort()








midA1 = nA[N//2-1]
midA2 = nA[N//2]
res = min(sum([abs(a-midA1) for a in nA]), sum([abs(a-midA2) for a in nA]))
print(res)

Solution (Python):
import numpy as np
n = int(input())
a = [int(i)- k-1 for k,i in enumerate(input().split())]
ans = 10**9
a = np.array(a,dtype = 'int64')
median = int(np.median(a))

print(np.sum(np.abs(a-median)))

Solution (Python):
import numpy as np

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

diff = A - (np.arange(N) + 1)
diff.sort()

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

print(np.sum(np.abs(diff - median)))

Solution (Python):
import sys
import numpy as np
input = sys.stdin.readline


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


def main():
    np.set_printoptions(threshold=20)
    N = int(input())
    l = list(map(int, input().rstrip().split()))
    for i, v in enumerate(l):
        l[i] = v - (i + 1)
    l.sort()
    now = 0
    for v in l:
        now += abs(v - (l[0] - 1))
    right_count = N
    left_count = 0
    ans = now
    before = l[0] - 1
    for v in l:
        now -= right_count * (v - before)
        now += left_count * (v - before)
        right_count -= 1
        left_count += 1
        ans = min(now, ans)
        before = v
    print(ans)


if __name__ == '__main__':
    main()

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

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

a_sub_i.sort()

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

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

Solution (Python):

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))
for i in range(N):
    A[i] -= (i+1)
A = sorted(A)
k = N // 2 
b = A[k]
ans = 0
for i in range(N):
    ans += abs(A[i]-b)
print(ans)

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

Solution (Python):
import statistics
import math
n = int(input())
a = list(int(x)-i-1 for i,x in enumerate(input().split()))
b = statistics.median(a)
print(math.floor(sum(abs(j-b) for j in a)))

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
import numpy as np
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    n = int(readline())
    a = np.array(readline().split(), np.int64)
    a -= np.arange(1, n + 1)
    median = np.median(a).astype(np.int64)

    print(np.abs(a - median).sum())



if __name__ == '__main__':
    main()

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

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

    

ans = 0
for i in range(N):
    ans += abs(a[i]-(med))
print(ans)

Solution (Python):
import copy

n = int(input())

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

asort = copy.copy(a)
asort.sort()

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

ans = 0

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

print(ans)

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

Solution (Python):
import statistics
N = int(input())
L = input().split()
A = sorted(int(L[X])-(X+1) for X in range(0,N))
B = int(statistics.median(A))
Disp = sum(abs(A[X]-B) for X in range(0,N))
print(Disp)

Solution (Python):
from numpy import *
N = int(input())
A = array(list(map(int,input().split())))
B = array(sorted([A[n]-(n+1) for n in range(N)]))
print(sum(abs(B-int(median(B)))))

Solution (Python):
from numpy import *
N = int(input())
A = list(map(int,input().split()))
B = array(sorted([A[n]-(n+1) for n in range(N)]))
print(sum(abs(B-int(median(B)))))

Solution (Python):
import collections
n = int(input())
a = list(map(int, input().split()))
if (n==1):
    print(0)
    exit()
for i in range(n):
    a[i] -= i+1
a.sort()
ans1 = 0
ans2 = 0
x = a[n//2]
y = a[n//2-1]
for i in range(n):
    ans1 += abs(a[i]-x)
    ans2 += abs(a[i]-y)
print(min(ans1,ans2))

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

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

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

aa = sorted(aa)
b1 = aa[n//2]
b2 = aa[n//2 + 1]
ans = min(
    sum([abs(a - b1) for a in aa]),
    sum([abs(a - b2) for a in aa])
)
print(ans)

Solution (Python):

import math
N = int(input())

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


B = sorted([a - i for i, a in enumerate(A, start=1)])

ans = []

if N % 2 == 1:
    b = B[N // 2]
    ans.append(sum([abs(x - b) for x in B]))
else:
    b_left = (B[N // 2 - 1] + B[N // 2]) // 2
    b_right = math.ceil((B[N // 2 - 1] + B[N // 2]) / 2)
    ans.append(sum([abs(x - b_left) for x in B]))
    ans.append(sum([abs(x - b_right) for x in B]))

print(min(ans))

Solution (Python):
from math import ceil
n = int(input())
arr = list(map(int, input().split()))
B = []
for i in range(n):
    B.append(arr[i] - (i+1))
B.sort()
b1 = B[n//2]
b2 = B[n//2]
if n > 1:
	b2 = B[int(ceil(n/2))]
ans1, ans2 = 0, 0
for i in range(n):
    ans1 += abs(arr[i]-(b1+i+1))
    ans2 += abs(arr[i]-(b2+i+1))
print (min(ans1, ans2))

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

a.sort()

s = 0
for i in a:
    s += abs(i)
if abs(a[(n-1)//2]) > abs(a[n//2]):
    t = a[(n-1)//2]
else:
    t = a[n//2]
ans = 0
for i in a:
    ans += abs(i-t)

print(ans)

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

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

a.sort()
ans = 0
b = a[n//2]
for i in range(n):
    ans += abs(a[i]-b)
if n%2 == 0:
    ans2 = 0
    b2 = a[n//2 - 1]
    for i in range(n):
        ans2 += abs(a[i]-b2)

if n%2 != 0:
    print(ans)
else:
    print(min(ans,ans2))

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

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

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

import math

B = sorted([a-i for i,a in enumerate(A, start=1)])

ans = []

if N%2 == 1:
    b = B[N//2]
    ans.append(sum([abs(x - b) for x in B]))
else:
    b_left = (B[N//2 - 1] + B[N//2])//2
    b_right = math.ceil((B[N//2 - 1] + B[N//2])/2)
    ans.append(sum([abs(x - b_left) for x in B]))
    ans.append(sum([abs(x - b_right) for x in B]))

print(min(ans))

Solution (Python):
n = int(raw_input())
ais = map(int, raw_input().split()) 
bis = sorted([ai - i - 1 for i,ai in enumerate(ais)])
if len(bis) % 2:
	b = bis[len(bis)/2]
else:
	b = (bis[len(bis)/2 -1] + bis[len(bis)/2]) /2
	

q = 0
for i in range(len(ais)):
	u = i+1
	q += abs(ais[i] - (b+u))
print q

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

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

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

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

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

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

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

Solution (Python):
import sys
import numpy as np
import math
import copy
input = sys.stdin.readline
 
N = int(input())
A = np.array(list(map(int,input().split())))
if N ==1:
    ans = 0
else:
    r = np.array(list(range(1,N+1)))
    B = np.array(sorted(A-r))
    ans = float('inf')
    for i in range(max(N//2-1,0),min(N//2+2,N)):
        c = list(map(abs,(B - B[i])))
        ans = min(ans,sum(c))
print(ans)

Solution (Python):

from statistics import median

n = input()
a_lst = list(map(int, input().split(" ")))

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

good_b = median(each_b)

total = 0
for (i, a) in enumerate(a_lst):
    total += abs(a - (good_b + i + 1))

print(int(total))

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

l=[]
for i in a:
    l.append(i-count)
    count+=1
import numpy
l=numpy.array(l)
b=numpy.median(l)
ans=0
for i in l:
    ans+=abs(i-b)
print(int(ans))