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-----
5
2 2 3 5 5

-----Sample Output-----
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.

Source: atcoder | Difficulty: MEDIUM_HARD


Solutions:
import sys
import os
from copy import copy
import operator
import time
import datetime
import math
from math import floor, ceil, sqrt, log
import statistics
from statistics import mean, median
from decimal import Decimal as D
from fractions import Fraction as F
import functools
import random
from random import randint, shuffle
import bisect
import string
from collections import deque
import collections
import itertools
import heapq
sys.setrecursionlimit(4100000)
product = functools.partial(functools.reduce, operator.mul)
INF = float('inf')

class UnionFind:

	def __init__(self, n, m):
		self.parents = [[-1, {m[i]: 1}] for i in range(n)]
		self.n = n

	def __getitem__(self, item):
		if type(item) == tuple:
			if len(item) == 1:
				return self.size(item[0])
			else:
				self.union(item[0], item[1])
		elif type(item) == slice:
			return self.same(item.start, item.stop)
		else:
			return self.find(item)

	def __len__(self):
		return self.group_count()

	def __pos__(self):
		return self.max_size()

	def __neg__(self):
		return self.min_size()

	def __invert__(self):
		return self.roots()

	def union(self, x, y):
		(x, y) = (self.find(x), self.find(y))
		if x != y:
			if self.parents[x][0] > self.parents[y][0]:
				(x, y) = (y, x)
			self.parents[x][0] += self.parents[y][0]
			for (k, v) in list(self.parents[y][1].items()):
				self.parents[x][1].setdefault(k, 0)
				self.parents[x][1][k] += v
			self.parents[y] = x

	def find(self, x):
		if type(self.parents[x]) == list:
			return x
		self.parents[x] = self.find(self.parents[x])
		return self.parents[x]

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return list([x for x in self.parents if x < 0])

	def group_count(self):
		return len(self.roots())

	def max_size(self):
		return -min(self.parents)

	def min_size(self):
		return -max(self.roots())

	def append(self, n):
		self.parents += [-1] * n

class Imos:

	def __init__(self, n):
		self.val = [0] * n

	def add(self, x, y, n=None):
		if n is None:
			n = 1
		self.val[x] += n
		if len(self.val) > y + 1:
			self.val[y + 1] -= n

	def imos(self):
		for i in range(1, len(self.val)):
			self.val[i] += self.val[i - 1]

	def max(self):
		return max(self.val)

	def min(self):
		return min(self.val)

class CS:

	def __init__(self, grid):
		self.cs = grid
		for i0 in range(len(grid)):
			for i1 in range(len(grid[0])):
				if i0 == 0:
					if i1 == 0:
						continue
					self.cs[i0][i1] += self.cs[i0][i1 - 1]
				elif i1 == 0:
					self.cs[i0][i1] += self.cs[i0 - 1][i1]
				else:
					self.cs[i0][i1] += self.cs[i0 - 1][i1] + self.cs[i0][i1 - 1] - self.cs[i0 - 1][i1 - 1]

	def sum(self, start_0, start_1, end_0, end_1):
		if start_0 == 0:
			if start_1 == 0:
				return self.cs[end_0][end_1]
			return self.cs[end_0][end_1] - self.cs[end_0][start_1 - 1]
		if start_1 == 0:
			return self.cs[end_0][end_1] - self.cs[start_0 - 1][end_1]
		start_0 -= 1
		start_1 -= 1
		return self.cs[end_0][end_1] - self.cs[start_0][end_1] - self.cs[end_0][start_1] + self.cs[start_0][start_1]

def mod(n):
	return n % (10 ** 9 + 7)

def sinput():
	return sys.stdin.readline()[:-1]

def input():
	inputs = list(map(int, sys.stdin.readline().split()))
	if len(inputs) == 1:
		return inputs[0]
	return inputs

def listban(l):
	return list(map(list, set(map(tuple, l))))

def div(n):
	(lower_divisors, upper_divisors) = ([], [])
	i = 1
	while i * i <= n:
		if n % i == 0:
			lower_divisors.append(i)
			if i != n // i:
				upper_divisors.append(n // i)
		i += 1
	return lower_divisors + upper_divisors[::-1]

def prime(n):
	a = []
	while n % 2 == 0:
		a.append(2)
		n //= 2
	f = 3
	while f * f <= n:
		if n % f == 0:
			a.append(f)
			n //= f
		else:
			f += 2
	if n != 1:
		a.append(n)
	return a

def div_counter(l, n):
	return prime(l).count(n)

def lcm(x, y):
	return x * y // math.gcd(x, y)

def C(n, r):
	if n < r:
		return 0
	return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def P(n, r):
	if n < r:
		return 0
	return math.factorial(n) // math.factorial(n - r)

def H(n, r):
	return C(n + r - 1, r)

def cos(x, y, a):
	return (x ** 2 + y ** 2 - 2 * x * y * math.cos(math.radians(a))) ** 0.5

def DFS(g, s, pos=None):
	if pos is None:
		pos = set()
	pos.add(s)
	for i in g[s]:
		if not i in pos:
			DFS(g, i, pos)
	return pos

def DFS_one(g, s, pos=None):
	if pos is None:
		pos = set()
	pos = copy(pos)
	pos.add(s)
	b = copy(pos)
	m = copy(pos)
	for i in g[s]:
		if not i in pos:
			b = DFS(g, i, pos)
			if len(m) < len(b):
				m = b
	return m

def BFS(g, q, pos=None):
	if pos is None:
		pos = set()
	if type(q) == deque:
		pos.add(q)
		q = deque([q])
	pos.add(q[-1])
	for i in g[q.pop()]:
		if not i in pos:
			q.append(i)
	while q != deque():
		(pos, q) = BFS(g, q, pos)
	return (pos, q)

def SSP(a, li=None):
	if li is None:
		li = []
	if len(a) == 1:
		return [a[0]]
	return list(set(li + SSP(a[1:], li) + list([x + a[0] for x in SSP(a[1:], li)]) + [a[0]]))

def dijkstra(g, s):
	n = len(g)
	dist = [10 ** 100] * n
	hq = [(0, s)]
	dist[s] = 0
	seen = [False] * n
	while hq:
		v = heapq.heappop(hq)[1]
		seen[v] = True
		for (to, cost) in g[v]:
			if seen[to] == False and dist[v] + cost < dist[to]:
				dist[to] = dist[v] + cost
				heapq.heappush(hq, (dist[to], to))
	return dist

def LIS(b):
	l = [b[0]]
	for i in b:
		if i > l[-1]:
			l += [i]
		else:
			l[bisect.bisect_left(l, i)] = i
	return len(l)

def yn(b):
	if b:
		print('Yes')
	else:
		print('No')

def op(s):
	print(s)
	return
n = input()
a = input()
if n == 1:
	a = [a]
for i in range(n):
	a[i] = a[i] - i - 1
hei = round(median(a))
ans = 0
for i in a:
	ans += abs(hei - i)
print(ans)


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

def snk(b):
	res = 0
	for i in range(N):
		res += abs(A[i] - b)
	return res
if N == 1:
	print(snk(A[N // 2]))
	return
print(min(snk(A[N // 2]), snk(A[N // 2 + 1])))


from sys import stdin, setrecursionlimit
import bisect, collections, copy, heapq, itertools, math, string
setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 1000000007

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

def main():
	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 x in a:
		ans += abs(x - b)
	print(ans)
	return

def __starting_point():
	main()
__starting_point()


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


import numpy as np
N = int(input())
A = list(map(int, input().split()))
B = np.sort(np.array([x - (i + 1) for (i, x) in enumerate(A)]))
if N % 2 == 1:
	b = np.median(B)
	ans = int(abs(B - b).sum())
else:
	b1 = B[N // 2 - 1]
	b2 = B[N // 2]
	ans = int(min(abs(B - b1).sum(), abs(B - b2).sum()))
print(ans)


import sys
import math
import itertools
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
input = sys.stdin.readline

def RD():
	return input().rstrip()

def F():
	return float(input().rstrip())

def I():
	return int(input().rstrip())

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

def MF():
	return map(float, input().split())

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

def TI():
	return tuple(map(int, input().split()))

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

def Init(H, W, num):
	return [[num for i in range(W)] for j in range(H)]

def main():
	N = I()
	A = LI()
	neg = []
	pos = []
	for i in range(N):
		num = A[i] - i - 1
		if num >= 0:
			pos.append(num)
		else:
			neg.append(-num)
	pos.sort()
	neg.sort()
	pos_l = len(pos)
	neg_l = len(neg)
	pos2 = [0] + deepcopy(pos)
	neg2 = [0] + deepcopy(neg)
	for i in range(1, pos_l + 1):
		pos2[i] += pos2[i - 1]
	for i in range(1, neg_l + 1):
		neg2[i] += neg2[i - 1]
	ans = float('inf')
	for i in range(pos_l):
		num = pos[i]
		res = i * num - pos2[i]
		res += pos2[pos_l] - pos2[i + 1] - num * (pos_l - 1 - i)
		res += neg2[neg_l] + num * neg_l
		ans = min(res, ans)
	for i in range(neg_l):
		num = neg[i]
		res = i * num - neg2[i]
		res += neg2[neg_l] - neg2[i + 1] - num * (neg_l - 1 - i)
		res += pos2[pos_l] + num * pos_l
		ans = min(res, ans)
	print(ans)

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline
import math

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

def find_minimum(N, A, l, r):
	m = (r + 2 * l) // 3
	q = (2 * r + l) // 3
	lf = sum([abs(A[i] - l) for i in range(N)])
	rf = sum([abs(A[i] - r) for i in range(N)])
	mf = sum([abs(A[i] - m) for i in range(N)])
	qf = sum([abs(A[i] - q) for i in range(N)])
	while r - l >= 3:
		m = (r + 2 * l) // 3
		q = (2 * r + l) // 3
		lf = sum([abs(A[i] - l) for i in range(N)])
		mf = sum([abs(A[i] - m) for i in range(N)])
		qf = sum([abs(A[i] - q) for i in range(N)])
		rf = sum([abs(A[i] - r) for i in range(N)])
		if mf >= qf:
			l = m
		else:
			r = q
	return min(lf, mf, qf, rf)

def solve(N, A, EPS=0.001):
	D = [A[i] - i - 1 for i in range(N)]
	return find_minimum(N, D, l=-10 ** 10, r=10 ** 10)

def __starting_point():
	inputs = read()
	outputs = solve(*inputs)
	if outputs is not None:
		print('%s' % str(outputs))
__starting_point()


import statistics
import math
N = int(input())
A_list = list(map(int, input().split()))
A_list_min = 10 ** 9 + 1
A_list_sum = 0
for i in range(N):
	A_list[i] = A_list[i] - (i + 1)
A_medi = int(statistics.median(A_list))
ans = 0
for i in range(N):
	ans += abs(A_list[i] - A_medi)
print(ans)


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


N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)
B = [A[i] - i for i in range(N + 1)]
B.pop(0)
B = sorted(B)
if N % 2 == 1:
	b = B[N // 2]
	cnt = 0
	for i in range(N):
		cnt += abs(B[i] - b)
else:
	b1 = B[N // 2 - 1]
	cnt1 = 0
	for i in range(N):
		cnt1 += abs(B[i] - b1)
	b2 = B[N // 2]
	cnt2 = 0
	for i in range(N):
		cnt2 += abs(B[i] - b2)
	cnt = min(cnt1, cnt2)
print(cnt)


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


def snk(b, A):
	res = 0
	for i in range(N):
		res += abs(A[i] - (b + i + 1))
	return res
N = int(input())
A = [int(i) for i in input().split()]
l = 1 - N
r = 10 ** 9 + N
while r - l > 2:
	ls = snk(l, A)
	rs = snk(r - 1, A)
	m = (l + r) // 2
	ms = snk(m, A)
	mp1s = snk(m + 1, A)
	mm1s = snk(m - 1, A)
	if mp1s <= ms <= mm1s:
		l = m
	elif mp1s >= ms >= mm1s:
		r = m + 1
	elif mp1s >= ms and ms <= mm1s:
		break
print(ms)


import bisect
import heapq
import itertools
import sys
import math
import random
from collections import Counter, deque, defaultdict
from functools import reduce
from operator import xor
from typing import List
mod = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 9)

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

def main():
	N = int(input())
	A = lmi()
	A_dash = [a - (i + 1) for (i, a) in enumerate(A)]
	A_dash.sort()
	b = A_dash[N // 2]
	ans = sum((abs(a - b) for (i, a) in enumerate(A_dash)))
	if N // 2 + 1 < len(A_dash):
		b = A_dash[N // 2 + 1]
		ans = min(ans, sum((abs(a - b) for (i, a) in enumerate(A_dash))))
	print(ans)

def __starting_point():
	main()
__starting_point()


import numpy as np
N = int(input())
A = list(map(int, input().split()))
a = np.array(A)
b = a - np.arange(1, N + 1)
c = np.median(b)
d = abs(b - c).sum()
print(int(d))


n = int(input())
A = list(map(int, input().split()))
(B, total) = ([], 0)
for i in range(n):
	B.append(A[i] - i)
B.sort()
if len(B) % 2 == 0:
	b = (B[n // 2 - 1] + B[n // 2]) // 2
else:
	b = B[n // 2]
for i in range(n):
	total += abs(B[i] - b)
print(total)


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


N = int(input())
A = list(map(int, input().split()))
median = sorted((a - i for (i, a) in enumerate(A)))[N // 2]
print(sum((abs(a - (median + i)) for (i, a) in enumerate(A))))


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


n = int(input())
al = list(map(int, input().split()))
bl = list((i + 1 for i in range(n)))
cl = []
for (a, b) in zip(al, bl):
	cl.append(a - b)
cl.sort()
x = cl[n // 2]
ans = 0
for (a, b) in zip(al, bl):
	ans += abs(a - b - x)
print(ans)


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


N = int(input())
vA = list(map(int, input().split()))
vAm = sorted([vA[i] - i - 1 for i in range(N)])
b = vAm[N // 2]
vans = [abs(Am - b) for Am in vAm]
print(sum(vans))


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
for i in range(N):
	A[i] -= i + 1
A.sort()
ans = float('inf')
cand = [A[N // 2]]
if N > 1:
	cand.append(A[N // 2 + 1])
for i in cand:
	tmp = 0
	for a in A:
		tmp += abs(a - i)
	ans = min(ans, tmp)
print(ans)


import sys
from statistics import median
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
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)]
	M = int(median(A))
	res = 0
	for a in A:
		res += abs(a - M)
	print(res)

def __starting_point():
	resolve()
__starting_point()


import sys
sys.setrecursionlimit(10 ** 9)

def int1(x):
	return int(x) - 1

def II():
	return int(input())

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

def MI1():
	return list(map(int1, input().split()))

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

def LI1():
	return list(map(int1, input().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def MS():
	return input().split()

def LS():
	return list(input())

def LLS(rows_number):
	return [LS() for _ in range(rows_number)]

def printlist(lst, k=' '):
	print(k.join(list(map(str, lst))))
INF = float('inf')
from math import ceil, floor, log2
import numpy as np

def solve():
	N = II()
	A = LI()
	for i in range(N):
		A[i] = A[i] - (i + 1)
	med = int(np.median(A))
	ans = 0
	for a in A:
		ans += abs(a - med)
	print(ans)

def __starting_point():
	solve()
__starting_point()


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

def __starting_point():
	main()
__starting_point()


import math
import numpy as np
import sys
input = sys.stdin.readline
mod = 1000000007

def main():
	n = int(input())
	A = list(map(int, input().split()))
	for i in range(n):
		A[i] -= i + 1
	b = int(np.median(A))
	for i in range(n):
		A[i] = abs(A[i] - b)
	print(int(np.sum(A)))
main()


import sys
N = int(input())
A = list(map(int, sys.stdin.readline().rsplit()))
for i in range(N):
	A[i] = A[i] - (i + 1)
A.sort()
b = A[(N - int(N % 2 == 0)) // 2]
res = 0
for a in A:
	res += abs(a - b)
print(res)


(N, *A) = list(map(int, open(0).read().split()))
if N == 1:
	print(0)
else:
	cs = [a - i for (i, a) in enumerate(A)]
	cs.sort()
	n = len(cs)
	half = n // 2
	d1 = -cs[half]
	d2 = -cs[half + 1]
	sad1 = sum([abs(c + d1) for c in cs])
	sad2 = sum([abs(c + d2) for c in cs])
	print(min(sad1, sad2))


n = int(input())
a = list(map(int, input().split()))
a2 = [ai - i for (i, ai) in enumerate(a, 1)]
a2.sort()
cumsum = [0] * n
cumsum[0] = a2[0]
for i in range(n - 1):
	cumsum[i + 1] = cumsum[i] + a2[i + 1]
ans = 10 ** 20
for i in range(n):
	low = cumsum[i]
	high = cumsum[-1] - cumsum[i]
	ai = a2[i]
	ans = min(ans, ai * (i + 1) - low + (high - ai * (n - 1 - i)))
print(ans)


import statistics
from functools import reduce
n = int(input())
A = list(map(int, input().split()))
for i in range(n):
	A[i] -= i + 1
m = int(statistics.median(A))
ans1 = 0
ans2 = 0
for i in range(n):
	ans1 += abs(m - A[i])
	ans2 += abs(m + 1 - A[i])
print(min(ans1, ans2))


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


import sys, math
from itertools import combinations as c, permutations as perm, product as p
from collections import deque
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def si():
	return input()

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

def fi():
	return float(input())

def lstr():
	return input().split()

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

def lintdec():
	return list(map(lambda x: int(x) - 1, input().split()))

def lnstr(n):
	return [input() for _ in range(n)]

def lnint(n):
	return [int(input()) for _ in range(n)]

def lint_list(n):
	return [lint() for _ in range(n)]
N = ii()
A = lint()
B = [A[i] - i - 1 for i in range(N)]
B.sort()
if N % 2 == 1:
	m = B[N // 2]
	print(sum((abs(b - m) for b in B)))
else:
	m = (B[N // 2] + B[N // 2 - 1]) / 2
	print(int(sum((abs(b - m) for b in B))))


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


import statistics

def main():
	n = int(input())
	a = [int(x) for x in input().split()]
	c = [a[i] - i - 1 for i in range(n)]
	b = int(statistics.median(c))
	ans = 0
	for i in range(n):
		ans += abs(a[i] - (b + i + 1))
	print(ans)

def __starting_point():
	main()
__starting_point()


import numpy as np
N = input().split()
N = int(N[0])
A = np.array(list(map(int, input().split())))
s = 0
I = np.array([i + 1 for i in range(N)])
Aminusi = np.array(A - I)
mmid = np.median(Aminusi)
sad = 0
for l in Aminusi:
	sad += abs(l - mmid)
print(int(sad))


n = int(input().strip())
input_line = list(map(int, input().strip().split(' ')))
for idx in range(n):
	input_line[idx] = input_line[idx] - (idx + 1)
input_line.sort()
min_num = input_line[0]
num_sum = 0
for idx in range(n):
	num_sum = num_sum + abs(input_line[idx] - min_num)
res = num_sum
for idx in range(1, n):
	point_dist = input_line[idx] - input_line[idx - 1]
	this_dist = num_sum + idx * point_dist - (n - idx) * point_dist
	num_sum = this_dist
	res = min(res, this_dist)
print(res)


from statistics import median
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
	a[i] -= i + 1
a.sort()
m = int(median(a))
print(sum((abs(a[i] - m) for i in range(n))))


n = int(input())
a = [ai - i for (ai, i) in zip(map(int, input().split()), [j for j in range(1, n + 1)])]
a.sort()
if n % 2:
	b = a[n // 2]
	print(sum([abs(ai - b) for ai in a]))
else:
	(b1, b2) = (a[n // 2 - 1], a[n // 2])
	print(min(sum([abs(ai - b1) for ai in a]), sum([abs(ai - b2) for ai in a])))


N = int(input())
A = list(map(int, input().split()))
import numpy as np
A_np = np.array(A)
data = np.array(list(range(1, N + 1)))
A_i = sorted(A_np - data)
if N % 2 == 0:
	x = A_i[int(N / 2) - 1]
	y = A_i[int(N / 2)]
	A_x = A_i - x
	A_p_x = A_x[A_x >= 0]
	A_m_x = A_x[A_x < 0]
	A_y = A_i - y
	A_p_y = A_y[A_y >= 0]
	A_m_y = A_y[A_y < 0]
	ans = min(sum(A_p_x) - sum(A_m_x), sum(A_p_y) - sum(A_m_y))
	print(ans)
else:
	x = A_i[int((N - 1) / 2)]
	A_x = A_i - x
	A_p = A_x[A_x >= 0]
	A_m = A_x[A_x < 0]
	ans = sum(A_p) - sum(A_m)
	print(ans)


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


n = int(input())
a = list(map(int, input().split()))
b = []
for (i, aa) in enumerate(a):
	b.append(aa - (i + 1))
b.sort()
(s1, s2) = (0, 0)
(m1, m2) = (0, 0)
if n % 2 == 0:
	m1 = b[n // 2]
	m2 = b[n // 2 + 1]
	for bb in b:
		s1 += abs(bb - m1)
		s2 += abs(bb - m2)
	print(min(s1, s2))
else:
	m1 = b[n // 2]
	for bb in b:
		s1 += abs(bb - m1)
	print(s1)


def main():
	n = int(input())
	a = list(map(int, input().split()))
	l = -1 * max(a) - 2 * 10 ** 5
	r = max(a) + 2 * 10 ** 5

	def f(k):
		ans = 0
		for i in range(n):
			ans += abs(a[i] - 1 - i - k)
		return ans
	while l + 1 < r:
		if f(l) < f(r):
			r = (l + r) // 2
		else:
			l = (l + r) // 2
	print(min(f(l), f(r)))

def __starting_point():
	main()
__starting_point()


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


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

def __starting_point():
	resolve()
__starting_point()


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


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


import statistics
N = int(input())
A = list(map(int, input().split()))
As = []
for i in range(N):
	As.append(A[i] - (i + 1))
mid = int(statistics.median(As))
result = 0
for i in range(N):
	result += abs(A[i] - (mid + i + 1))
print(result)


import sys
input = sys.stdin.readline
import math

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

def solve(N, A, EPS=0.001):
	D = [A[i] - i - 1 for i in range(N)]
	D.sort()
	if N == 1:
		median = sum([abs(d - D[0]) for d in D])
		return median
	median_left = sum([abs(d - D[N // 2]) for d in D])
	median_right = sum([abs(d - D[N // 2 + 1]) for d in D])
	return min(median_left, median_right)

def __starting_point():
	inputs = read()
	outputs = solve(*inputs)
	if outputs is not None:
		print('%s' % str(outputs))
__starting_point()


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

def snk(b):
	return sum([abs(A[i] - (b + i + 1)) for i in range(N)])
l = 1 - N
r = 10 ** 9 + N
ans = 10 ** 18
while l + 2 < r:
	l1 = (l * 2 + r) // 3
	r1 = (l + r * 2) // 3
	(ls, rs) = [snk(i) for i in [l1, r1]]
	if ls > rs:
		l = l1
	else:
		r = r1
ans = 10 ** 18
for i in range(l, r + 1):
	ans = min(ans, snk(i))
print(ans)


n = int(input())
a = list(map(int, input().split()))
arr = []
for i in range(n):
	arr.append(a[i] - (i + 1))
sorted_arr = sorted(arr)
if n % 2 == 1:
	val = sorted_arr[n // 2]
	for i in range(n):
		arr[i] = arr[i] - val
	print(sum([abs(i) for i in arr]))
else:
	arr1 = []
	arr2 = []
	val1 = sorted_arr[n // 2]
	val2 = sorted_arr[n // 2 - 1]
	for i in range(n):
		arr1.append(arr[i] - val1)
		arr2.append(arr[i] - val2)
	print(min(sum([abs(i) for i in arr1]), sum([abs(i) for i in arr2])))


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


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


import numpy as np
n = int(input())
a = list(map(int, input().split()))
a_ = [abs(a[i]) - (i + 1) for i in range(n)]
med = int(np.median(a_))

def fun(a, b):
	ans = 0
	for i in range(1, len(a) + 1):
		ans += abs(a[i - 1] - (b + i))
	return ans
print(fun(a, med))


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


def resolve():
	inf = 10 ** 10 + 1
	N = int(input())
	A = [int(x) for x in input().split(' ')]
	for i in range(N):
		A[i] -= i + 1
	A.sort()
	if len(A) % 2:
		b = A[len(A) // 2]
	else:
		center = len(A) // 2
		b = round((A[center] + A[center - 1]) // 2)
	ans = 0
	for i in range(N):
		ans += abs(A[i] - b)
	print(ans)
resolve()


import sys
readline = sys.stdin.readline
read = sys.stdin.read
n = int(readline())
(*a,) = map(int, readline().split())
for i in range(n):
	a[i] -= i + 1
a.sort()
b = a[n // 2]
ans = sum((abs(ai - b) for ai in a))
print(ans)


import sys

def IN_I():
	return int(sys.stdin.readline().rstrip())

def IN_LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

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

def IN_LS():
	return list(sys.stdin.readline().rstrip().split())
INF = float('inf')
MOD = 10 ** 9 + 7
N = IN_I()
A = IN_LI()
for i in range(N):
	A[i] -= i + 1
A.sort()
if N % 2 == 1:
	b = A[N // 2]
else:
	b = (A[N // 2 - 1] + A[N // 2]) // 2
ans = 0
for a in A:
	ans += abs(a - b)
print(ans)


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


n = int(input())
a = list(map(int, input().split()))
stairs = [1] * n
(l, r) = (10 ** 9, -2 ** 5)
for i in range(n):
	stairs[i] += i
	r = max(r, a[i] - stairs[i])
	l = min(l, a[i] - stairs[i])

def pos(b):
	return sum((abs(i - b - j) for (i, j) in zip(a, stairs)))
while l + 2 < r:
	c1 = l + (r - l) // 3
	c2 = r - (r - l) // 3
	if pos(c1) < pos(c2):
		r = c2
	else:
		l = c1
ans = min(min(pos(l), pos(r)), pos(l + 1))
print(ans)


n = int(input())
a = list([int(x[1]) - x[0] - 1 for x in enumerate(input().split())])
nh = (n + 1) // 2
a.sort()
b = a[nh - 1]
s = 0
for ai in a:
	s += abs(ai - b)
print(s)


import sys
from functools import reduce
zz = 1
sys.setrecursionlimit(10 ** 5)
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def ii():
	return input().rstrip()

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def comp(a, b):
	if a > b:
		return 2
	return 2 if a == b else 0

def gi():
	return [xx for xx in input().split()]

def gtc(tc, ans):
	print(('Case #' + str(tc) + ':', ans))

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def si():
	return list(input().rstrip())

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

def gh():
	sys.stdout.flush()

def isvalid(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = 1
uu = t

def can(val):
	p = val
	c = 0
	for i in range(n):
		c += abs(a[i] - p)
		p += 1
	return c
while t > 0:
	t -= 1
	n = fi()
	a = li()
	l = -2 * max(a)
	r = 2 * max(a)
	mini = 10 ** 18
	while l <= r:
		lmid = l + (r - l) // 3
		rmid = r - (r - l) // 3
		p1 = can(lmid)
		p2 = can(rmid)
		mini = min([mini, p1, p2])
		if p1 >= p2:
			l = lmid + 1
		else:
			r = rmid - 1
	print(mini)


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


N = int(input())
A = sorted([int(x) - i for (i, x) in enumerate(input().split(), 1)])
mid = N // 2
ans = sum(list([abs(x - A[mid]) for x in A]))
if N % 2 == 0:
	_mid = N // 2 + 1
	_ans = sum(list([abs(x - A[_mid]) for x in A]))
	ans = min(ans, _ans)
print(ans)


n = int(input())
aa = list(map(int, input().split()))
am = [aa[i] - (i + 1) for i in range(n)]
am = sorted(am)
b1 = am[n // 2 - 1]
b2 = am[n // 2]
sum1 = 0
sum2 = 0
for i in range(n):
	sum1 += abs(am[i] - b1)
	sum2 += abs(am[i] - b2)
ans = min(sum1, sum2)
print(ans)


import sys
MOD = 10 ** 9 + 7
INF = float('inf')
N = int(input())
A = list(map(int, input().split()))
Aafter = [A[i] - (i + 1) for i in range(N)]
minus = []
zero_count = 0
plus = []
for i in range(N):
	if Aafter[i] < 0:
		minus.append(-Aafter[i])
	elif Aafter[i] == 0:
		zero_count += 1
	else:
		plus.append(Aafter[i])
minus.sort()
plus.sort()
minus_count = len(minus)
plus_count = len(plus)
bias = 0
if minus_count + zero_count < plus_count:
	dif = (plus_count - (minus_count + zero_count)) // 2
	bias = plus[dif]
elif plus_count + zero_count < minus_count:
	dif = (minus_count - (plus_count + zero_count)) // 2
	bias = -minus[dif]
res = 0
for i in range(N):
	res += abs(Aafter[i] - bias)
print('{}'.format(res))


from math import gcd
from itertools import combinations, permutations, accumulate, product, combinations_with_replacement
from collections import deque, defaultdict, Counter
import decimal
import re
import math
import bisect
import heapq
import sys
sys.setrecursionlimit(10000000)
mod = 10 ** 9 + 7
INF = float('inf')
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
from sys import stdin
readline = stdin.readline

def readInts():
	return list(map(int, readline().split()))

def readTuples():
	return tuple(map(int, readline().split()))

def I():
	return int(readline())

def f(n):
	return int(math.ceil(n - 0.5))
from math import gcd
from itertools import combinations, permutations, accumulate, product, combinations_with_replacement
from collections import deque, defaultdict, Counter
import decimal
import re
import math
import bisect
import heapq
import sys
sys.setrecursionlimit(10000000)
mod = 10 ** 9 + 7
INF = float('inf')
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
from sys import stdin
readline = stdin.readline

def readInts():
	return list(map(int, readline().split()))

def readTuples():
	return tuple(map(int, readline().split()))

def I():
	return int(readline())

def f(n):
	return int(math.ceil(n - 0.5))
N = I()
A = readInts()
S = []
for i in range(N):
	S.append(A[i] - (i + 1))
S = sorted(S)
nya = []
nya.append(S[min(N // 2 + 1, N - 1)])
nya.append(S[N // 2])
nya.append(S[N // 2 - 1])
ans = INF
for n in nya:
	wa = 0
	for i in range(N):
		wa += abs(A[i] - (n + (i + 1)))
	ans = min(ans, wa)
print(ans)


def main():
	N = int(input())
	a_list = list(map(int, input().split()))
	s_list = [n - i for (i, n) in enumerate(a_list)]
	s_list.sort()
	b = s_list[N // 2]
	result = sum((abs(n - b) for n in s_list))
	print(result)
main()


import sys

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

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

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

def main():
	n = input_int()
	A = input_int_list()
	for i in range(n):
		A[i] = A[i] - (i + 1)
	A.sort()
	if n % 2 == 0:
		mid = (A[(n - 1) // 2] + A[(n - 1) // 2 + 1]) // 2
	else:
		mid = A[(n - 1) // 2]
	tmp0 = 0
	tmp1 = 0
	for a in A:
		tmp0 += abs(a - mid)
		tmp1 += abs(a - mid - 1)
	print(min(tmp0, tmp1))
	return

def __starting_point():
	main()
__starting_point()


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


from statistics import mean, median, variance, stdev
n = int(input())
A = list(map(int, input().split()))
A_b = A.copy()
for i in range(n):
	tmp = A[i] - i - 1
	A_b[i] = tmp
b = int(median(A_b))
ans = 0
for i in range(n):
	ans += abs(A[i] - b - i - 1)
print(ans)


n = int(input())
a = list(map(int, input().split()))
b = a
for bb in range(n):
	b[bb] -= bb + 1
b.sort()
if n % 2 == 1:
	c = b[n // 2]
	d = c
else:
	c1 = b[n // 2 - 1]
	c2 = b[n // 2]
	c = c1 + c2
	if c % 2 == 1:
		c = c // 2
		d = c + 1
	else:
		c = c // 2
		d = c
res1 = 0
res2 = 0
for i in range(n):
	res1 += abs(b[i] - c)
for j in range(n):
	res2 += abs(b[j] - d)
print(min(res1, res2))


n = int(input())
arr = list(map(int, input().split()))
al = list((ai - (i + 1) for (i, ai) in enumerate(arr)))
al_s = sorted(al)

def func(ARR, x):
	tmp = 0
	for ai in ARR:
		tmp += abs(ai - x)
	return tmp
if n % 2 != 0:
	b = al_s[n // 2]
	ans = func(al, b)
else:
	b1 = al_s[n // 2]
	b2 = al_s[n // 2 - 1]
	ans = min(func(al, b1), func(al, b2))
print(ans)


n = int(input())
A = list(map(int, input().split()))
B = []
for i in range(n):
	B.append(A[i] - (i + 1))
B.sort()
if len(B) % 2:
	ans = 0
	for i in range(n):
		ans += abs(B[i] - B[len(B) // 2])
else:
	ans = float('inf')
	tmp = 0
	for i in range(n):
		tmp += abs(B[i] - B[len(B) // 2 - 1])
	ans = min(ans, tmp)
	tmp = 0
	for i in range(n):
		tmp += abs(B[i] - B[len(B) // 2])
	ans = min(ans, tmp)
print(ans)


import sys
input = sys.stdin.readline
N = int(input())
A = [0] + list(map(int, input().split()))
lst = []
for n in range(1, N + 1):
	lst.append(A[n] - n)
lst.sort()
median = lst[N // 2]
ans = sum([abs(x - median) for x in lst])
print(ans)


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


n = int(input())
A = list(map(int, input().split()))
L = []
for i in range(n):
	L.append(A[i] - (i + 1))
L.sort()
if n == 1:
	b1 = L[0]
	b2 = L[0]
elif n == 2:
	b1 = L[0]
	b2 = L[1]
else:
	b1 = L[n // 2]
	b2 = L[n // 2 - 1]
ans = 0
cnt1 = 0
cnt2 = 0
for i in range(n):
	cnt1 += abs(L[i] - b1)
	cnt2 += abs(L[i] - b2)
print(min(cnt1, cnt2))


import statistics
n = int(input())
x = list(map(int, input().split()))
value = 0
for _ in range(n):
	x[_] -= _ + 1
x.sort()
for _ in x:
	value += abs(_ - x[n // 2])
print(value)


import statistics
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
	a[i] = a[i] - (i + 1)
min_sad = float('inf')
b = int(statistics.median(a))
for b_ in range(b - 1, b + 2):
	a_ = [abs(i - b_) for i in a]
	sad = sum(a_)
	min_sad = min(sad, min_sad)
print(min_sad)


import numpy as np
import statistics
n = int(input())
a = list(map(int, input().split()))
a = np.array(a, dtype=int)
one = np.ones(n, dtype=int)
stairs = np.add.accumulate(one)
a = a - stairs
b = int(statistics.median(a))

def pos(b):
	return sum(abs(a - b))
print(pos(b))


N = int(input())
A = list(map(int, input().split()))
A = [A[i] - (i + 1) for i in range(N)]
A = sorted(A)
A.insert(0, 0)
if N % 2 == 1:
	b = A[(N + 1) // 2]
	ans = 0
	for i in range(1, N + 1):
		ans += abs(A[i] - b)
else:
	b1 = A[N // 2]
	b2 = A[N // 2 + 1]
	bmax = max(b1, b2)
	bmin = min(b1, b2)
	if (bmax - bmin) % 2 == 0:
		b = (bmax + bmin) // 2
		ans = 0
		for i in range(1, N + 1):
			ans += abs(A[i] - b)
	else:
		b1 = (bmax + bmin) // 2
		a1 = 0
		for i in range(1, N + 1):
			a1 += abs(A[i] - b1)
		b2 = (bmax + bmin) // 2 + 1
		a2 = 0
		for i in range(1, N + 1):
			a2 += abs(A[i] - b2)
		ans = min(a1, a2)
print(ans)


N = int(input())
(*A,) = list(map(int, input().split()))
l = [j - i for (i, j) in enumerate(A, start=1)]
l.sort()
b = l[N // 2]
ans = sum((abs(i - b) for i in l))
print(ans)


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


N = int(input())
A = list(map(int, input().split()))
a = []
for i in range(N):
	a.append(A[i] - (i + 1))
a.sort()
ave = a[N // 2 - 1]
cnt1 = 0
cnt2 = 0
for i in range(N):
	cnt1 += abs(a[i] - ave)
for i in range(N):
	cnt2 += abs(a[i] - a[N // 2])
print(min(cnt1, cnt2))


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


from numpy import median
n = int(input())
alist = list(map(int, input().split()))
for i in range(n):
	alist[i] -= i + 1
med = int(median(alist))
ans = 0
for a in alist:
	ans += abs(a - med)
print(ans)