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



Sample input:
5
2 2 3 5 5


Sample output:
2

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
diff = []
for i, a in enumerate(A):
  diff.append(abs(a - (i + 1)))
med = list(sorted(diff))[N // 2]
print(abs(sum(diff) - med * N))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i, a in enumerate(A):
  ans += abs(a - (i + 1))
print(abs(ans - abs(N - max(A)) * N))

Submission status: Wrong Answer

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

for k in range(N):
    A[k] -= k

A.sort()


def get_pity_sum(x):
    pity_sum = 0
    for l in A:
        if A[x] - l >= 0:
            pity_sum += A[x] - l
        else:
            pity_sum += l - A[x]
    return pity_sum


if N % 2 == 1:
    print(get_pity_sum(int((N - 1) % 2)))
else:
    print(min(get_pity_sum(int(N / 2)), get_pity_sum(int(N / 2 - 1))))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    for i in range(N):
        A[i] -= i + 1
    s = sum(A)
    x = s // N
    ret = [0, 0, 0]
    for a in A:
        ret[0] += abs(a - (x - 1))
        ret[1] += abs(a - (x))
        ret[2] += abs(a - (x + 1))
    ret = min(ret)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    for i in range(N):
        A[i] -= i
    s = sum(A)
    x = s // N
    ret = [0, 0, 0]
    for a in A:
        ret[0] += abs(a - (x - 1))
        ret[1] += abs(a - (x))
        ret[2] += abs(a - (x + 1))
    ret = min(ret)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

b = sum(A) // N

def regret(A, b):
    result = 0
    for a in A:
        result += abs(a-b)
    return result

print(min(regret(A, b), regret(A, b+1)))

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
inputs = [int(i) for i in input().split()]
a = np.array(inputs)

min_num = 100000000000
z = a - np.array(range(1, n + 1))
nums = list(set(inputs))
#allnum = nums + list(np.array(nums) * (-1)) + [0]
allnum = []
allnum.append(min(abs(z)))
allnum.append(-min(abs(z)))
allnum.append(max(abs(z)))
allnum.append(-max(abs(z)))
allnum.append(0)

for x in allnum:
  min_sum = sum(abs(z - np.ones(len(a)) * x))
  if min_sum < min_num:
    min_num = min_sum

print(int(min_num))

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
inputs = [int(i) for i in input().split()]
a = np.array(inputs)

min_num = 100000000000
z = a - np.array(range(1, n + 1))
nums = list(set(inputs))
#allnum = nums + list(np.array(nums) * (-1)) + [0]
allnum = []
allnum.append(min(abs(z)))
allnum.append(-min(abs(z)))
allnum.append(max(abs(z)))
allnum.append(-max(abs(z)))


for x in allnum:
  min_sum = sum(abs(z - np.ones(len(a)) * x))
  if min_sum < min_num:
    min_num = min_sum

print(int(min_num))

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
inputs = [int(i) for i in input().split()]
a = np.array(inputs)

min_num = 100000000000
z = a - np.array(range(1, n + 1))
nums = list(set(inputs))
#allnum = nums + list(np.array(nums) * (-1)) + [0]
allnum = []
allnum.append(min(abs(z)))
allnum.append(-min(abs(z)))
for x in allnum:
  min_sum = sum(abs(z - np.ones(len(a)) * x))

  if min_sum < min_num:
    min_num = min_sum

print(int(min_num))

Submission status: Wrong Answer

Solution code:
n = int(input())
a_lst = [int(i) for i in input().split()]

def return_kanashisa(b):

	kanashisa = 0

	for a, num in zip(a_lst, range(1, n + 1)):
		kanashisa += abs(a - (b + num))

	return kanashisa

b_lst = []

def compare(b_1, b_2):
	if (return_kanashisa(b_1) > return_kanashisa(b_2)):
		return b_2
      
	else:
		return b_1
      
tmp = compare(-max(a_lst), max(a_lst))
if tmp < 0:
	for b in range(tmp, 0):
		b_lst.append(return_kanashisa(b))
else:
	for b in range(0, tmp):
		b_lst.append(return_kanashisa(b))
    
print(min(b_lst))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [0]*n
x = n * (max(a)-min(a))

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


for i in range(max(b)+1):
    cnt = 0
    for j in range(n):
        cnt += abs(b[j] - i - j)
    x = min(x,cnt)

print(x)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
inputs = [int(i) for i in input().split()]
a = np.array(inputs)

min_num = 100000000000
z = a - np.array(range(1, n + 1))
nums = list(set(inputs))
allnum = nums + list(np.array(nums) * (-1)) + [0]

for x in allnum:
  min_sum = sum(abs(z - np.ones(len(a)) * x))
  #print(abs(a - np.array(range(1, n + 1))))
  if min_sum < min_num:
    min_num = min_sum

print(int(min_num))

Submission status: Wrong Answer

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

x = 2*10**5*10**9

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


for i in range(max(a)+1):
    cnt = 0
    for j in range(n):
        cnt += abs(a[j] - i - j)
    x = min(x,cnt)

print(x)

Submission status: Wrong Answer

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

x = 2*10**5*10**9

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


for i in range(max(a)):
    cnt = 0
    for j in range(n):
        cnt += abs(a[j] - i - j)
    x = min(x,cnt)

print(x)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.array([int(i) for i in input().split()])

min_num = 100000000000

for x in range(-(max(a)), max(a) + 1):
  min_sum = sum(abs(a - np.ones(len(a)) * x - np.array(range(1, n + 1))))
  #print(abs(a - np.array(range(1, n + 1))))
  if min_sum < min_num:
    min_num = min_sum

print(min_num)

Submission status: Wrong Answer

Solution code:
from math import ceil, floor
n=int(input())
aa=list(map(int,input().split()))
b=sum(a-i-1 for i,a in enumerate(aa)) / n
print(min(sum(abs(a-b-i-1) for i,a in enumerate(aa)) for b in (ceil(b), floor(b))))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
for i in range(N):
  A[i] = A[i] - i - 1
ave = sum(A) // N
ans1 = 0
ans2 = 0
ans3 = 0
for i in range(N):
  ans1 += abs(A[i] - ave)
  ans2 += abs(A[i] - ave - 1)
  ans3 += abs(A[i] - ave + 1)
print(min(ans1, ans2, ans3))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
for i in range(N):
  A[i] = A[i] - i - 1
ave = sum(A) // N
ans1 = 0
ans2 = 0
for i in range(N):
  ans1 += abs(A[i] - ave)
  ans2 += abs(A[i] - ave - 1)
print(min(ans1, ans2))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def ternary_search( search_range, f, n = 100, eps = 1e-24 ):
    l, r = search_range
    for i in range( n ):
        ll = ( l + l + r ) / 3.0
        rr = ( l + r + r ) / 3.0

        vl = f( ll )
        vr = f( rr )
        if abs( vl - vr ) < eps:
            break

        if vl > vr :
            r =rr 
        else:
            l =ll 

    return ( l + r ) / 2.0


def solve(N: int, A: "List[int]"):
    A = sorted([a - i for i, a in enumerate(A, 1)])

    def _f(b):
        return -sum([abs(a - b) for a in A])

    b = ternary_search((A[0], A[-1]), _f)
    return -int(round(_f(b)))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    result = solve(N, A)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, A: "List[int]"):
    A = [a - i for i, a in enumerate(A, 1)]
    b0 = int(floor(sum(A) / len(A)))
    b1 = int(ceil(sum(A) / len(A)))
    r0 =  sum([abs(a - b0) for a in A])
    r1 =  sum([abs(a - b1) for a in A])
    return min(r0, r1)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    result = solve(N, A)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
lista = [int(i) for i in input().split()]
summ = 0
for i in range(n):
    summ += lista[i]-(1*i +1)
ave = summ//n
ans = 0
for i in range(n):
    ans += abs(lista[i]-(1*i +1)-ave)
    
ave = summ//n
ave += 1
ans1 = 0
for i in range(n):
    ans1 += abs(lista[i]-(1*i +1)-ave)
    
ave = summ//n
ave -= 1
ans2 = 0
for i in range(n):
    ans2 += abs(lista[i]-(1*i +1)-ave)
    
print(min(ans,ans1,ans2))

Submission status: Wrong Answer

Solution code:
n=int(input())
lista = [int(i) for i in input().split()]
summ = 0
for i in range(n):
    summ += lista[i]-(1*i +1)
ave = summ//n
if ave<0:
    ave+=1
ans = 0
for i in range(n):
    ans += abs(lista[i]-(1*i +1)-ave)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
lista = [int(i) for i in input().split()]
summ = 0
for i in range(n):
    summ += lista[i]-(1*i +1)
ave = summ//n
ans = 0
for i in range(n):
    ans += abs(lista[i]-(1*i +1)-ave)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int, input().split()))
from collections import Counter
import itertools

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

mode_v = c.most_common()[0][-1]
it = itertools.takewhile(
    lambda kv: kv[-1] == mode_v, c.most_common()
)
a = [k for k, v in it]
x = 10**10
for ai in a:
    x = min(abs(ai), x)
ans = 0
for i in range(1, N+1):
    ans += abs(A[i-1]-(x+i))
print(ans)

Submission status: Wrong Answer

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

print(sum(A))

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = [int(v)-(i+1) for i,v in enumerate(input().split())]
num = math.floor(sum(A)/len(A))
ret = 0
for i in A:
    ret += abs(i-num)

print(ret)

Submission status: Wrong Answer

Solution code:
def main():
	N = int(input())
	A = list(map(int, input().split()))
	ans = 0
	max_val = 0
	for i in range(N):
		max_val = max(max_val, abs(A[i]-(i+1)))

	l = -max_val
	r = max_val+1

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

	pre = l
	while l < r:
		mid = (l+r)//2
		this_ans = 0
		for i in range(N):
			this_ans += abs(A[i]-(mid+i+1))
		if this_ans < ans:
			ans = this_ans
			if pre == l:
				r = mid-1
			else:
				l = mid
				pre = r
		else:
			if pre == l:
				l = mid
				pre = r
			else:
				r = mid-1
	print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

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

c=math.ceil(sum(A)/len(A))
f=math.floor(sum(A)/len(A))

print(min(sum([abs(a-c) for a in A]), sum([abs(a-f) for a in A])))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(v)-k for k,v in enumerate(input().split())]

z=sum(A)//len(A)
print(sum([abs(a-z) for a in A]))

Submission status: Wrong Answer

Solution code:
import statistics

n = int(input())
a = [a - i - 1 for i, a in enumerate(map(int, input().split()))]
m_a = statistics.median(a)
print(sum(i - m_a if i > m_a else m_a - i for i in a))

Submission status: Wrong Answer

Solution code:
import statistics


N = int(input())
A = list(map(int, input().split()))
sum_a = 0
B = [0]*len(A)
for i in range(N):
    B[i] = A[i] - i
B.sort()
sum_b = 0
b = statistics.median(B)
for i in range(N):
    sum_b += abs(B[i]-b)
print(sum_b)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
sum_a = 0
min_sum = 10000000000000000000
for b in range(-10000, 10000):
    sum_a = 0
    for i in range(N):
        sum_a += abs(A[i] - (b + i + 1))
    if sum_a <= min_sum:
        min_sum = sum_a
print(min_sum)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
sum_a = 0
min_sum = 10000000000000000000
for b in range(-10, 10):
    sum_a = 0
    for i in range(N):
        sum_a += abs(A[i] - (b + i + 1))
    if sum_a <= min_sum:
        min_sum = sum_a
print(min_sum)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
for i in range(N):
    A[i] -= i+1
sunuke = A[N // 2]
ans = 0
for a in A:
    ans += abs(a-sunuke)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
	A[i] -= (i + 1)
average_A = sum(A) // N
temp_ave = [average_A,average_A+1]
temp_ans = []
for i in temp_ave:
	temp_sum = 0
	for j in A:
		temp_sum += abs(i - j)
	temp_ans.append(temp_sum)

print(min(temp_ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
a_list = [int(i) for i in input().split()]
a_list.sort()
b1,b2 = a_list[N//2-1], a_list[N//2]
c1,c2 = 0,0
for i in range(N):
    c1 += abs(a_list[i] - (b1 + i + 1))
for i in range(N):
    c2 += abs(a_list[i] - (b2 + i + 1))
print(min(c1,c2))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,input().split()))
b = [b-i for i,b in enumerate(a,1)]
m,M = min(b),max(b)
if m<0 and M>0:
    out = sum([abs(c) for c in b])
elif m>=0:
    out = sum([abs(c-m) for c in b])
else:
    out = sum([abs(c-M) for c in b])
print(out)

Submission status: Wrong Answer

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

import statistics
b = statistics.median(a)
ans = sum([abs(i-b) for i in a])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(map(int,input().split()))
t = 0
r = 0
w = 0
o = 0
for i in range(n):
    t += s[i] - ( i + 1 )
    s[i] = s[i] - ( i + 1 )
k = t // n
for i in range(n):
    r += abs(s[i] - k)
    w += abs(s[i] - k-1)
    o += abs(s[i] - k+1)
print(min(r,w,o))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(map(int,input().split()))
t = 0
r = 0
for i in range(n):
    t += s[i] - ( i + 1 )
    s[i] = s[i] - ( i + 1 )
k = t // n
for i in range(n):
    r += abs(s[i] - k)
print(r)

Submission status: Wrong Answer

Solution code:
import math
import statistics


N = int(input())
A = [int(i) for i in input().split()]
b = math.ceil(statistics.median([a-n for a,n in zip(A,range(1,N+1))]))
print(b)
ans = [abs(a - b - n) for a,n in zip(A,range(1, N+1))]
print(sum(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
b = (sum(A) - sum(range(1, N+1))) // N
ans = [abs(a - b - n) for a,n in zip(A,range(1, N+1))]
print(sum(ans))

Submission status: Wrong Answer

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

A_ = [a--1-i for i,a in enumerate(A)]
b = int(0.5 * (A_[len(A_)//2] + A_[len(A_)//2 - (len(A_)+1)%2]))

print(sum([abs(a-b) for a in A_]))

Submission status: Wrong Answer

Solution code:
import numpy as np


def f(_b, _a):
    return sum([abs(i - _b) for i in _a])


N = int(input())
A = list(map(int, input().split()))
A = [a - i - 1 for i, a in enumerate(A)]
b = int(np.mean(A))
print(min(f(b, A), f(b + 1, A), f(b - 1, A)))

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
c=0
if n%2==0:
  for i in range(n):
    l[i]=l[i]-i-1
  l1=sorted(l)
  for i in range(n):
    l1[i]=abs(l1[i]-l1[n//2-1]//2-l1[n//2]//2)
    c+=l1[i]
  print(c)
else:
  for i in range(n):
    l[i]=l[i]-i-1
  l1=sorted(l)
  for i in range(n):
    l1[i]=abs(l1[i]-l1[(n-1)//2])
    c+=l1[i]
  print(c)

Submission status: Wrong Answer

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

res = 10 ** 10
if n % 2 == 0:
	p = n // 2 - 1
	q = n // 2
	for cand in [p, q]:
		tmp = 0
		for i in a:
			tmp += abs(i - a[cand])
		res = min(res, tmp)
else:
	tmp = 0
	for i in a:
		tmp += abs(i - a[n // 2])
	res = min(res, tmp)
	
print(res)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
 
import statistics
 
N = int(input())
A = list(map(int, input().rstrip().split(' ')))
 
A_dash = sorted([x - i - 1 for i, x in enumerate(A)])
med = statistics.median(A_dash)

print(sum([abs(x - med) for x in A_dash]))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

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

A_dash = [x - i - 1 for i, x in enumerate(A)]
b = sum(A_dash) // len(A_dash)

print(sum([abs(x - b) for x in A_dash]))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


inf = float('inf')


# globals
N = 0
A = []


def set_inputs():
    global N, A
    N = get_int()
    A = get_li()
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    X = [a - (i + 1) for i, a in enumerate(A)]
    b = round(float(sum(X)) / float(N))
    print(min(sum(abs(x-(b-1)) for x in X), sum(abs(x-b) for x in X), sum(abs(x-(b+1)) for x in X)))
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


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


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[0]
c=[0]
count=0
count2=0
for i in range(n):
  a[i]-=i
for i in range(n-1):
  count+=a[i+1]-a[i]
  b.append(count)
for i in range(n-1):
  count2+=b[i+1]
  c.append(count2)
ans=10**18
for i in range(n):
  ans=min(ans,c[-1]-c[i]-b[i]*(n-i-1))
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[0]
c=[0]
count=0
count2=0
for i in range(n):
  a[i]-=i
for i in range(n-1):
  count+=a[i+1]-a[i]
  b.append(count)
for i in range(n-1):
  count2+=b[i+1]-b[i]
  c.append(count2)
ans=10**18
for i in range(n):
  ans=min(ans,c[-1]-i*c[i])
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def sadness(A, b):
    return sum([abs(a-b) for a in A])

N = int(input())
B = [int(a) - (i+1) for i, a in enumerate(input().split())]

sum_B = sum(B)
b1 = sum_B//len(B)
b2 = -(-sum_B//len(B))

print(min(sadness(B, b1), sadness(B, b2)))

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
A = list(map(int, input().split()))
s = 0
c = 0
f = 0
for i in range(N):
    A[i] = A[i] - i
#print(A)
#m = round(sum(A)/N)
c = math.ceil(sum(A)/N)
f = math.floor(sum(A)/N)
if c == f:
    for j in range(N):
        s += abs(A[j] - c)
    print(s)
else:
    r = 0
    for j in range(N):
        s += abs(A[j] - c)
#    print(s)
    for k in range(N):
        r += abs(A[k] - f)
#    print(r)
    print(min(s, r))

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
A = list(map(int,input().split()))
s = 0
c = 0
f = 0
for i in range(N):
    A[i] = A[i] - (i+1)
#print(A)
m = round(sum(A)/N)
c = math.ceil(sum(A)/N)
f = math.floor(sum(A)/N)
if c == f:
    for j in range(N):
        s += abs(A[j] - c)
    print(s)
else:
    r = 0
    for j in range(N):
        s += abs(A[j] - c)
#    print(s)
    for k in range(N):
        r += abs(A[k] - f)
#    print(r)
    print(min(s,r))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(item) for item in input().split()]

for i in range(n):
  a[i] -= i+1
  
ave = round(sum(a) / n)

b1, b2, b3 = 0, 0, 0
for i in range(n):
  b1 += abs(a[i] - ave - 1)
  b2 += abs(a[i] - ave)
  b3 += abs(a[i] - ave + 1)
  
print(min([b1, b2, b3]))

Submission status: Wrong Answer

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

l = sum([a-i-1 for i,a in enumerate(A)])//N

print(min(sum([abs(a-i-1-l) for i, a in enumerate(A)]),
sum([abs(a-i-l) for i, a in enumerate(A)])))

Submission status: Wrong Answer

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

l = sum([a-i-1 for i,a in enumerate(A)])//N

print(max(sum([abs(a-i-1-l) for i, a in enumerate(A)]),
sum([abs(a-i-1) for i, a in enumerate(A)])))

Submission status: Wrong Answer

Solution code:
N=input()
N=int(N)
M=list(map(int,input().split()))

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

M.sort()

if N%2==0:
  p=M[int(N/2)-1]+M[int(N/2)]
else:
  p=M[int((N+1)/2)-1] 

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

  
print(sum)

Submission status: Wrong Answer

Solution code:
from statistics import median as m;n=input();d=[i-h-1 for h,i in enumerate(list(map(int,input().split())))];print(sum([abs(i-m(d)) for i in d]))

Submission status: Wrong Answer

Solution code:
n = int(input())
H = list(map(int,input().split()))
h = []
for i in range(n):
    h.append(H[i]-(i+1))
ave = sum(h)//n
s = 0
for i in h:
    s += abs(i-ave)
print(s)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
n = int(input())
a = list(map(int, input().split()))
for i in range(len(a)):
    a[i] -= i + 1
a.sort()
mean = sum(a) / len(a)
il = bisect_left(a, mean)
res = 10 ** 30
for i in [max(0, il-1), il]:
    total = 0
    for j in range(len(a)):
        total += abs(a[i] - a[j])
    res = min(res, total)
print(res)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
n = int(input())
a = list(map(int, input().split()))
for i in range(len(a)):
    a[i] -= i + 1
a.sort()
mean = sum(a) / len(a)
il = bisect_left(a, mean)
ir = bisect_right(a, mean)
res = 10 ** 10
for i in [max(0, il-1), il, min(len(a)-1, ir), ir-1]:
    total = 0
    for j in range(len(a)):
        total += abs(a[i] - a[j])
    res = min(res, total)
print(res)

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

test = False
if test:
    N = 2*10**5
    A = [i*2 for i in range(N)]
else:
    N = I()
    A = LI()

for idx in range(0, N):
    A[idx] -= idx + 1

import statistics
b = statistics.median(A)
#  print('b', b)
result = 10**10
for i in range(-1, 2, 1):
    tmp = 0
    for a in A:
        tmp += abs(a-(b+i))
    result = min(result, tmp)
print(int(result))

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

test = False
if test:
    N = 2*10**5
    A = [i*2 for i in range(N)]
else:
    N = I()
    A = LI()

for idx in range(0, N):
    A[idx] -= idx + 1

b = round(sum(A) / len(A))
b = round(b)
#  print('b', b)
result = 10**10
for i in range(-1, 2, 1):
    tmp = 0
    for a in A:
        tmp += abs(a-(b+i))
    result = min(result, tmp)
print(result)

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

N = I()
A = LI()

for idx in range(0, len(A)):
    A[idx] -= idx + 1
#  print(A)
b = sum(A) // len(A)
#  print(b)
result = 0
for a in A:
    result += abs(a-b)
print(result)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import Counter
N=int(input())
A=list(map(int,input().split()))
l=[]
ans=0
n=1
for i in A:
    l.append(i-n)
    n+=1
c=Counter(l)
#print(c.most_common())

if c.most_common()[0][1]>1:
    b=c.most_common()[0][0]
    #print("b",b)
    for i in l:
        ans+=abs(i-b)
#    ans-=Nb
else:
    for i in l:
        ans+=abs(i)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
Ai = list(map(int, input().split()))

avg = 0
for i in range(N):
    avg += Ai[i] - (i + 1)

avg = avg // N
ans = 0
for i in range(N):
    a = abs(Ai[i] - (avg + i + 1))
    ans += a
avg += 1
ans2 = 0
for i in range(N):
    a = abs(Ai[i] - (avg + i + 1))
    ans2 += a
print(min(ans, ans2))

Submission status: Wrong Answer

Solution code:
N = int(input())
Ai = list(map(int, input().split()))

avg = 0
for i in range(N):
    avg += Ai[i] - (i + 1)
avg = avg // N
ans = 0
for i in range(N):
    a = abs(Ai[i] - (avg + i + 1))
    ans += a
print(ans)

Submission status: Wrong Answer

Solution code:
import statistics
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()
m=statistics.median(b)
b=list(map(lambda x:abs(x-m),b))
ans=0
for i in range(n):
    ans+=b[i]
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in range(n):
    b[i]=a[i]-(i+1)
s=0
for i in range(n):
    s+=b[i]
mean=s//(len(b))
ans=10**10
mi=mean-10**2
ma=mean+10**2
for i in range(mi,ma):
    w=0
    c=list(map(lambda x:abs(x-i),b))
    for j in range(n):
        w+=c[j]
    if w<ans:
        ans=w
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
N=int(input())
A=list(map(int,input().split()))
B=[A[i]-i-1 for i in range(N)]
B.sort()
if N%2==0:
    b=B[N//2]
else:
    b=(B[N//2-1]+B[N//2])//2
print(sum([abs(Bb-b) for Bb in B]))

Submission status: Wrong Answer

Solution code:
import numpy as np
N=int(input())
A=list(map(int,input().split()))
B=list(A[i]-i-1 for i in range(N-1))
#B.sort()
#print(B)
b=np.median(B)
print(int(sum([abs(Bb-b) for Bb in B])))

Submission status: Wrong Answer

Solution code:
# 中央値が最適値(数直線で考える)
N = int(input())
A = [int(i) for i in input().split()]
for i in range(len(A)):
    A[i] -= i+1
A.sort()
b = A[N // 2]
print(sum([abs(a) for a in A]))

Submission status: Wrong Answer

Solution code:
# def decrement(a):
#    return a-1


N = int(input())
A = [int(i) for i in input().split()]
for i in range(len(A)):
    A[i] -= i+1
# print(A)
average_A = sum(A) / N
int_average = round(average_A)
#print(average_A, int_average)
"""
print([a for a in A])  # if a > 0])
while len([a for a in A if a > 0]) > N // 2:
    A = list(map(decrement, A))
    print(A)
# print(A)
print(sum([abs(a) for a in A]))
"""
ans = [sum(list(map(lambda x: abs(x-int_average+1), A)))
       for i in range(-100, 100)]
print(min(ans))