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):
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    b = []
    for i, v in enumerate(a):
        b.append(v - (i + 1))
    b.sort()
    t = b[len(b) // 2]
    s = 0
    for i, v in enumerate(a):
        s += abs(v - (t + (i + 1)))
    print(s)


if __name__ == '__main__':
    slove()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a = [i-idx-1 for idx,i in enumerate(a)]
import statistics as st
b = st.median(a)
print(int(sum([abs(i-b) for i in a])))

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

Solution (Python):
from statistics import median
import math
n = int(input())
a = [int(i) for i in input().split()]
for i in range(n):
    a[i] -= i+1
a_fl = math.floor(median(a))
a_ce = math.ceil(median(a))
ans_fl=ans_ce=0

for i in range(n):
    ans_fl += abs(a[i]-a_fl)
    ans_ce += abs(a[i]-a_ce)
print(int(min(ans_fl,ans_ce)))

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

n = I()
a = LI()
if n == 1:
    print(0)
    quit()
for i in range(n):
    a[i] -= i+1
a.sort()
b = a[n>>1]
ans = 0
for i in a:
    ans += abs(i-b)
if n%2:
    b = a[(n>>1)+1]
    ans_ = 0
    for i in a:
        ans_ += abs(i-b)
    if ans > ans_:
        ans = ans_
    b = (a[(n>>1)+1]+a[n>>1])>>1
    ans_ = 0
    for i in a:
        ans_ += abs(i-b)
    if ans > ans_:
        ans = ans_
print(ans)

Solution (Python):


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

amin=float('inf')
for i in range(n):
    a[i]-=i+1

a.sort()
b=a[n//2]
ans=0
for e in a:
    ans+=abs(e-b)
print(ans)

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


if N %2 == 1:
    ans = A[(N-1)//2]
    t = 0
    for i in range(N):
        t += abs(A[i]-ans)
    ans = t

else:
    ans1 = A[(N)//2]
    ans2 = A[(N)//2 -1]
    t = 0
    for i in range(N):
        t += abs(A[i]-ans1)
    s = 0
    for i in range(N):
        s += abs(A[i]-ans2)
    ans = min(t, s)

print(ans)

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

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

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

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

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

A_diff.sort()
A_diff.reverse()

print(sum(list(map(lambda x : abs(x - A_diff[N//2]), A_diff))))

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

    b = c[n // 2]
    sad = sum([abs(cc - b) for cc in c])
    print(sad)


main()

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

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

Solution (Python):
from statistics import median
import math
n = int(input())
a = list(map(int,input().split()))
for i in range(0,n):
    a[i] = a[i]-(i+1)
b1 = round(median(a)) 
a1 = []
a2 = []
for i in range(0,n):
    a1.append(abs(a[i]-b1))
print(sum(a1))

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



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


print(str(grief))

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

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

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

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

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

print(ans)

Solution (Python):

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


if __name__ == "__main__":
    main()

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

Solution (Python):
from statistics import median
N = int(input())
As = list(map(int,input().split()))
calcA = sorted([As[i]-(i+1) for i in range(len(As))])
med = median(calcA)
print(int(sum([abs(As[i]-(med+i+1)) for i in range(len(As))])))

Solution (Python):
import sys
import numpy as np


def main():
    n = int(input())
    a = np.array([int(x) for x in input().split()])
    a -= np.arange(1, n + 1)
    a -= int(np.median(a))
    print(np.sum(np.abs(a)))


main()

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

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 == 0:
    center = (a[n//2] + a[n//2-1]) // 2
else:
    center = a[(n-1)//2]
sub = lambda x: abs(x - center)
print(sum(list(map(sub, a))))

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

b = A_[N//2]
print(sum([abs(ai-b) for ai in A_]))

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

if N % 2 != 0:
    b = A[(N+1)//2 - 1]
    print( sum( [abs(x-b) for x in A] ) )
else:
    mf,mb = A[N//2-1], A[N//2]
    if mb - mf >= 2:    b = mb -1
    else:  b = mb
    print( sum( [abs(x-b) for x in A] ) )

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    a[i]-=(1+i)
a.sort()
b = a[n//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()))

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

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

a = sorted([aa - i for i, aa in enumerate(a, start = 1)])
b = a[n//2] if n%2 > 0 else (a[n//2-1]+a[n//2])//2
ans = sum([abs(aa - b) for aa in a])
print(ans)

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

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

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

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

total=0
for i in a_list:
    total+=abs(i-a_list[n//2])
print(total)

Solution (Python):
import math
import numpy as np
N = int(input())
A = [int(_) for _ in input().split()]
B = [A[i] - i for i in range(N)]
B.sort()
C = np.array(B)
print(np.sum([abs(C[i]-C[math.floor(N/2)]) for i in range(N)]))

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

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

l = sorted([ x - (idx+1) for x,idx in enumerate(A)])


import statistics
median = statistics.median(l)


ans = 0
for x in l:
  ans += abs(x - median)
  
print(int(ans))

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

Solution (Python):
N = int(input())
li = [ int(it) for it in input().split() ]
li = [ li[i]-i-1 for i in range(N) ]
li.sort()

p = li[N//2]
pi = [ abs(it-p) for it in li ]
print ( sum(pi) )

Solution (Python):
N = int(input())
li = [ int(it) for it in input().split() ]
li = [ li[i]-i-1 for i in range(N) ]
li.sort()

p = li[N//2]
pi = [ abs(it-p) for it in li ]
print ( sum(pi) )

Solution (Python):


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

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

A.sort()

center1 = A[N//2]
if N == 1:
    center2 = 10 ** 9
else:
    center2 = A[(N+2)//2]

ans1 = 0
for i in range(N):
    ans1 +=abs(A[i]-center1)
    
ans2 = 0
for j in range(N):
    ans2 += abs(A[j]-center2)
    
print (min(ans1, ans2))

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

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

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

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
B = [a - i for i, a in enumerate(A)]
B.sort()
def median(list):
    L = sorted(list)
    n = len(L)
    m = int(n/2)
    if n % 2 == 0:
        return (L[m - 1] + L[m]) / 2
    else:
        return L[(n - 1) // 2]
b = int(median(B))
print(sum(abs(x - b) for x in B))

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

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

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

s=0
for i in aa:
  s+=abs(i-b)
print(int(s))

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

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

Bs = sorted(B)
if n%2 == 1:
    b = Bs[n//2]
else:
    b = (Bs[n//2-1]+Bs[n//2])//2
ans = 0
for i in B:
    ans += abs(i-b)
print(ans)

Solution (Python):
N = int(input())
A = [int(i) for i in 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()))

aa = [ai - i-1 for i,ai in enumerate(a)]

def tri_search(f:"f(x:float)->float", left, right, iter=100)->float:
    for _ in range(iter):
        ml = (left*2 + right) / 3
        mr = (left + right*2) / 3
        if f(ml) < f(mr):
            right = mr
        else:
            left = ml
    
    return (right + left) / 2

def f(x):
    ret = 0
    x = int(x+0.5)
    for aai in aa:
        ret += abs(aai - x)
    return ret

b = tri_search(f, -10**9, 10**9)
print(min(f(b), f(b+1), f(b-1)))

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

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

Solution (Python):
def mm(N, A, x):
  S = 0
  for i in range(N):
    S += abs(A[i] - x)
  return S

N = int(input())
A = []
j = 0
for i in input().split():
  j += 1
  A.append(int(i)-j)
A.sort()
if N % 2 == 0:
  print(mm(N, A, A[N//2]))
elif N == 1:
  print(0)
else:
  print(min(mm(N, A, A[N//2]), mm(N, A, A[N//2 + 1])))

Solution (Python):
N = int(input())
A = list(map(int,input().split(' ')))
num = 0
X = []
for i,j in enumerate(A):
  B = j-(i+1)
  X.append(B)
X.sort()
median = 0
if N % 2 == 0:
  median = (X[int(N/2)] + X[int(N/2-1)])/2
else:
  median = X[int((N-1)/2)] 

for x in X:
  num += abs(x-median)
print(int(num))

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

a = sorted([aa-i for i, aa in enumerate(a, start = 1)])
med = (a[n//2-1]+a[n//2])//2 if n%2 == 0 else a[n//2]
ans = sum([abs(aa - med) for aa in a])
print(ans)

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

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

if N % 2 == 1:
    median = A[N//2]
    sad = sum([abs(A[i] - median) for i in range(N)])
else:
    hoge, fuga = (A[N//2-1]+A[N//2])//2, (A[N//2-1]+A[N//2])//2+1
    sad = min(sum([abs(A[i] - hoge) for i in range(N)]), sum([abs(A[i] - fuga) for i in range(N)]))
print(sad)

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

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

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

l.sort()
t = l[int(len(l) / 2)]

for i in range(len(l)):
    l[i] = abs(l[i] - t)
    
print(sum(l))

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

B = [a - i for i, a in enumerate(A)]
B.sort()
median = B[(N - 1) // 2]
print(sum(abs(b - median) for b in B))

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



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

Solution (Python):
import statistics
import math
N = int( input())
temp = list(map(int,input().split(" ")))
for i in range(len(temp)):
    temp[i] = (temp[i] - (i+1))

m = statistics.median(temp)
nums = list(map(lambda x:abs(x-m),temp))
ans = sum(nums)
ans = int(ans)
print(ans)

Solution (Python):
from math import ceil

N = int(input())
A = [int(c) - i for i, c in enumerate(input().split())]

A.sort()

median = A[ceil((N - 1) /2)]

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

print(num)

Solution (Python):
N = int(input())
src = list(map(int,input().split()))
 
dis = [a-i-1 for i,a in enumerate(src)]
center = sorted(dis)[N//2]
 
ans = 0
for a in dis:
    ans += abs(a - center)
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)
mid = B[N // 2]
num = 0
for i in range(N):
    num += abs(B[i] - mid)

print(num)

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()
M = B[n//2]
res = 0
for b in B:
    res += abs(b-M)
print(res)

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

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

b = statistics.median(B)

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

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

b = []
i = 1
for a in A:
    b.append(a-i)
    i+=1

b.sort()

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

abs = lambda x : x if x > 0 else -x
sad = lambda x : abs(x - med)
print(sum(map(sad,b)))

Solution (Python):


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

    for i in range(0, N):
        A[i] = A[i] - (i+1)
    
    sorted_A = sorted(A)
    b = sorted_A[N//2]

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

    print(ans)

if __name__ == "__main__":
    solve()

Solution (Python):
N = int(input())
As = list(map(int, input().split()))
A = [As[i] - (i+1) for i in range(N)]
A.sort()
b1 = A[N//2]
b2 = A[N//2 -1]
ans1 = 0
ans2 = 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())
L = list(map(int,input().split()))
for i in range(N):
  L[i] = L[i]-i-1
L.sort()
S = 0
if len(L)%2 != 0:
  k = L[len(L)//2]
else:
  k = (L[len(L)//2-1]+L[len(L)//2])//2
for i in range(len(L)):
  S += abs(L[i]-k)
print(S)

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

Solution (Python):
N=int(input())
B=list(map(int,input().strip().split(" ")))
B=[B[i]-(i+1) for i in range(N)]
B=sorted(B)
want=B[N//2]
ans=0
for x in B:
    ans+=abs(x-want)
print(ans)

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]
li = []
ans = 0
for ind,i in enumerate(A):
    li+=[i-(ind+1)]
li.sort()
x = li[(len(li)-1)//2]
for i in li:
    ans+=abs(i-x)
print(ans)

Solution (Python):
import numpy as np
def f(n, b, c):
    return np.sum(np.abs(c-b))

def solve(n, a):
    c = np.asarray([(a[i]-i-1) for i in range(n)], dtype=int)
    b = np.median(c)
    return int(f(n, b, c))

assert solve(5, [2, 2, 3, 5, 5]) == 2
assert solve(9, [1, 2, 3, 4, 5, 6, 7, 8, 9]) == 0
assert solve(6, [6, 5, 4, 3, 2, 1]) == 18
assert solve(7, [1, 1, 1, 1, 2, 3, 4]) == 6
n = int(input())
a = list(map(int, input().split()))
print(solve(n, 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()
b=B[N//2]
ans=0
for i in B:
    ans+=abs(i-b)
print(ans)

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

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

Solution (Python):
from numpy import*;n,*a=map(int,open(0).read().split());x=sorted(array(a)-arange(1,n+1));print(sum(abs(x-x[n//2])))

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] if N % 2 else A[((N - 1) // 2 + N // 2) // 2]

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

print(sum)

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

Solution (Python):
import numpy as np
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(_) for _ in stdin.readline().rstrip().split()]
B = [A[i]-i-1 for i in range(0,N)]
median = np.median(B)
print(int(np.sum(np.abs(B-median))))

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]
for i in range(N):
    A[i] -= i+1
A.sort()
len_A = len(A)
Sum = 0
for i in range(len_A//2):
    Sum += A[len_A-1-i] - A[i]
print(Sum)

Solution (Python):
import statistics
import math

input()
num_list = [int(x) - i for (i,x) in enumerate(input().split(),1)]
med = statistics.median_low(num_list)
sad_list = [abs(x-med) for x in num_list]

print (sum(sad_list))

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

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

import numpy as np
b0 = np.median(b)
print(int(np.sum(np.abs(b - b0))))

Solution (Python):

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

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

bs = [As[N//2]]
if N % 2 == 0:
    bs.append(As[N//2-1])

total = 2*10**14
for b in bs:
    t = 0
    for A in As:
        t += abs(A - b)
    total = min(total, t)
print(total)

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

d_mid = d_[int(N/2)]
print(sum([abs(d_[i]-d_mid) for i in range(N)]))

Solution (Python):


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

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

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

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

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

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

A = sorted(A)

if N % 2 == 1:
    b = A[N//2]
    for i in A:
        ans += abs(i - b)
    print(ans)
else:
    ans = -sum(A[:N//2])+sum(A[N//2:])
    print(ans)

Solution (Python):
""" AtCoder """

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

b = A[N//2]

ans = 0

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

print(ans)

Solution (Python):
""" AtCoder """

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

b = A[N//2]
bb = A[N//2 + 1]

ans = 0
ansans = 0

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

print(min(ans, ansans))

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

ai = list(sorted([a - i - 1 for i, a in enumerate(alist)]))
if n % 2 == 1:
  b = ai[n // 2]
  print(sum(abs(_ai - b) for _ai in ai))
else:
  b = (ai[n // 2 - 1] + ai[n // 2])
  if b % 2 == 0:
    b //= 2
    print(sum(abs(_ai - b) for _ai in ai))
  else:
    b //= 2
    print(min(sum(abs(_ai - b - 1) for _ai in ai), sum(abs(_ai - b) for _ai in ai)))

Solution (Python):
import sys

N = int(input())
A = list(map(int, input().split()))
A = sorted([A[k]-(k+1) for k in range(N)])

if N == 1:
  print(0)
  sys.exit()

for k in range((N-2)//2 + 1, N-1):
  if A[k] < A[k+1]:
    b = k
    break
  if k == N-2:
    print(0)
    sys.exit()
print(sum([abs(A[k]-A[b]) for k in range(N)]))

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007


def A():
    return


def B():
    return


def C():
    n = II()
    A = LI()
    for i in range(n):
        A[i] = A[i] - i - 1
    import statistics
    a = round(statistics.median(A))
    ans = 0
    for i in range(n):
        ans += abs(A[i] - a)
    print(ans)

def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == '__main__':
    C()

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

Solution (Python):
import math
def p(d): print(d)
def i(): return input()

def LI():  
    
    return int(input())
def LIS():  
    
    return [int(x) for x in input().split()]
def MLIS(n):  
    
    return [[int(x) for x in input().split()] for y in range(n)]
def LC():  
    
    return input()
def LCS(): 
    
    return [x for x in input().split()]
def MLCS(n): 
    
    return [[x for x in input().split()] for y in range(n)]

def alp2int(alphabet):
    
    return ord(alphabet) - ord('a')
def int2alp(num):
    
    return chr(num + ord('a'))
def cnt2dic(lst, dic={}):
    
    for x in lst:
        key = str(x)
        if key in dic:
            dic[key] += 1
        else:
            dic[key] = 1
    return dic
def dic2lst(dic, key=lambda x:x[1]):
    
    return sorted(list(dic.items()), key=key);

def unqlst(lst):
    return list(set(lst))

def A():
    a = LC()
    if a[0] == a[2]:
        print('Yes')
    else:
        print('No')

def B():
    a, b, c, d = LIS()
    s = max(a, c)
    e = min(b, d)
    if s < e:
        p(e-s)
    else:
        p(0)

def C():
    N = LI()
    reds = sorted(MLIS(N), key=lambda x:x[0])
    blues = sorted(MLIS(N), key=lambda x:x[0])

    blueF = [False for x in range(N)]

    count = 0

    for i in range(N):
        for j in range(N):
            if blueF[j] == False and reds[i] < blues[j]:
                blueF[j] = True
                count += 1
                break
    print(count)

def D():
    pass

def E():
    s = LC()
    k = LI()
    words = []
    for b in range(len(s)):
        for e in range(1, 6):
            if s[b:b+e] != '':
                words.append(s[b:b+e])
    words = sorted(unqlst(words))
    print(words[k-1])
def F():
    pass

def G():
    n = LI()
    A = LIS()
    B = [A[i] - (i+1) for i in range(n)]
    B = sorted(B)

    b = B[n//2]

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

def H():
    pass

G()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


def A():
    return


def B():
    return


def C():
    n = I()
    a = LI()
    for i in range(n):
        a[i] -= i+1
    a.sort()
    b = sum(a)//n
    ans = 0
    for i in range(n):
        ans += abs(a[i]-b)
    ans2 = 0
    b += 1
    for i in range(n):
        ans2 += abs(a[i]-b)
    ans3 = 0
    b = a[n//2]
    for i in range(n):
        ans3 += abs(a[i]-b)
    print(min(ans,ans2,ans3))


def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    C()

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

Solution (Python):
n=int(input());a=sorted(int(x)-i for i,x in enumerate(input().split()));print(sum(abs(i-a[n//2])for i 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 len(A)%2==1:
    num = A[len(A)//2]
else:
    num = (A[len(A)//2] + A[len(A)//2-1]) // 2
for i in range(n):
    A[i]-=num
for i in range(n):
    A[i]=abs(A[i])

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

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

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

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

m.sort()
index = n//2

b = m[index]

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

print(ans)

Solution (Python):
import statistics

n = int(input())
A = list(map(int, input().split()))
B = [A[i-1]-i for i in range(1,n+1)]
b = statistics.median(B)

print(int(sum([abs(B[i]-b) for i in range(n)])))

Solution (Python):
import statistics

n = input()
l = list(map(int, input().split()))
x = []
for i in range(len(l)):
  x.append(l[i] - i)
    
b = 0
if (len(x) % 2 == 1):
  b = statistics.median(x)
else:
  b = statistics.median_low(x)

sad = 0
for i in x:
  sad += abs(i - b)

print(sad)

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

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

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

if N==0:
    print(1)
elif N%2==1:
    ANS=0
    for j in range(N):
        ANS+=abs(B[j]-B[N//2])
    print(ANS)
else:
    S=0
    for j in range(N):
        S+=abs(B[j]-B[N//2-1])
    L=0
    for k in range(N):
        L+=abs(B[j]-B[N//2])
    print(min(S,L))

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

A2 = sorted([A[i]-i-1 for i in range(len(A))])
median = A2[len(A)//2]

ans = 0
for i in range(len(A)):
    ans += abs(A2[i]-median)
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()

b1 = A[N//2-1]
b2 = A[N//2]

ans1 = 0
ans2 = 0

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

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

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

Solution (Python):
def inpli(): return [int(v)-i-1 for i,v in enumerate(input().split())]
N = int(input())
A = sorted(inpli())
a = A[N//2]
ans = 0
for i in A:
    ans += abs(a-i)
print(ans)