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:
import copy
input()
a=[int(i) for i in input().split()]
sa=copy.copy(a)
for i in range(len(a)):
    sa[i]=sa[i]-(i+1)
b=sum(sa)//len(a)
c=sum(sa)//len(a)+1
sb=0
sc=0
for i in range(len(a)):
    sb=sb+abs(a[i]-(b+i+1))
    sc=sc+abs(a[i]-(c+i+1))
print(min(sb,sc))

Submission status: Wrong Answer

Solution code:
input()
a=[int(i) for i in input().split()]
for i in range(len(a)):
    a[i]=a[i]-(i+1)
b=sum(a)//len(a)
c=sum(a)//len(a)+1
sb=0
sc=0
for i in range(len(a)):
    sb=sb+abs(a[i]-b)
    sc=sc+abs(a[i]-c)
print(min(sb,sc))

Submission status: Wrong Answer

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
A_sub_list = [a - (i + 1) for i, a in enumerate(A_list)]
b_max = max(abs(max(A_sub_list)), abs(min(A_sub_list)))
b_min = -b_max
min_s = pow(10, 10)
for b in range(b_min, b_max + 1):
    s = sum([abs(a - b) for a in A_sub_list])
    if s < min_s:
        min_s = s
    else:
        break
print(min_s)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
A_sub_list = [a - (i + 1) for i, a in enumerate(A_list)]
b_max = max(A_sub_list)
b_min = min(A_sub_list)
min_s = pow(10, 10)
for b in range(b_min, b_max + 1):
    s = sum([abs(a - b) for a in A_sub_list])
    if s < min_s:
        min_s = s
    else:
        break
print(min_s)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
A_sub_list = [a - (i + 1) for i, a in enumerate(A_list)]
b_max = max(A_sub_list)
b_min = min(A_sub_list)
min_s = pow(10, 10)
for b in range(b_min, b_max + 1):
    s = sum([abs(a - b) for a in A_sub_list])
    min_s = min(min_s, s)
    if s < min_s:
        min_s = s
    else:
        break
print(min_s)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
A_sub_list = [a - (i + 1) for i, a in enumerate(A_list)]
b_max = max(A_sub_list)
b_min = min(A_sub_list)
min_s = pow(10, 10)
for b in range(b_min, b_max + 1):
    s = sum([abs(a - b) for a in A_sub_list])
    min_s = min(min_s, s)
    if min_s < s:
        min_s = s
    else:
        break
print(min_s)

Submission status: Wrong Answer

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

sorted_A = sorted(A)
center_idx = int(N/2)
center_num = sorted_A[center_idx]
num = center_num - (center_idx + 1)
ans = 0
for i in range(N):
	ans += abs(A[i]-(num + (i+1)))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
min_sum = -1
for b in range(-len(A_list), len(A_list)):
    s = 0
    for i, a in enumerate(A_list):
        s += abs(a - (b + (i + 1)))
    if min_sum == -1:
        min_sum = s
    min_sum = min(min_sum, s)
print(min_sum)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
min_sum = -1
for b in range(len(A_list)):
    s = 0
    for i, a in enumerate(A_list):
        s += abs(a - (b + (i + 1)))
    if min_sum == -1:
        min_sum = s
    min_sum = min(min_sum, s)
print(min_sum)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
min_sum = 0
for b in range(len(A_list)):
    sum = 0
    for i, a in enumerate(A_list):
        sum += abs(a - (b + i))
    if min_sum == 0:
        min_sum = sum
    min_sum = min(min_sum, sum)
print(min_sum)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
min_sum = 0
for b in range(len(A_list)):
    sum = 0
    for i, a in enumerate(A_list):
        sum += abs(a - (b + i))
    min_sum = min(min_sum, sum)
print(min_sum)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import statistics as s
n = int(input())
an = list(map(int, input().split()))
a = []
sum = 0
for i in range(n):
  a.append(an[i] - i+1) 
b = s.median(a)
for i in range(n):
  sum += abs(an[i] - (b + i))  
print(int(sum))

Submission status: Wrong Answer

Solution code:
n = int(input())
an = list(map(int, input().split()))
s = 114514
for b in range(9999):
  tmp = 0
  for i in range(n):
    tmp += abs(an[i] - (b + i))
  if s > tmp:
    s = tmp
  else:
    break
print(s)

Submission status: Wrong Answer

Solution code:
import math

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

b = [math.floor(sum(A)/len(A)), math.ceil(sum(A)/len(A))]
anss = []
for i in range(2):
    anss.append(sum(list(map(lambda a:abs(a-b[i]), A))))

print(min(anss))

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

median = A[N//2]

for i in range(N):
    A[i] -= median
print(sum(A))

Submission status: Wrong Answer

Solution code:
n = input()
xs = input().split(" ")

l = list()
for x in xs:
	l.append(int(x))


ll = list()
for x in range(max(l)):
	for index, argv in enumerate(l):
		ls = list()		
		ab = abs(argv - (x + index))
		ls.append(ab)
	ll.append(ls)

sum_list = list()
for line in ll:
	s = sum(line)
	sum_list.append(s)

print(min(sum_list))

Submission status: Wrong Answer

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

print(sum([abs(a_i-(i+1)) for i, a_i in enumerate(a)]))

Submission status: Wrong Answer

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

print(sum(a)%n)

Submission status: Wrong Answer

Solution code:
N = int(input())
numbers = list(map(int, input().split()))
min_num = min(numbers)
max_num = max(numbers)
abs_= float('inf')
for b in range(min_num, max_num+1):
    abs_pre = sum([abs(a-b-i) for i, a in enumerate(numbers)])
    if abs_pre < abs_:
        abs_ = abs_pre
print(abs_)

Submission status: Wrong Answer

Solution code:
N = int(input())
numbers = list(map(int, input().split()))
min_num = min(numbers)
max_num = max(numbers)
abs_= float('inf')
for b in range(min_num, max_num):
    abs_pre = sum([abs(a-b-i) for i, a in enumerate(numbers)])
    if abs_pre < abs_:
        abs_ = abs_pre
print(abs_)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
a = [int(i) for i in input().split()]
b = [elem - i for i, elem in enumerate(a, 1)]
b.sort
center = b[math.floor(len(b) / 2)]
c = [abs(i - center) for i in b]
print(sum(c))

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
a = [int(i) for i in input().split()]
b = [elem - i for i, elem in enumerate(a, 1)]
center = abs(b[math.floor(len(b) / 2)])
c = [abs(i + center) for i in b]
print(sum(c))

Submission status: Wrong Answer

Solution code:
import statistics

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


for i in range(len(a)):
    a[i] -= (i+1)
med = statistics.median(a)
b = [a_i-med for a_i in a] 
S=0
for i in b:
    S += abs(i)
    
print(S)

Submission status: Wrong Answer

Solution code:
import statistics

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

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

med = statistics.median(a)
b = [a_i-med for a_i in a] 

S=0
for i in b:
    S += i
    
print(S)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
num_list = map(int, input().split())

B_list = list()
for i, num in enumerate(num_list):
    B_list.append(num - (i + 1))

if N % 2 != 0:
    centre_index = math.ceil(N / 2)
    b = B_list[centre_index - 1]
    loss = 0
    
    for i in range(N):
        loss += abs(B_list[i] - b)
        
else:
    centre_left_index = N // 2 - 1
    centre_right_index = centre_left_index + 1
    b1 = B_list[centre_left_index]
    b2 = B_list[centre_right_index]
    loss1 = 0
    loss2 = 0
    
    for i in range(N):
        loss1 += abs(B_list[i] - b1)
        loss2 += abs(B_list[i] - b2)
    
    loss = loss1 if loss1 < loss2 else loss2

print(str(loss))

Submission status: Wrong Answer

Solution code:
n = int(input())

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

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

print(l)

Submission status: Wrong Answer

Solution code:
from statistics import median

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

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

b = median(A)
ans = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
array = [int(x) for x in input().split()]
array2 = [array[x]-(x+1) for x in range(n)]

b_ = array2[n//2]

res = [abs(array[x]-(b_+x+1)) for x in range(n)]
print(min(sum(res), sum(array2)))

Submission status: Wrong Answer

Solution code:
n = int(input())
array = [int(x) for x in input().split()]
array2 = [array[x]-(x+1) for x in range(n)]

b_ = array2[n//2]

res = [abs(array[x]-(b_+x+1)) for x in range(n)]
print(sum(res))

Submission status: Wrong Answer

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

Ni = list(range(1, N + 1))

i=0
before = 0
flag = 0
while True:
    i += 1
    sum_diff = sum([abs(a-i) for a, i in zip(A, Ni)])//i
    if flag == 0:
        before = sum_diff
        flag = 1

    if sum_diff >= before:
        break

print(before)

Submission status: Wrong Answer

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

Ni = list(range(1, N + 1))
print(sum([abs(a-i) for a, i in zip(A, Ni)]))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]
B = [ av - i  for i, av in enumerate(a,1)]
B.sort
middle = len(B) //2
b = B[middle]

result = 0
for a2 in B:
  result = result + abs(a2 -b)
print(result)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]
B = [ av - i  for i, av in enumerate(a,1)]
b = B[len(B) // 2]

result = 0
for a2 in B:
  result = result + abs(a2 -b)
print(result)

Submission status: Wrong Answer

Solution code:
# median を import する
from statistics import median

# N と Ai を標準入力
N = int(input())
listNumsAs = list(map(int,input().split()))

# 空のリスト listNumsBs を用意
listNumsBs = []

# listNumAs の各要素から、その (index + 1) の数を引いた (Ai - (i + 1)) をリスト listNumsBs に順番に代入
for index in range(len(listNumsAs)):
    listNumsBs.append(listNumsAs[index] - index - 1)

# listNumsBs を昇順にソートする
listNumsBs.sort()

# listNumsBs の中央値を med に代入する
med = int(median(listNumsBs))
print("med: " + str(med))

listSadnessA1 = [abs(s - med - N) for s in listNumsBs]
minimumSum = sum(listSadnessA1)

# listNumsBs の中央値 ± N の範囲の変数 b で処理を繰り返す
for b in range(med - N, med + N):
    
    # 悲しさ指数のリスト listSadness に (Bi - b) の絶対値の計算結果を順番に代入する
    listSadness = [abs(s - b) for s in listNumsBs]
       
    if sum(listSadness) < minimumSum:
        minimumSum = sum(listSadness)
        listTruthSadness = listSadness
        truthB = b
print(minimumSum)

Submission status: Wrong Answer

Solution code:
a = int(input())
b = input().split()
c = []
for i in range(a):
  c.append(int(b[i]))
g = []
for i in range(a):
  g.append(c[i] - i-1)
g.sort()
d = g[int(a/2)]
f = 0
for i in range(a):
  e = abs(c[i]-(d+i+1))
  f += e
f

Submission status: Wrong Answer

Solution code:
from statistics import median
N = int(input())
A = [int(i) for i in input().split()]

B = [A[i] - (i+1) for i in range(N)]
b = int(median(B))

C = [abs(B[i] - b) for i in range(N)]

print(C)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

n = int(input())
a = list(map(int, input().split(" ")))
B = 0
cry = 0

for i in range(n):
    cry += abs(a[i] - (B+i+1))
print(cry)

Submission status: Wrong Answer

Solution code:
def main6():
    buf = int(input(""));
    strbuf = input("");
    strbufs = strbuf.split();
    buf2 = []
    saisyo = 100000000000000000000000;
    for i in range(buf):
        buf2.append((int(strbufs[i])-(i+1)));
    maxi = max(buf2);
    mini = min(buf2);
    kari2 = 0;
    for i in range(buf):
        kari2 = kari2 + buf2[i];
    kari2 =int(kari2/buf) -5;

    for i in range(kari2,kari2+10):
        kari = 0
        for j in range(buf):
            kari = kari + abs(buf2[j]-i);
        if kari < saisyo:
            saisyo = kari;

    print(saisyo);

if __name__ == '__main__':
    main6()

Submission status: Wrong Answer

Solution code:
def main6():
    buf = int(input(""));
    strbuf = input("");
    strbufs = strbuf.split();
    buf2 = []
    saisyo = 100000000;
    for i in range(buf):
        buf2.append((int(strbufs[i])-(i+1)));
    maxi = max(buf2);
    mini = min(buf2);
    kari2 = 0;
    for i in range(buf):
        kari2 = kari2 + buf2[i];
    kari2 =int(kari2/buf) -5;

    for i in range(kari2,kari2+10):
        kari = 0
        for j in range(buf):
            kari = kari + abs(buf2[j]-i);
        if kari < saisyo:
            saisyo = kari;

    print(saisyo);

if __name__ == '__main__':
    main6()

Submission status: Wrong Answer

Solution code:
def main6():
    buf = int(input(""));
    strbuf = input("");
    strbufs = strbuf.split();
    buf2 = []
    saisyo = 100000000;
    for i in range(buf):
        buf2.append((int(strbufs[i])-(i+1)));
    maxi = max(buf2);
    mini = min(buf2);
    kari2 = 0;
    for i in range(buf):
        kari2 = kari2 + buf2[i];
    kari2 =int(kari2/buf) -2;

    for i in range(kari2,kari2+4):
        kari = 0
        for j in range(buf):
            kari = kari + abs(buf2[j]-i);
        if kari < saisyo:
            saisyo = kari;

    print(saisyo);

if __name__ == '__main__':
    main6()

Submission status: Wrong Answer

Solution code:
from statistics import median

N = int(input())
listNumsAs = list(map(int,input().split()))
listNumsBs = []

for index in range(len(listNumsAs)):
    listNumsBs.append(listNumsAs[index] - index - 1)
listNumsBs.sort()
med = int(median(listNumsBs))
listSadnessA1 = [abs(s - med - N) for s in listNumsBs]
minimumSum = sum(listSadnessA1)

for b in range(med - N, med + N):
    listSadness = [abs(s + b) for s in listNumsBs]
       
    if sum(listSadness) < minimumSum:
        minimumSum = sum(listSadness)
        
print(minimumSum)

Submission status: Wrong Answer

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

cnt = 0

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

if N % 2 == 0:
    b = (c[N // 2] + c[N // 2 - 1]) / 2
else:
    b = c[N // 2]
for i in range(N):
    cnt += abs(L[i] - (b + i + 1))
print(int(cnt))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
b = 0
for i, num in enumerate(A):
    b += num - i - 1
extreme1 = b // N
extreme2 = extreme1 + 1
ans1 = ans2 = 0
for i, num in enumerate(A):
    ans1 += abs(num - (extreme1 + i + 1))
    ans2 += abs(num - (extreme2 + i + 1))
print(ans1 if ans1 < ans2 else ans2)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = map(int, input().split())
b = 0
for i, num in enumerate(A):
    b += num - i - 1
extreme1 = b // N
extreme2 = extreme1 + 1
ans1 = ans2 = 0
for i, num in enumerate(A):
    ans1 += abs(num - (extreme1 + i + 1))
    ans2 += abs(num - (extreme2 + i + 1))
print(ans1 if ans1 < ans2 else ans2)

Submission status: Wrong Answer

Solution code:
import statistics
n = int(input())
a_list = list(map(int, input().split()))

pro_list = [a_list[i-1] - i for i in range(1, n+1)]
ave = int(statistics.mean(pro_list))

b_list = [ave-1, ave, ave+1]

ans = [sum([abs(pro-b)for pro in pro_list]) for b in b_list]
print(min(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in list(input().split())]
sum = 0

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

A.sort()

min1 = 0
min2 = 0

if N % 2 == 1:
    mid1 = A[(N - 1) // 2]
    for i in range(N):
        min1 += abs(A[i] - mid1)
    print(min1)

else:
    mid1 = (A[N // 2] - A[N // 2 - 1]) // 2
    mid2 = mid1 + 1
    for i in range(N):
        min1 += abs(A[i] - mid1)
        min2 += abs(A[i] - mid2)
    if min1 < min2:
        print(min1)
    else:
        print(min2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
absx = 0
list0 = []
for b in range(-10000,10000):
    for j in range(len(A)):
        absj = abs(A[j]-(b+j))
        absx += absj
    list0.append(absx)
    absx=0
print(min(list0))

Submission status: Wrong Answer

Solution code:
import numpy
N=int(input())
A=list(map(int,input().split()))
B=[A[i]-i for i in range(N)]
C=int(numpy.median(B))
print(sum([b-C for b in B]))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(input().split())
sum = 0

for i in range(N):
    A[i] = int(A[i]) - (i + 1)
    sum += A[i]
ave1 = sum // N
ave2 = ave1 + 1

min1 = 0
min2 = 0

for i in range(N):
    min1 += abs(A[i] - ave1)
    min2 += abs(A[i] - ave2)

if min1 < min2:
    print(min1)
else:
    print(min2)

Submission status: Wrong Answer

Solution code:
from bisect import bisect

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

cums = [0]
for a in src:
    cums.append(cums[-1] + a)

ans = cums[-1] * 999
for c in range(2,N-1):
    b1 = bisect(cums[:c], cums[c]//2)
    b2 = bisect(cums[c:], (cums[c]+cums[-1])//2) + c
    pq_cands = []
    for i in (b1,b1-1):
        if not 0 < i < c: continue
        p = cums[i]
        q = cums[c] - cums[i]
        pq_cands.append((p,q))
    rs_cands = []
    for i in (b2,b2-1):
        if not c < i < N: continue
        r = cums[i] - cums[c]
        s = cums[-1] - cums[i]
        rs_cands.append((r,s))
    for p,q in pq_cands:
        for r,s in rs_cands:
            mn = min(p,q,r,s)
            mx = max(p,q,r,s)
            ans = min(ans, mx-mn)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
total = sum(a)
b = round(total/n-(n+1)/2)
ans = 0
for i in range(n):
	ans += abs(a[i]-(b+i+1))
ba = b+1
ansa = 0
for i in range(n):
	ansa += abs(a[i]-(ba+i+1))
bb = b-1
ansb = 0
for i in range(n):
	ansb += abs(a[i]-(bb+i+1))
l = [ans,ansa,ansb]
print(min(l))

Submission status: Wrong Answer

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

def calc_sadness(points, b):
    return sum([abs(y - (b + x)) for x, y in points])

points = [(i+1, y) for i, y in enumerate(A)]

# y = x + b
# b = y - x
b_list = [y - x for x, y in points]
b_list.sort(reverse=True)


max_b = b_list[0]
min_b = b_list[-1]


def search(max_b, min_b):

    eval_max = calc_sadness(points, max_b)
    eval_min = calc_sadness(points, min_b)
    
    if max_b == min_b + 1:     # neighbors
        return min(eval_max, eval_min)
    
    mid_b = (max_b + min_b) // 2
    eval_mid = calc_sadness(points, mid_b)

    minimum = min(eval_max, eval_mid, eval_min)
    #print(eval_mid)

    if minimum == eval_max:
        return eval_max
    elif minimum == eval_min:
        return eval_min
    else:
        return min(search(max_b, mid_b), search(mid_b, min_b))


print(search(max_b, min_b))

Submission status: Wrong Answer

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

def calc_sadness(points, b):
    return sum([abs(y - (b + x)) for x, y in points])

points = [(i+1, y) for i, y in enumerate(A)]

# y = x + b
# b = y - x
b_list = [y - x for x, y in points]
b_list.sort(reverse=True)


max_b = b_list[0]
min_b = b_list[-1]


def search(max_b, min_b):

    eval_max = calc_sadness(points, max_b)
    eval_min = calc_sadness(points, min_b)
    
    if max_b == min_b + 1:     # neighbors
        return min(eval_max, eval_min)
    
    mid_b = (max_b + min_b) // 2
    eval_mid = calc_sadness(points, mid_b)

    minimum = min(eval_max, eval_mid, eval_min)
    #print(eval_mid)

    if minimum == eval_max:
        return eval_max
    elif minimum == eval_min:
        return eval_min
    else:
        return min(search(max_b, mid_b), search(mid_b, min_b))

if max_b == min_b:
    print(calc_sadness(points, min_b))
else:
    print(search(max_b, min_b))

Submission status: Wrong Answer

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

points = [(i+1, y) for i, y in enumerate(A)]

diff_list = [y - x for x, y in points]
diff_list.sort()

def eval_sadness(points, b):
    return sum([abs(y - (b + x)) for x, y in points])

max_b = diff_list[-1]
min_b = diff_list[0]
mid_b = (max_b + min_b)//2



def search(max_b, mid_b, min_b):
#    print("search", max_b, mid_b, min_b)
    
    eval_max = eval_sadness(points, max_b)
    eval_min = eval_sadness(points, min_b)
    eval_mid = eval_sadness(points, mid_b)

    minimum = min(eval_max, eval_mid, eval_min)
    #print(eval_mid)

    if minimum == eval_max:
        return eval_max
    elif minimum == eval_min:
        return eval_min
    elif max_b == min_b + 1:
        # no mid position
        return minimum
    else:
        return min(search(max_b, (max_b + mid_b)//2, mid_b), search(mid_b, (mid_b + min_b)//2, min_b))

if max_b == min_b:
    print(eval_sadness(points, min_b))
else:
    print(search(max_b, mid_b, min_b))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
B = [A[i]-i-1 for i in range(N)]
b = int(sum(B)/N)
print(min(abs(sum(B)-b*N),abs(sum(B)-b*N-b)))

Submission status: Wrong Answer

Solution code:
import math

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

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

b= math.floor(sum(a)/n)

ans=0

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

print(ans)

Submission status: Wrong Answer

Solution code:
#abc102c

n=int(raw_input())
a=map(int,raw_input().split())
b=[]
for i in xrange(n):
 b.append(abs(a[i]-i))
print sum(b)-min(b)*n

Submission status: Wrong Answer

Solution code:
import math
import collections

n = int(input())
array = [int(x) for x in input().split()]
array2 = [array[x]-(x+1) for x in range(n)]

b_ = sorted(array2)
b_ = b_[n//2]

res = sum([abs(x) for x in array2])
sad = sum(array2)

b = math.ceil(sad/n)
if sad >= 0:
    b *= -1
    b_ *= -1
tmp = sum([abs(abs(x) + b) for x in array2])
tmp2 = sum([abs(abs(x) + b_) for x in array2])


print(min(tmp, res, tmp2))

Submission status: Wrong Answer

Solution code:
from statistics import median
n = int(input())
a = [int(i) for i in input().split()]
b = []

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

m = median(b)

sum = 0
for i in range(n):
    sum += abs(a[i] - (m+i+1))

print(sum)

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

print(sum(B)-b*N)

Submission status: Wrong Answer

Solution code:
#coding:utf-8
n = int(input())
nums = list(map(int,input().split()))

nums = [num - i for i,num in enumerate(nums,1)]
nums.sort()

sums = [None for i in range(n)]
sums[0] = nums[0]
allv = sum(nums)
minv = nums[0] * (1 - n) - 2 * sums[0] + allv
for i in range(n-1):
    sums[i+1] = sums[i] + nums[i+1]
    for b in range(nums[i], nums[i+1]+1):
        p = b * (2*(i+1) - n) -2 * sums[i] + allv
        minv = min(minv,p)

print(minv)

Submission status: Wrong Answer

Solution code:
#coding:utf-8
n = int(input())
nums = list(map(int,input().split()))

nums = [num - i for i,num in enumerate(nums,1)]
nums.sort()

sums = [None for i in range(n)]
sums[0] = nums[0]
allv = sum(nums)
minv = nums[0] * (1 - n) - 2 * sums[0] + allv
for i in range(n-1):
    sums[i+1] = sums[i] + nums[i+1]
    if i >= n / 2:
        p = nums[i] * (2*(i+1) - n) -2 * sums[i] + allv
    else:
        p = nums[i+1] * (2*(i+1) - n) -2 * sums[i] + allv
    minv = min(minv,p)

print(minv)

Submission status: Wrong Answer

Solution code:
#coding:utf-8
n = int(input())
nums = list(map(int,input().split()))

nums = [num - i for i,num in enumerate(nums,1)]
nums.sort()

sums = [None for i in range(n)]
sums[0] = nums[0]
allv = sum(nums)
minv = nums[0] * (1 - n) - 2 * sums[0] + allv
for i in range(n-1):
    sums[i+1] = sums[i] + nums[i+1]
    p = nums[i] * (2*(i+1) - n) -2 * sums[i] + allv
    minv = min(minv,p)

print(minv)

Submission status: Wrong Answer

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

a = sorted([r - (i + 1) for i, r in enumerate(a)])
b = a[n // 2 - 1]

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

Submission status: Wrong Answer

Solution code:
import statistics

def calc_sad_param(b):
    global numbers
    sad_param = 0
    for i in range(len(numbers)):
        sad_param += abs(numbers[i] - (b + i))
    return sad_param

n = int(input())
numbers = list(map(int, input().split()))
b_list = [numbers[i] - i for i in range(n)]
print(calc_sad_param(statistics.median(b_list)))

Submission status: Wrong Answer

Solution code:
def calc_sad_param(b):
    global numbers
    sad_param = 0
    for i in range(len(numbers)):
        sad_param += abs(numbers[i] - (b + i))
    return sad_param

n = int(input())
numbers = list(map(int, input().split()))
sad_params = []
for b in range(-n, n):
    sad_params.append(calc_sad_param(b))

sad_params.sort()

print(sad_params[0])

Submission status: Wrong Answer

Solution code:
from sys import stdin
from statistics import median
n = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split()]
bi = [x -( i +1) for i,x in enumerate(a)]
b = median(bi)
s = 0
i = 0
while i < n:
    s += abs(bi[i] - b)
    i = i+1
print(s)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from statistics import median
n = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split()]
bi = [x -( i +1) for i,x in enumerate(a)]
b = median(bi)
s = 0
i = 0
while i < n:
    s += int(abs(bi[i] - b))
    i = i+1
print(s)

Submission status: Wrong Answer

Solution code:
import math
import sys

sys.setrecursionlimit(10**8)

N = int(input())

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

B = []
sum = 0

for i in range(N):
	aa = A[i] - i - 1
	B.append(aa)
	sum += aa
	
best1 = math.floor(sum/N)
best2 = math.ceil(sum/N)

ans1 = 0
ans2 = 0

for i in range(N):
	ans1 += abs(B[i]-best1)
	ans2 += abs(B[i]-best2)
	
print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
from sys import stdin
from statistics import median
n = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split()]
bi = [x - i +1 for i,x in enumerate(a)]
b = median(bi)
s = 0
i = 0
while i < n:
    s += int(abs(bi[i] - b))
    i = i+1
print(s)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from statistics import median
n = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split()]
bi = [x - i +1 for i,x in enumerate(a)]
b = median(bi)
s = 0
i = 0
while i < n:
    s += abs(bi[i] - b)
    i = i+1
print(s)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

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

ans = float("inf")
for b in range(-10, 11):

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

    ans = min(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

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

ans = float("inf")
for b in range(-3, 4):

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

    ans = min(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
# 整数列A 
# abs(A1-(b+1))+abs(A2-(b+2))+...+abs(An-(b+N))の最小値
# bは任意
# すなわち、その時のbを求めれば良い問題

# 結局、bを、Ai-iの中央値にすれば最適解。

def calcVal(b):
	# print(b)
	val = 0
	for n in range(N):
		val += abs(A[n]-(b+n+1))
		# print(A[n])
		# print(n)
		# print(val)
		# print(abs(A[n]-(b+n+1)))
		# print("")
	return val

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

M=[]

for i,a in enumerate(A):
	if a - (i+1) not in M:
		M.append( a - (i+1) )

M.sort()
lenM=len(M)

if lenM==1:
	ans=calcVal(M[0])

elif lenM==2:
	ans=min(calcVal(M[0]),calcVal(M[1]))


elif lenM%2==0:
	med1=lenM//2-1
	med2=lenM//2
	#print(M)
	ans=min(calcVal(M[med1]),calcVal(M[med2]),calcVal(0))

else:
	med=(lenM+1)//2
	# print(M)
	ans = min(calcVal(M[med]),calcVal(0))


print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(s) - i for i, s in enumerate(input().split(), 1)]
min_minus = 0
max_plus = 0
sum_minus_abs = 0
sum_plus = 0

for i in a:
    if i < 0:
        sum_minus_abs -= i
        if i < min_minus:
            min_minus = i
    else:
        sum_plus += i
        if max_plus < i:
            max_plus = i

if sum_minus_abs < sum_plus:
    m = max_plus
else:
    m = min_minus

r_sum = 0

for i in a:
    j = i - m

    if j < 0:
        j *= -1

    r_sum += j

r_sum_ = 0

for i in a:
    j = i

    if j < 0:
        j *= -1

    r_sum_ += j

if r_sum < r_sum_:
    print(r_sum)
else:
    print(r_sum_)

Submission status: Wrong Answer

Solution code:
import sys

def sum(l, b):
    s = 0
    for e in l:
        s += abs(e - b)
    return s

def main():
    N = int(raw_input())
    list_A = map(int, raw_input().split(' '))
    list_A = sorted([list_A[i]-(i+1) for i in range(N)])

    left = list_A[0]
    center = (list_A[0] + list_A[-1])/2
    right = list_A[-1]
    min_sum = sys.maxint

    while True:
        m1 = (left+center)/2
        m2 = (center+right)/2
        m1_sum = sum(list_A, m1)
        m2_sum = sum(list_A, m2)
        if m1_sum == m2_sum:
            print m1_sum
            break
        if m1_sum < m2_sum:
            right = m2
            center = (left + right)/2
        else :
            left = m1
            center = (left + right)/2
main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul  1 20:09:43 2018
ABC102C
@author: maezawa
"""
import math
n = int(input())
a = list(map(int, input().split()))


normsum = 0

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

b = math.floor(normsum/n)
ans = 0
for i in range(n):
    d = abs(a[i]-i-1-b)
    ans += d

#print(abssum, pm, normsum)
print(ans)

Submission status: Wrong Answer

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

for n in range(N):
    An[n] -= (n+1)

An.sort()

if (N-1) % 2 != 0:
    m = N//2 - 1
else:
    m = (N-1)//2

bf = -sum(An[0:m+1:]) + m*An[m]
af = sum(An[m::]) + (N-m)*An[m]
ans = bf + af
print(ans)