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 = sorted(int(a) - i for i, a in enumerate(input().split(), 1))
if N % 2:
    median = A[N // 2]
    print(sum(abs(a - median) for a in A))
else:
    median1 = A[N // 2 - 1]
    median2 = A[N // 2]
    print(min(sum(abs(a - median1) for a in A), sum(abs(a - median2) for a 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:
    median = A[N // 2]
    print(sum(abs(a - median) for a in A))
else:
    median1 = A[N // 2 - 1]
    median2 = A[N // 2]
    print(min(sum(abs(a - median1) for a in A), sum(abs(a - median2) for a 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.sort()
k=B[N//2]

C=map(lambda x:abs(x-k),B)
print(sum(C))

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-1)//2]
else:
    b=a[n//2]

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

print(ans)

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def power(a,n,mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n-1
    while(tmp >= l):
        a = a*tmp%mod
        tmp -= 1
    return a

inf = 10**18
mod = 10**9+7

n = ir()
a = lr()
total = 0
for i,num in enumerate(a):
    a[i]=(num-(i+1))
a.sort()
if n%2 == 0:
    mean = (a[n//2-1]+a[n//2])//2
else:
    mean = a[n//2]
ans = [0,0]
for i in range(mean, mean+2):
    tmp = i%2
    for num in a:
        ans[tmp]+=abs(num-i)
print(min(ans))

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = []
    for i,ai in enumerate(ipt().split()):
        a.append(int(ai)-i-1)
    a.sort()
    b = a[n//2]
    ans = 0
    for i in a:
        ans += abs(i-b)
    print(ans)


    return

if __name__ == '__main__':
    main()

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

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

print(int(ans))

Solution (Python):
n = int(input())
a = [int(x) for x in input().split()]
for i in range(1, n+1):
    a[i-1] -= i 
a.sort()
b = n // 2
if n % 2 == 1:
    b = a[n//2]
else:
    b = (a[n//2] + a[n//2 - 1])//2
ans = 0
for x in a:
    ans += abs(x - b)
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()
flag = True
if n % 2 == 1:
    b = A[(n-1)//2]
else:
    if A[n//2] == A[n//2-1]:
        b = A[n//2]
    else:
        flag = False
if flag:
    ans = 0
    for i in A:
        ans += abs(i-b)
    print(ans)
else:
    ans1=0
    ans2=0
    for i in A:
        ans1 += abs(i-A[n//2])
        ans2 += abs(i-A[n//2-1])
    print(min(ans1,ans2))

Solution (Python):
import math

def isinteger(n):
    if isinstance(n, int):
        return True
    elif isinstance(n,float):
        return n.is_integer()
    return False

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-1)//2]
else:
    b = (A[n//2]+A[n//2]-1)/2
if isinteger(b):
    ans = 0
    for i in A:
        ans += abs(i-b)
    print(ans)
else:
    ans1=0
    ans2=0
    b1= math.floor(b)
    b2=b1+1
    for i in A:
        ans1 += abs(i-b1)
        ans2 += abs(i-b2)
    print(min(ans1,ans2))

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

A = sorted([a-i-1 for i, a in enumerate(A)])
i = int(len(A)/2)
b = A[i]

print(sum([abs(a-b) for a 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:
    b = a[n//2]
    ans = 0
    for i in range(n):
        ans += abs(a[i] - b)
    print(ans)
else:
    b1 = (a[n//2-1] + a[n//2] + 1) // 2
    b2 = (a[n//2-1] + a[n//2]) // 2
    ans1, ans2 = 0, 0
    for i in range(n):
        ans1 += abs(a[i] - b1)
        ans2 += abs(a[i] - b2)
    print(min(ans1, ans2))

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

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

rlt = 0
n = N//2
for a in As:
  rlt += abs(a-As[n])

print(rlt)

Solution (Python):
from statistics import median


from fractions import gcd














import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
for i in range(1,n+1):
    A[i-1] -= i

medi = median(A)
medi = int(medi) if medi - int(medi) < 0.5 else int(medi) + 1
ans = 0
for i in range(n):
    ans += abs(A[i] - medi)
print(ans)

Solution (Python):
import sys
import numpy as np
n = int(input())
arr = np.array(list(map(int, input().split())))

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

diff.sort()

diff = diff - np.median(diff)

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

Solution (Python):
import numpy as np

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

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

b = int(np.median(diff))

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

print(ans)

Solution (Python):
N = int(input())
*A, = map(int, input().split())
l = [j-i for i, j in enumerate(A, start=1)]
l.sort()

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

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

c1=a[n//2-1]
c2=a[n//2]
ans=float('inf')

for c in [c1,c2]:
    tmp=0
    for i in range(n):
        tmp+=abs(a[i]-c)
    ans=min(ans, tmp)
print(ans)

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

Solution (Python):






from collections import deque



import bisect

n=int(input())
a=list(map(int,input().split()))
c=[0]*n
for i in range(n):
    c[i]=a[i]-(i+1)
c.sort()
ans=0
if n%2==1:
  p=(n+1)//2-1
  b=c[p]
  for i in range(n):
    ans+=abs(c[i]-b)
  print(ans)
else:
  p=n//2
  b=(c[p-1]+c[p])/2
  b=round(b)
  for i in range(n):
    ans+=abs(c[i]-b)
  print(ans)

Solution (Python):
from statistics import median

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

for i in range(N):
    B.append(A[i]-i-1)
B.sort()

b=median(B)

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

print(int(ans))

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

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

c.sort()
b = c[n//2]
ans = 0
for j in range(n):
    ans += abs(c[j] - b)

print(ans)

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

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

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

B.sort()

b=B[n//2]

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

print(s)

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

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

left = -10**10
right = 10**10

def get_score(b):
    score = 0
    for i in range(N):
        score += abs(A[i]-b-i)
    return score

while(right > left + 1):
    mid = (left+right) // 2
    if get_score(mid+1) - get_score(mid) < 0:
        left = mid
    else:
        right = mid

print(get_score(right))

Solution (Python):

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)



import itertools
import math

from bisect import bisect_left,bisect_right

n=n0()
A=n1()

A2=[A[i-1]-i for i in range(1,n+1)]
A2.sort()

if n%2==1:
    b=A2[n//2]
    ans=sum([abs(A[i-1]-i-b) for i in range(1,n+1)])
else:
    b1=A2[n//2-1]
    b2=A2[n//2]
    ans1=sum([abs(A[i-1]-i-b1) for i in range(1,n+1)])
    ans2=sum([abs(A[i-1]-i-b2) for i in range(1,n+1)])
    ans=min(ans1,ans2)
print(ans)

Solution (Python):

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)



import itertools
import math

from bisect import bisect_left,bisect_right

n=n0()
A=n1()

A2=[A[i-1]-i for i in range(1,n+1)]
A2.sort()

if n%2==1:
    b=A2[n//2]
    ans=sum([abs(A[i-1]-i-b) for i in range(1,n+1)])
else:
    b1=A2[n//2-1]
    b2=A2[n//2]
    ans1=sum([abs(A[i-1]-i-b1) for i in range(1,n+1)])
    ans2=sum([abs(A[i-1]-i-b2) for i in range(1,n+1)])
    ans=min(ans1,ans2)
print(ans)

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

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

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

Solution (Python):
n = int(input())
x = [int(i) for i in input().split()]
c = []
for i,xi in enumerate(x):
  c.append(xi-i-1)
c.sort()
if n%2 == 1:
  b = c[n//2]
else:
  b = (c[n//2-1]+c[n//2])//2
ans = 0
for i in c:
  ans += abs(i-b)
print(ans)

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

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

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

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

c = []
for i in range(n):
    c.append(abs(b[i] - median))

print(sum(c))

Solution (Python):


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

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

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

for i in range(n):
    list_A[i] -= i + 1
list_A.sort()
b = 0
if n % 2 == 1:
    b = list_A[n//2]
else:
    b = (list_A[n//2]+list_A[n//2-1])//2

ans = 0

for num in list_A:
    ans += abs(num-b)

print(ans)

Solution (Python):
import statistics
def main():
    N, A = int(input()), list(map(int, input().split()))
    for i in range(N):
        A[i] -= i + 1
    m = int(statistics.median(A))
    a, b = m, m + 1
    c, d = 0, 0
    for el in A:
        c += abs(el-a)
        d += abs(el-b)
    print(min(c, d))
main()

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

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

s.sort()
a = s[(n+1)//2 - 1]

res = 0
for ss in s:
    res += abs(ss - a)
print(res)

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

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

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

sum = 0
for i in A:
    sum += abs(i-median)
print(int(sum))

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

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

dic=defaultdict(int)
result=0
posi=0

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

sort_dic=sorted(dic.items())

for j in sort_dic:
    if posi+j[1]>N//2:
        siki=j[0]
        break
    else:
        posi+=j[1]

for k in sort_dic:
    result+=abs(k[0]-siki)*k[1]

print(result)

Solution (Python):
n = int(input())
A = [a-i-1 for i, a in enumerate(map(int, input().split()))]
if n & 1:
    mid = n//2
else:
    mid = (n-1)//2
median = sorted(A)[mid]
print(sum(map(lambda x: abs(x-median), A)))

Solution (Python):
def calc(b,A):
  ret=0
  for i,num in enumerate(A):
    ret += abs( num-(b+i+1) )
  return ret    


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

L=-1*10**9
R=10**9
i=(L+R)//2

while True:
  s=calc(i-1,A)
  t=calc(i,A)
  u=calc(i+1,A)
  if s<t<u:
    R=i
    i=(L+R)//2
  elif s>t>u:
    L=i
    i=(L+R)//2
  else:
    print(t)
    break

Solution (Python):
def main():
    N = int(input())
    A = [x - i for i, x in enumerate(map(int, input().split()), start=1)]
    A.sort()

    m = A[N // 2]  

    ans = sum(abs(x - m) for x in A)

    print(ans)


if __name__ == '__main__':
    main()

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

ave = B[N//2]
ans = 0
for i in range(N):
    ans += abs(B[i]-ave)
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()

ave1,ave2 = B[N//2],B[N//2-1]
ans1,ans2 = 0,0
for i in range(N):
    ans1 += abs(B[i]-ave1)
    ans2 += abs(B[i]-ave2)
print(ans1)

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

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

b = []

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

kb = [b[n//2],b[n//2]]

ans = []

for i in kb:
    x = 0
    for s in range(len(a)):
        x += abs(a[s]-i-s)
    ans.append(x)
    
print(min(ans))

Solution (Python):
import numpy as np  







import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    N=int(input())
    A=list(map(int,input().split()))
    B=[0]*N
    for i in range(N):
        B[i]=A[i]-(i+1)
    val=np.median(B)

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

    

    
resolve()

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

B = []
for i,a in enumerate(A):
    B.append(a-(i+1))
B.sort()
C = B[N//2-1:N//2+2]

MIN = 10**18
for j in C:
    ans = 0
    for i in B:
        ans += abs(i-j)

    MIN = min(ans,MIN)

print(MIN)

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

B.sort()

ans = 0
t = B[len(B)//2]

for x in B:
    ans += abs(x - t)

print(ans)

Solution (Python):
import sys
import statistics
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    b = statistics.median(A)

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

    print(int(res))


if __name__ == '__main__':
    resolve()

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()
lb = [B[N//2]-1,B[N//2]]

sad = float("inf")
for b in lb:
  c = 0
  for j in range(N):
    c += abs( A[j]-(b+j+1) )
  sad = min(sad,c)
print(sad)

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

ave1,ave2 = B[N//2],B[N//2-1]
ans1,ans2 = 0,0
for i in range(N):
    ans1 += abs(B[i]-ave1)
    ans2 += abs(B[i]-ave2)
print(min(ans1,ans2))

Solution (Python):
def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    a1 = []
    for i in range(len(a)):
        a1.append(a[i]-i-1)
    a2 = sorted(a1)
    if len(a2)%2 == 0:
        mda = a2[len(a2)//2]
    else:
        mda = a2[(len(a2)-1)//2]
    ans = 0
    for i in range(len(a2)):
        ans += abs(mda-a2[i])
    print(ans)
resolve()

Solution (Python):
n=int(input())
b=[int(a-(i+1))  for i,a in enumerate(list(map(int,input().split())))]
if n==1:
  print(0)
  exit(0)
bm=b[:]
bm.sort()
mid_1=bm[n//2]
mid_2=bm[(n//2)+1]
ans_1,ans_2=0,0
if n%2==1:
  for bb in b:
    ans_1+=abs(bb-mid_1)
  print(ans_1)
else:
  for bb in b:
    ans_1+=abs(bb-mid_1)
    ans_2+=abs(bb-mid_2)
  print(min(ans_1,ans_2))

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()
c=b[n//2]
ans=100000000000000000000
for i in range(c-2,c+3):
  temp=0
  for j in range(n):
    temp+=abs(b[j]-i)
  if temp<ans:
    ans=temp
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


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


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, read().split())))
    return tuple(map(list, zip(*ret)))


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


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

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  



N = read_a_int()
A = read_ints()



B = []
for i, a in enu(A, start=1):
    B.append(a - i)
import numpy as np
b = np.median(B)
ans = 0
print(int(np.abs(np.array(B) - b).sum()))

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

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

print(int(ans))

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

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

N = int(input())

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

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

tmp = A[N // 2]

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

print (ans)

Solution (Python):
n = int(input())
ll = list(map(int,input().split()))
li = [l-i for i,l in enumerate(ll)]
import statistics
median = statistics.median(li)
ans = 0
for l in li:
    ans+= abs(l-median)
print(int(ans))

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
c = [a[i]-i-1 for i in range(n)]
c.sort()
mn = s = sum(c[1:])-(n-1)*c[0]
for i in range(n-1):
    s += (2*i+2-n)*(c[i+1]-c[i])
    mn = min(mn,s)
print(mn)

Solution (Python):
def main():
    N, *A = map(int, open(0).read().split())
    B = [A[i] - i - 1 for i in range(N)]
    B.sort()
    b1 = B[(N-1)//2]
    b2 = B[N//2]
    ans1 = ans2 = 0
    for i in range(N):
        a = A[i] - i - 1
        ans1 += abs(a - b1)
        ans2 += abs(a - b2)
    print(min(ans1, ans2))

if __name__ == '__main__':
  main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, *a = map(int, read().split())
a = sorted(aa - i for i, aa in enumerate(a))
print(sum(a[n // 2:]) - sum(a[:(n + 1) // 2]))

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

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

b = statistics.median(x)

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

print(int(ans))

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

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

x.sort()
x_ = []
b = 0
if x.count(0) <= n//2:
    for i in range(n):
        if x[i] != 0:
             x_.append(x[i])

    b = statistics.median(x_)

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

print(int(ans))

Solution (Python):
import math
n=int(input())
res = [0]*n
A=[int(i) for i in input().split()]
for i in range(n):
    res[i]=(A[i]-(i+1))
res.sort()

if n%2==1:
    ans = sum([abs(i-res[n//2]) for i in res])
else:
    b0 = (res[n//2-1]+res[n//2])//2
    b1 = (res[n//2-1]+res[n//2])
    ans = min(sum([abs(a-b0) for a in res]), sum([abs(a-b1) for a in res]))
print(ans)

Solution (Python):
import math
n=int(input())
res = [0]*n
A=[int(i) for i in input().split()]
for i in range(n):
    res[i]=(A[i]-(i+1))
res.sort()

if n%2==1:
    ans = sum([abs(i-res[n//2]) for i in res])
else:
    b0 = (res[n//2-1]+res[n//2])//2
    b1 = math.ceil(res[n//2-1]+res[n//2])
    ans = min(sum([abs(a-b0) for a in res]), sum([abs(a-b1) for a in res]))
print(ans)

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

b = B[n//2]

total = 0

for i in B:
    total += abs(i - b)
print(total)

Solution (Python):
import math
N = int(input())
A = sorted([int(v)-i for i, v in enumerate(input().split(), start=1)])

if N % 2 == 1:
    ans = sum([abs(a-A[N//2]) for a in A])
else:
    b0 = (A[N//2-1]+A[N//2])//2
    b1 = math.ceil(A[N//2-1]+A[N//2])
    ans = min(sum([abs(a-b0) for a in A]), sum([abs(a-b1) for a in A]))

print(ans)

Solution (Python):




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

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

ami.sort()
medi = ami[n // 2]

wk_val = 0
for j in range(n):
    wk_val = wk_val + abs(a[j]-(medi+j+1))

ans = wk_val


print(ans)

Solution (Python):
def main(n,a):
  a=sorted([a[i]-i for i in range(n)])
  m0=a[n//2]
  m1=a[n//2-1]
  ans0,ans1=0,0
  for i in range(n):
    ans0+=abs(a[i]-m0)
    ans1+=abs(a[i]-m1)
  print(min(ans0,ans1))
if __name__=='__main__':
  import sys
  input = sys.stdin.readline
  n=int(input())
  a=list(map(int,input().split()))
  main(n,a)

Solution (Python):
import statistics as stat
import math
N = int(input())
A = list(map(int, input().split()))
linear = [i+1 for i in range(N)]
B = [x-y for (x, y) in zip(A, linear)]
med = stat.median(B)
med_up = math.ceil(med)
med_low = math.floor(med)
count_up = 0
count_low = 0
for i in range(N):
    count_up += abs(B[i] - med_up)
    count_low += abs(B[i] - med_low)
print(min(count_up, count_low))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A = [a - i - 1 for i, a in enumerate(A)]
    A.sort()
    i = N // 2
    b = A[i]
    ans = 0
    for a in A:
        ans += abs(a - b)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math  
import bisect  
import queue  


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


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

    A = [a - (i + 1) for i, a in enumerate(A)]
    A.sort()
    b = A[(N + 1) // 2 - 1]

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

    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
INF = 114514191981036436433-4
bl = []

for i in range(n):
    bl.append(a[i] - (i+1))
    
bl.sort()
d = bl[0]
c = [bl[i]-d for i in range(n)]

ans = sum(c)
cur = sum(c)

for i in range(1,n):
    e = c[i] - c[i-1]
    cur = cur + i * e - (n-i) * e
    ans = min(cur,ans)
    
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]





n=ii()
arr=limii()
for i in range(n):
    arr[i]-=i+1

arr.sort()

def med(x):
    h = int(n/2)
    if n%2==0:
        return (arr[h-1]+arr[h])//2
    else:
        return arr[int((n-1)/2)]

ans=10**100
if n%2 ==0:
    ans1=0
    ans2=0
    m=med(arr)
    for i in range(n):
        ans1+=abs(arr[i]-m)
        ans2+=abs(arr[i]-(m+1))
    ans=min(ans1,ans2)
else:
    m=med(arr)
    ans1=0
    for i in range(n):
        ans1+=abs(arr[i]-m)
    ans=ans1
print(ans)

Solution (Python):
_,a=open(0);S=sorted(int(x)-i for i,x in enumerate(a.split()));print(sum(abs(S[len(S)//2]-s)for s in S))

Solution (Python):
_,a=open(0)
S=sorted(int(x)-i for i,x in enumerate(a.split()))
print(sum(abs(S[len(S)//2]-s)for s in S))

Solution (Python):
input();S=sorted(int(x)-i-1 for i,x in enumerate(input().split()))
print(sum(abs(S[len(S)//2]-s)for s in S))

Solution (Python):
N=int(input())
B=sorted(int(x)-i-1 for i,x in enumerate(input().split()))
def sad(x):
    return sum(abs(b-x)for b in B)
print(sad(B[N//2]))

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
a = list(map(int, readline().split()))
a = sorted(x - i for i, x in enumerate(a))
low = (len(a) + 1) // 2 - 1
high = len(a) // 2
print(sum(a[high:]) - sum(a[:low + 1]))

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

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

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

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

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

median = statistics.median(bi)

ans = 0
for i in range(n):
    ans += abs(a[i]-(median+i+1))
print(int(ans))

Solution (Python):
n = int(input())
A = list(map(int,input().split()))
A = [j-i-1 for i,j in enumerate(A)]
top = max(A)
bottom = min(A)
def sad(b):
  ret=0
  for i in A:
    ret += abs(i-b)
  return ret
while top - bottom > 2:
  mid1 = (top + bottom*2)//3
  mid2 = (top*2 + bottom)//3
  if sad(mid1) < sad(mid2):
    top = mid2
  else:
    bottom = mid1
print(min(sad(bottom), sad((bottom+top)//2), sad(top)))

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter
import math

def main():
    N = int(input())
    A = [int(a) - i for i, a in enumerate(input().split(), 1)]
    A.sort()

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

    
main()

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

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

print(ans)

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

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

    print(ans)
else:
    b1 = A_i[N // 2]
    b2 = A_i[N // 2 - 1]
    ans1 = 0
    ans2 = 0
    for a in A_i:
        ans1 += abs(a - b1)
        ans2 += abs(a - b2)
    print(min(ans1, ans2))