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

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

ave = sum(A) // N
ans1 = 0
ans2 = 0
for a in A:
    ans1 += abs(a - ave)
    ans2 += abs(a - (ave + 1))

print(min(ans1, ans2))

Submission status: Wrong Answer

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

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

ave = sum(A) // N
ans = 0
for a in A:
    ans += abs(a - ave)

print(ans)

Submission status: Wrong Answer

Solution code:
sousuu = int(input())
listnum = list(map(int, input().split()))
posinum = sousuu // 2 if sousuu % 2 == 0 else sousuu // 2 + 1
posival = sum(listnum) // len(listnum)
dst = 99999
for p in range(posinum - 3, posinum + 3):
    _dst = 0
    for i, s in enumerate(range(p - sousuu//2, p - sousuu//2 + sousuu)):
        _dst += abs(listnum[i] - s)
    if dst > _dst:
        dst = _dst
print(dst)

Submission status: Wrong Answer

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

def f(lst,b):
    res = 0
    for i in range(1,N+1):
        res += abs(lst[i-1]-(b+i))
    return res

ans = float('inf')
for b in range(-10**5,10**5+1):
    ans = min(ans, f(A,b))
    if ans==0:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline=sys.stdin.readline

N=int(readline())
A=list(map(int,readline().split()))
B=[0]*N
sumB=0
for i in range(N):
  B[i]=A[i]-(i+1)
  
B=sorted(B)
candi=[0]*2
candi[0]=B[N//2-1]
candi[1]=B[N//2]

ans=10**10
for c in candi:
  res=0
  for i in range(N):
    res+=abs(B[i]-c)
  if res<ans:
    ans=res
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline=sys.stdin.readline

N=int(readline())
A=list(map(int,readline().split()))
B=[0]*N
sumB=0
for i in range(N):
  B[i]=A[i]-(i+1)
  sumB+=B[i]
aveB=sumB//N

ans=10**10
for k in range(aveB-5,aveB+6):
  res=0
  for i in range(N):
    res+=abs(B[i]-k)
  if res<ans:
    ans=res
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline=sys.stdin.readline

N=int(readline())
A=list(map(int,readline().split()))
B=[0]*N
sumB=0
for i in range(N):
  B[i]=A[i]-(i+1)
  sumB+=B[i]
aveB=sumB//N

ans=10**10
for k in range(aveB-1,aveB+2):
  res=0
  for i in range(N):
    res+=abs(B[i]-k)
  if res<ans:
    ans=res
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
s = 0
X = []

for b in range(10000):
  for i in range(1,N+1):
    s += abs(A[i-1] - (b + i))
  X.append(s)

print(min(X))

Submission status: Wrong Answer

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

for i in range(1,N+1):

  s += abs(A[i-1] - (b + i))
           
print(s)

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) ]
idx = n//2
print( sum( [ abs(b-B[idx]) for b in B ] ) )

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) ]
idx = n//2-1 if n%2 == 0 else (n-1)//2
print( sum( [ abs(b-B[idx]) for b in B ] ) )

Submission status: Wrong Answer

Solution code:
import sys
import math
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
n=int(input())
A=list(map(int,input().split()))

def cost(x):
    ans=0
    for i in range(n):
        ans+= abs(A[i]-(x+i+1))
    return ans
def geti(x):
    ans=0
    for i in range(n):
        ans+= A[i]-(x+i+1)
    return ans
geta=geti(0)//n
answ=inf
for j in range(geta-5,geta+7):
    answ=min(answ,cost(j))
print(answ)

Submission status: Wrong Answer

Solution code:
import sys
import math
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
n=int(input())
A=list(map(int,input().split()))

def cost(x):
    ans=0
    for i in range(n):
        ans+= abs(A[i]-(x+i+1))
    return ans
def geti(x):
    ans=0
    for i in range(n):
        ans+= A[i]-(x+i+1)
    return ans
geta=geti(0)
answ=inf
for j in range(geta-30,geta+39):
    answ=min(answ,cost(j))
print(answ)

Submission status: Wrong Answer

Solution code:
import sys
import math
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
n=int(input())
A=list(map(int,input().split()))
ave=sum(A)//n
mid=math.ceil(n/2)
geta=ave-mid
def cost(x):
    ans=0
    for i in range(n):
        ans+= abs(A[i]-(x+i+1))
    return ans
answ=inf
for j in range(geta-5,geta+7):
    answ=min(answ,cost(j))
print(answ)

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([A[i]-i-b-1 for i in range(N)]))

Submission status: Wrong Answer

Solution code:
"""
102 C
"""

import math

def read_input():
    n = int(input())
    alist = list(map(int, input().split()))

    return n, alist


def sum_abs(alist, b):
    return sum([abs(a - b) for a in alist])


def submit():
    n, alist = read_input()

    alist = [a - (i + 1) for i, a in enumerate(alist)]
    t = sum(alist) / n
    b_min, b_max = math.floor(t), math.ceil(t)

    print(min(sum_abs(alist, b_min), sum_abs(alist, b_max)))


if __name__ == "__main__":
    submit()

Submission status: Wrong Answer

Solution code:
"""
102 C
"""

import math

def read_input():
    n = int(input())
    alist = list(map(int, input().split()))

    return n, alist


def sum_abs(alist, b):
    return sum([abs(a - b) for a in alist])


def submit():
    n, alist = read_input()

    alist = [a - (i + 1) for i, a in enumerate(alist)]
    asum = sum(alist)

    b_min = math.floor(asum // n)
    b_max = math.floor(asum // n + 1)

    print(min(sum_abs(alist, b_min), sum_abs(alist, b_max)))


if __name__ == "__main__":
    submit()

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
N = int(input())
A = list(map(int,input().split()))
B = deepcopy(A)
B.sort()

b = 0
if N%2 == 0:
    b = (B[N//2-1]+B[N//2])//2 - N//2
else:
    b = B[N//2] - N//2 - 1
##print(b)
ans = 0
for i in range(N):
    ans += abs(A[i]-(b+i+1))
ans2 = 0
b += 1
for i in range(N):
    ans2 += abs(A[i]-(b+i+1))
ans = min(ans,ans2)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

b = 0
if N%2 == 0:
    b = (A[N//2-1]+A[N//2])//2 - N//2 + 1
else:
    b = A[N//2] - N//2 - 1
##print(b)
ans = 0
for i in range(N):
    ans += abs(A[i]-(b+i+1))
ans2 = 0
b += 1
for i in range(N):
    ans2 += abs(A[i]-(b+i+1))
ans = min(ans,ans2)
print(ans)

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

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

b = 0
if N%2 == 0:
    b = int((A[N//2-1]+A[N//2])/2 - (N//2-1+N//2)/2)
else:
    b = A[N//2] - N//2 - 1
##print(b)
ans = 0
for i in range(N):
    ans += abs(A[i]-(b+i+1))
b += 1
ans2 = 0
for i in range(N):
    ans2 += abs(A[i]-(b+i+1))
ans = min(ans,ans2)
print(int(ans))

Submission status: Wrong Answer

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

b = 0
if N%2 == 0:
    b = int((A[N//2-1]+A[N//2])/2 - (N//2-1+N//2)/2)
else:
    b = A[N//2-1] - N//2 - 1
##print(b)
ans = 0
for i in range(N):
    ans += abs(A[i]-(b+i+1))
b += 1
ans2 = 0
for i in range(N):
    ans2 += abs(A[i]-(b+i+1))
ans = min(ans,ans2)
print(int(ans))

Submission status: Wrong Answer

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

b = 0
if N%2 == 0:
    b = int((A[N//2]+A[N//2+1])/2 - (N//2 - 0.5))
else:
    b = A[N//2] - N//2 - 1
ans = 0
for i in range(N):
    ans += abs(A[i]-(b+i+1))
b += 1
ans2 = 0
for i in range(N):
    ans2 += abs(A[i]-(b+i+1))
ans = min(ans,ans2)
print(int(ans))

Submission status: Wrong Answer

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

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

print(int(ans))

Submission status: Wrong Answer

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

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

print(int(ans))

Submission status: Wrong Answer

Solution code:
from math import ceil, floor

n = int(input())
a = [int(ai) - i - 1 for i, ai in enumerate(input().split())]
b = sum(a) / n
print(min(sum(abs(i - bk) for i in a) for bk in [ceil(b), floor(b)]))

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc102/tasks/arc100_a
import sys
read = sys.stdin.readline


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


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


class cumsum1d:
    def __init__(self, ls: list):
        '''
        1次元リストを受け取る
        '''
        from itertools import accumulate
        self.ls_accum = [0] + list(accumulate(ls))

    def total(self, i, j):
        # もとの配列lsにおける[i,j)の中合計
        return self.ls_accum[j] - self.ls_accum[i]


N = read_a_int()
A = read_ints()
if N == 1:
    print(0)
    exit()
B = [a - i for a, i in zip(A, range(1, N + 1))]
B.sort()

# 絶対値を区切る境目はどこがよいか？
B_cum = cumsum1d(B)
ans = 10**11
for k in range(1, N):
    tmp_sum = -B_cum.total(0, k) + B_cum.total(k, N)
    add = min((2 * k - N) * B[k - 1], (2 * k - N) * B[k])
    ans = min(ans, tmp_sum + add)


print(ans)
# 式ごちゃごちゃやったけど絶対楽な方法がある。
# 明日復習

Submission status: Wrong Answer

Solution code:
import bisect

a=[]
def asff(b,a,n):
    asum=0
    for j in range(n):
        asum=asum+abs(a[j]-(b+j+1))
    return asum    

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

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

s=[a[0]]
for i in range(1,n):
    s.append(s[i-1]+a[i])
    
amin=min(a)-n
amax=max(a)+n

  
asmin=amax*n
m0=0
for b in range(amin,amax+1):
    m=bisect.bisect(a,b)
    asf=(2*m-n)*b+s[n-1]-2*s[m-1]
#    print("b",b,"m",m,"asf",asf)
    if asf<asmin:
        asmin=asf

print(asmin)

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)

m = sum(b)/n
m1 = int(m)
m2 = int(m)-1
res1,res2=0,0
for i in range(n):
    res1+=abs(b[i]-m1)
    res2+=abs(b[i]-m2)
print(min(res1,res2))

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc102/tasks/arc100_a
import sys
read = sys.stdin.readline


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


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


class cumsum1d:
    def __init__(self, ls: list):
        '''
        1次元リストを受け取る
        '''
        from itertools import accumulate
        self.ls_accum = [0] + list(accumulate(ls))

    def total(self, i, j):
        # もとの配列lsにおける[i,j)の中合計
        return self.ls_accum[j] - self.ls_accum[i]


N = read_a_int()
A = read_ints()
B = [a - i for a, i in zip(A, range(1, N + 1))]
B.sort()

# 絶対値を区切る境目はどこがよいか？
B_cum = cumsum1d(B)
ans = 10**11
for k in range(1, N):
    tmp_sum = -B_cum.total(0, k) + B_cum.total(k, N)
    add = min((2 * k - N) * B[k - 1], (2 * k - N) * B[k])
    ans = min(ans, tmp_sum + add)


print(ans)
# 式ごちゃごちゃやったけど絶対楽な方法がある。
# 明日復習

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc102/tasks/arc100_a
import sys
read = sys.stdin.readline


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


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


N = read_a_int()
A = read_ints()
B = [a - i for a, i in zip(A, range(1, N + 1))]

mu = sum(B) // N
ans = 0
ans1 = 0
for b in B:
    ans += abs(b - mu)
    ans1 += abs(b - mu - 1)

print(min(ans, ans1))

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc102/tasks/arc100_a
import sys
read = sys.stdin.readline


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


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


N = read_a_int()
A = read_ints()
B = [a - i for a, i in zip(A, range(1, N + 1))]

mu = sum(B) // N
ans = 0
for b in B:
    ans += abs(b - mu)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(N):
        A[i] -= (i + 1)
    x = sum(A)//N
    xr = sum(abs(i - x) for i in A)
    xr2 = sum(abs(i - (x + 1)) for i in A)
    xr3 = sum(abs(i - (x - 1)) for i in A)
    return min(xr, xr2, xr3)
print(main())

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(N):
        A[i] -= (i + 1)
    x = sum(A)//N
    xr = sum(abs(i - x) for i in A)
    xr2 = sum(abs(i - (x + 1)) for i in A)
    return min(xr, xr2)
print(main())

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    t = sum(a - i for i, a in enumerate(A, 1))
    t = t // N
    print(min(sum(abs(a - (t + i)) for i, a in enumerate(A, 1)),
              sum(abs(a - (t + i + 1)) for i, a in enumerate(A, 1))))
            

main()

Submission status: Wrong Answer

Solution code:
N = int(input())
An = [int(s) - i -1 for i, s in enumerate(input().split())]
if N % 2 == 0:
  medians = [(An[N//2] + An[N//2 + 1] + 1)//2, (An[N//2] + An[N//2 + 1])//2] 
else:
  medians = [An[N//2]]
min_sum = 1e20
for median in medians:
  sum_ = 0
  for a in An:
    sum_ += abs(a - median)
  min_sum = min(min_sum, sum_)
print(min_sum)

Submission status: Wrong Answer

Solution code:
N = int(input())
An = [int(s) - i -1 for i, s in enumerate(input().split())]
if N % 2 == 0:
  median = (An[N//2] + An[N//2 + 1] + 1)//2
else:
  median = An[N//2]
sum_ = 0
for a in An:
  sum_ += abs(a - median)
print(sum_)

Submission status: Wrong Answer

Solution code:
a=[]
def asff(b,a,n):
    asum=0
    for j in range(n):
        asum=asum+abs(a[j]-(b+j+1))
    return asum    

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

amin=min(a)-n
amax=max(a)+n

#asmin=amax*n
#for i in range(amin,amax+1):
#    asf=asff(i,a,n)
#    if asf<asmin:
#        asmin=asf

ast=min(a)-n
aed=max(a)+n
asst=asff(ast,a,n)
ased=asff(aed,a,n)

icnt=0
while ast+1<=aed:
    amed=(ast+aed)//2
    if asst>ased:
        ast=amed
        asst=asff(ast,a,n)
    else:
        aed=amed
        ased=asff(aed,a,n)
    icnt=icnt+1
    if icnt>100:
        break              
#    print(ast,aed,asst,ased)    
#print(ased)

imin=10**15
for i in range(ast-5,aed+5):
    asi=asff(i,a,n)
    if asi<imin:
        imin=asi
print(imin)

Submission status: Wrong Answer

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

if N % 2 != 0:
    b = B[(N+1)//2 - 1]
    print(b)
    ans = 0
    for i in range(len(B)):
        ans += abs(B[i] - b)
else:
    b1 = B[N//2 - 1]
    ans1 = 0
    for i in range(len(B)):
        ans1 += abs(B[i] - b1)
    b2 = B[N//2]
    ans2 = 0
    for i in range(len(B)):
        ans2 += abs(B[i] - b2)
    ans = min(ans1, ans2)
print(ans)

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
b = sum(A) // N
b1 = b + 1
ans = 0
ans1 = 0
for i in range(N):
  ans += abs(A[i] - b)
  ans1 += abs(A[i] - b1)
print(min(ans,ans1))

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

Submission status: Wrong Answer

Solution code:
a=[]
def asff(b,a,n):
    asum=0
    for j in range(n):
        asum=asum+abs(a[j]-(b+j+1))
    return asum    

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

amin=min(a)-n
amax=max(a)+n

#asmin=amax*n
#for i in range(amin,amax+1):
#    asf=asff(i,a,n)
#    if asf<asmin:
#        asmin=asf

ast=min(a)-n
aed=max(a)+n
asst=asff(ast,a,n)
ased=asff(aed,a,n)

icnt=0
while ast+1<=aed:    
    amed=(ast+aed)//2
    if asst>ased:
        ast=amed
        asst=asff(ast,a,n)
    else:
        aed=amed
        ased=asff(aed,a,n)
    icnt=icnt+1
    if icnt>100:
        break              
    
print(ased)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_list = [int(item)-(index+1) for index, item in enumerate(input().split())]

b = sum(A_list)//len(A_list)

ans = 0
for i in A_list:
  ans += abs(i-b)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = sorted([x-i-1 for x,i in zip(a,range(n))])
print(sum([x-b[n//2] for x in b]))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [x-i-1 for x,i in zip(a,range(n))]
print(sum([x-b[n//2] for x in b]))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [x-i-1 for x,i in zip(a,range(n))]
ans = sum([abs(x) for x in b])
ngo = 0
val = 0
for i in list(set(b)):
    tmp = abs(b.count(i)*i)
    if ngo < tmp:
        ngo = tmp
        val = i
print(sum([abs(x-val) for x in b]))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
for i in range(N):
    A[i] -= i+1
b = A[N//2]
answer = 0
for i in range(N):
    answer += abs(A[i] - b)

print(answer)

Submission status: Wrong Answer

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

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

total = sum(A)
b1,b2 = total//N,math.ceil(total/N)
sad1,sad2 = 0,0
for i in range(N):
    sad1 += abs(A[i]-b1)
    sad2 += abs(A[i]-b2)

print(min(sad1,sad2))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
def abs(x):
    if x>=0:
        return x
    else:
        return x*(-1)
B=[]
for i in range(N):
  B.append(A[i]-i-1)
B.sort()
if N%2==0:
  b=(B[N//2]+B[N//2-1])//2
else:
  b=B[N//2-1]
sad=0
for j in range(N):
  sad=sad+abs(B[j]-b)
print(sad)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
def quick_sort(a):
    if len(a) <= 1:
        return a
    else:
        b = []
        c = []
        for i in range(1, len(a)):
            if a[i] < a[0]:
                b.append(a[i])
            else:
                c.append(a[i])
        return quick_sort(b)+[a[0]]+quick_sort(c)
def abs(x):
    if x>=0:
        return x
    else:
        return x*(-1)
B=[0]*N
for j in range(N):
    B[j]=A[j]-j-1
bh=quick_sort(B)[0]
bt=quick_sort(B)[N-1]
def sad(A,b):
  s=[0]*(len(A))
  for m in range(len(A)):
    s[m]=abs(A[m]-(b+m+1))
  return s
def sum(A):
  sum=0
  for n in range(len(A)):
    sum=sum+A[n]
  return sum
l=[]
for o in range(bh-5,bt+5):
  l.append(sum(sad(A,o)))

Submission status: Wrong Answer

Solution code:
import collections
n=int(input())
a=list(map(int,input().split() ))
absa=[]
za=[]
for i in range(n):
    za.append(a[i]-(i+1))
#print(za)
#print(sum(za))

z=sum(za)
#print(z)
c = collections.Counter(za)
if z<0:
    if (z/n)+z//n>=0.5:
        b=z//n+1
    else:
        b=z//n
else:
    if (z/n)-z//n>=0.5:
        b=z//n-1
    else:
        b=z//n
#print(b)
for i in range(n):
    absa.append(abs(a[i]-(b+(i+1))))
#print(absa)
print(sum(absa))

Submission status: Wrong Answer

Solution code:
import collections
n=int(input())
a=list(map(int,input().split() ))
absa=[]
za=[]
for i in range(n):
    za.append(a[i]-(i+1))
#print(za)
#print(sum(za))
z=sum(za)
#print(z)
c = collections.Counter(za)
if (z/n)+z//n>=0.5:
    b=z//n+1
else:
    b=z//n
#print(b)
for i in range(n):
    absa.append(abs(a[i]-(b+(i+1))))
#print(absa)
print(sum(absa))

Submission status: Wrong Answer

Solution code:
import collections
n=int(input())

a=list(map(int,input().split() ))
absa=[]
za=[]

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


c = collections.Counter(za)

if c.most_common()[0][1]==1:
    b=0
else:
    b=c.most_common()[0][0]

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



#print(absa)
print(sum(absa))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
cur=0
ans=10000
b=-1
while(True):
    b+=1
    for i in range(n):
        cur+=abs(a[i]-(b+(i+1)))
    if(ans>cur):
        ans=cur
    else:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
from math import floor

def solve(n, A):
    A.sort()
    B = [a - (i + 1) for i, a in enumerate(sorted(A))]
    b = B[n // 2]
    ret = sum(abs(a - (b + i + 1)) for i, a in enumerate(A))
    if n % 2 == 0:
        b = B[n // 2 + 1]
        tmp = sum(abs(a - (b + i + 1)) for i, a in enumerate(A))
        if tmp < ret:
            ret = tmp
    return ret

_n = int(input())
_A = list(map(int, input().split()))
print(solve(_n, _A))

Submission status: Wrong Answer

Solution code:
from math import floor

def solve(n, A):
    A.sort()
    b = [a - (i + 1) for i, a in enumerate(A)][n // 2]
    return sum(abs(a - (b + i + 1)) for i, a in enumerate(A))

_n = int(input())
_A = list(map(int, input().split()))
print(solve(_n, _A))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
ave=(sum(A)-(N*(N+1))//2)//N

ans=10**20
for dx in [-1,0,1]:
    temp=0
    for i in range(N):
        temp+=abs(A[i]-(ave+dx+i+1))
    ans=min(ans,temp)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
ave=(sum(A)-(N*(N-1)//2))//N

ans=10**20
for dx in [-1,0,1]:
    temp=0
    for i in range(N):
        temp+=abs(A[i]-(ave+dx+i+1))
    ans=min(ans,temp)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
B = [a-i-1 for i, a in enumerate(A)]
m = B[n//2]
print(sum(abs(b-m) for b in 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
  

A.sort()

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

Submission status: Wrong Answer

Solution code:

import numpy as np
import sys
sys.setrecursionlimit(100000)



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



directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

N=int(input())
A=np.array(acinput())
s=A-range(1,N+1)

s=sorted(s)
m=np.median(s)

res=0
for i in range(N):
    res+=np.abs(A[i]-m-(i+1))

print(res)

Submission status: Wrong Answer

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

A = [a - (i + 1) for i, a in enumerate(A)]

b1 = sum(A) // N
b2 = b1 + 1
tmp1, tmp2 = 0, 0

for a in A:
  tmp1 += abs(a - b1)
  tmp2 += abs(a - b2)
  
print(min(tmp1, tmp2))

Submission status: Wrong Answer

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

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

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

fans = 0
cans = 0
f = math.floor(sum(A)/N)
c = math.ceil(sum(A)/N)
for a in A:
    fans += abs(a-f)
    cans += abs(a-c)

print(min(fans, cans))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from math import floor, ceil

def solve(n, A):
    b1 = floor(sum(a - (i + 1) for i, a in enumerate(A)) / n)
    b2 = ceil(sum(a - (i + 1) for i, a in enumerate(A)) / n)
    return min(
        sum(abs(a - (b1 + i + 1)) for i, a in enumerate(A)),
        sum(abs(a - (b2 + i + 1)) for i, a in enumerate(A))
    )

_n = int(input())
_A = list(map(int, input().split()))
print(solve(_n, _A))

Submission status: Wrong Answer

Solution code:
from math import floor, ceil

def solve(n, A):
    b = sum(a - (i + 1) for i, a in enumerate(A)) / n
    b = floor(b) if b > 0 else ceil(b)
    return sum(abs(a - (b + i + 1)) for i, a in enumerate(A))

_n = int(input())
_A = list(map(int, input().split()))
print(solve(_n, _A))

Submission status: Wrong Answer

Solution code:
from math import floor

def solve(n, A):
    b = floor(sum(a - (i + 1) for i, a in enumerate(A)) / n)
    return sum(abs(a - (b + i + 1)) for i, a in enumerate(A))

_n = int(input())
_A = list(map(int, input().split()))
print(solve(_n, _A))

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import Counter
n = int(input())
l = np.array([int(i) for i in input().split()])
l2 = np.array([i for i in range(1,n+1)])

c = Counter(l-l2)
mode = c.most_common()[0][0] if c.most_common()[0][1] != 1 else 0

print(abs((l- (l2 + mode))).sum())

Submission status: Wrong Answer

Solution code:
def binary_search(a, left, right):
    ll,rr = 0, 0
    for i in a:
        rr += abs(right - i)
        ll += abs(left - i)
    cost = min(ll,rr)
    while left < right:
        mid = (left+right)//2
        cost = 0
        for i in a:
            cost += abs(mid - i)
        rd,ld = abs(rr - cost), abs(ll - cost)
        if rd == ld:
            return cost
        elif rd >= ld:
            right = mid
            rr = cost
        else:
            left = mid
            ll = cost
        # print(left, right , ll, rr, cost)
    return min(cost, ll, rr)


n = int(input())
a = [ int(b)-(i+1) for i,b in enumerate(input().split())]
tmp = 0
t = binary_search(a, min(a), max(a))
print(t)

Submission status: Wrong Answer

Solution code:
def binary_search(a, left, right):
    ll,rr = 0, 0
    for i in a:
        rr += abs(right - i)
        ll += abs(left - i)
    cost = min(ll,rr)
    while left + 1 < right:
        mid = (left+right)//2
        cost = 0
        for i in a:
            cost += abs(mid - i)
        rd,ld = abs(rr - cost), abs(ll - cost) 
        if rd > ld:
            right = mid
            rr = cost
        else:
            left = mid
            ll = cost
    # print(left, right , ll, rr)
    return min(cost, rr, ll)


n = int(input())
a = [ int(b)-i-1 for i,b in enumerate(input().split())]
print(binary_search(a, min(a), max(a)))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
from collections import defaultdict
diff=defaultdict(int)
for i in range(N):
  diff[A[i]-(i+1)]+=1
b=sorted(diff.items(),key=lambda x:x[1])[-1][0]
ans=0
for i in range(N):
  ans+=abs(A[i]-(b+i+1))
print(ans)

Submission status: Wrong Answer

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

B = []

for b in range(-100,100):
    cnt = 0
    for i in range(N):
        cnt += abs(A[i]-(b + i + 1))
        #print(cnt)
    B.append(cnt)

print(min(B))

Submission status: Wrong Answer

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

cnt = 0
B = []

for b in range(100):
    for i in range(N):
        cnt += abs(A[i]-(b + i + 1))
    B.append(cnt)
print(min(B))