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()))
b = [a[i] - (i+1) for i in range(n)]
#sa = sum(a)
b.sort()
#print(b)
ans = 10 ** 10
for j in range(3):
    bi = b[(n//2+j)%n]
    s = 0
    for i in range(n):
        s += abs(b[i] - bi)
    #print(s)
    ans = min(ans, s)
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)]
#sa = sum(a)
b.sort()
#print(b)
ans = 10 ** 10
for j in range(3):
    bi = b[(n - j)//2]
    s = 0
    for i in range(n):
        s += abs(b[i] - bi)
    #print(s)
    ans = min(ans, s)
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)]
#sa = sum(a)
b.sort()
#print(b)
ans = 10 ** 10
for j in range(3):
    bi = b[(n - j)//2]
    s = 0
    for i in range(n):
        s += b[i] - bi
    #print(s)
    ans = min(ans, s)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int , input().split()))
n = len(a)
#sa = sum(a)
sa = 0
for i in range(len(a)):
    sa += a[i] - (i + 1)
b = sa // n
ans = 10 ** 10
for bi in range(b-2, b+2):
    s = 0
    for i in range(len(a)):
        s += abs(a[i] - (bi + i + 1))
    ans = min(ans, s)
print(ans)
"""
sn = (n * (n+1)) // 2
print(sa, sn, (sa-sn)/n, (sa+sn)/n, sa/n)
prev = 0
for b in range(170, 180):
    s = 0
    for i in range(len(a)):
        s += abs(a[i] - (b + i + 1))
    print(b, s, s - prev)
    prev = s
"""

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int , input().split()))
n = len(a)
#sa = sum(a)
sa = 0
for i in range(len(a)):
    sa += a[i] - (i + 1)
b = sa // n
ans = 10 ** 10
for bi in range(b, b+3):
    s = 0
    for i in range(len(a)):
        s += abs(a[i] - (bi + i + 1))
    ans = min(ans, s)
print(ans)
"""
sn = (n * (n+1)) // 2
print(sa, sn, (sa-sn)/n, (sa+sn)/n, sa/n)
prev = 0
for b in range(170, 180):
    s = 0
    for i in range(len(a)):
        s += abs(a[i] - (b + i + 1))
    print(b, s, s - prev)
    prev = s
"""

Submission status: Wrong Answer

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()
a = nl()

s = []

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

avg = sorted(s)[n//2]

dir = 1

last = 0

def getErr(num):
  err = 0
  for i in range(n):
    err += abs(s[i] - num)
  return err

mn = 10**10
for i in range(avg-1000,avg+1000):
  mn = min(mn, getErr(i))

print(mn)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
na = [0]*n
for i in range(n):
    na[i] = a[i]-(i+1)
mid = sum(na)//n
mid1 = mid+1
ans = 0
ans1 = 0
for i in range(n):
    ans += abs(na[i]-mid)
    ans1 += abs(na[i]+mid1)
print(min(ans, ans1))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = IL()

AA = [A[i]-i for i in range(N)]
sumAA = sum(AA)
avehiku = sumAA//N
avetaka = -(-sumAA//N)


AAhiku = [abs(AA[i]-avehiku)  for i in range(N)]
AAtaka = [abs(AA[i]-avetaka)  for i in range(N)]
print(min(sum(AAhiku),sum(AAtaka)))

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = IL()

AA = [A[i]-i-1 for i in range(N)]
sumAA = sum(AA)
avehiku = sumAA//N
avetaka = -(-sumAA//N)


AAhiku = [abs(AA[i]-avehiku)  for i in range(N)]
AAtaka = [abs(AA[i]-avetaka)  for i in range(N)]
print(min(sum(AAhiku),sum(AAtaka)))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array(lr(), dtype=np.int32)
A -= np.arange(1, N+1)
answer = np.abs(A - np.median(A)).sum()
print(answer)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

n = I()
A = LI()
B = [A[i]-i-1 for i in range(n)]
mid = B[n//2]
mid2 = B[(n-1)//2]
def sad(b, n):
    ret = 0
    for i in range(n):
        ret += abs(B[i]-b)
    return ret

ans = min(sad(mid, n), sad(mid2, n))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

n = I()
A = LI()
B = [A[i]-i-1 for i in range(n)]
mid = B[n//2]
def sad(b, n):
    ret = 0
    for i in range(n):
        ret += abs(B[i]-b)
    return ret

ans = INF
for i in range(mid-50, mid+50):
    ans = min(ans, sad(i, n))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

n = I()
A = LI()
B = [A[i]-i-1 for i in range(n)]
mid = round(sum(B)/len(B))
def sad(b, n):
    ret = 0
    for i in range(n):
        ret += abs(A[i]-(b+i+1))
    return ret

ans = INF
for i in range(mid-50, mid+50):
    ans = min(ans, sad(i, n))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
Min = 10**9+1
for i in range(1,n):
    a[i] -= i
sum = 0
print(a)
a.sort()
base = 0
for i in range(n):
    if a[i] != base:
        base = a[i]
        sum = 0
        for j in range(n):
            sum += abs(a[j]-base)
        Min = min(sum,Min)
print(Min)

Submission status: Wrong Answer

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A = [A[i] - i - 1 for i in range(N)]
    # print(A)
    diff = math.floor(sum(A) / N)
    diff2 = math.ceil(sum(A) / N)
    # print(sum(A) / N)
    ans = sum([abs(a-diff) for a in A])
    ans2 = sum([abs(a-diff2) for a in A])
    print(min(ans,ans2))
    # print([abs(a-diff) for a in A])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A = [A[i] - i - 1 for i in range(N)]
    # print(A)
    diff = math.floor(sum(A) / N)
    # print(sum(A) / N)
    print(sum([abs(a-diff) for a in A]))
    # print([abs(a-diff) for a in A])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A = [A[i] - i - 1 for i in range(N)]
    diff = sum(A) // N
    print(sum([abs(a-diff) for a in A]))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np


def main():
  readline = sys.stdin.readline
  
  n = int(readline().rstrip())
  a = np.array(
    tuple(int(a_i) for a_i in readline().rstrip().split())
  )
  
  b = int(np.median(a - np.arange(1, n + 1)))
  
  print(b)
  

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil, floor

n = int(input())
a_list = [int(x) for x in input().split()]

temp_list = [a - i for a, i in zip(a_list, range(1, n + 1))]
avg = sum(temp_list) / n

def calc(num):
    return sum([abs(temp - num) for temp in temp_list])

print(min(calc(floor(avg)), calc(ceil(avg))))

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
A_num = list(map(int, input().split()))
A_num.sort()

if N % 2 == 0:
    b1 = int(A_num[int(N / 2)-1] - (N + 1) / 2)
    b2 = int(A_num[int(N / 2)-1] - (N + 1) / 2) + 1
else:
    b1 = int((A_num[int((N+1) / 2)-1]+A_num[int((N-1) / 2)-1])/2 - (N + 1) / 2)
    b2 = int((A_num[int((N + 1) / 2)-1] + A_num[int((N - 1) / 2)-1]) / 2 - (N + 1) / 2)+1

sum1 = 0
sum2 = 0
for i in range(N):
    sum1 = sum1 + math.fabs(A_num[i]-(i+1)-b1)
    sum2 = sum2 + math.fabs(A_num[i] - (i + 1) - b2)

print(int(min(sum1,sum2)))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
res = [int()]*n
for i in range(n):
    res[i] = a[i] - i - 1
res.sort()
x = sum(res)/n
x = int(x)
if x < 0:
    x -= 1
elif x > 0:
    x += 1
"""
if n % 2 == 0:
    x = res[int(n/2)] + res[int(n/2)-1]
else:
    x = res[int(n/2)]
"""
for j in range(n):
    res[j] = abs(res[j] - x)
print(sum(res))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
res = [int()]*n
for i in range(n):
    res[i] = a[i] - i - 1
res.sort()
x = sum(res)/n
x = int(x)
if x < 0:
    x -= 1
"""
if n % 2 == 0:
    x = res[int(n/2)] + res[int(n/2)-1]
else:
    x = res[int(n/2)]
"""
for j in range(n):
    res[j] = abs(res[j] - x)
print(sum(res))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
alta = []
for i in range(N):
    alta.append(A[i] - (i + 1))
    
def f(x):
    sum = 0
    for i in alta:
        sum += abs(x - i)
    return sum

# 極地があるので三分探索使う
left, right = 0, max(alta)
# 答えが整数になる場合このrightとleftの幅を3未満にするとバグる
while abs(right - left) > 3:
    mid1 = (right * 2 + left) // 3 + 1
    mid2 = (right + left * 2) // 3
    if f(mid1) >= f(mid2):
        # 上限を下げる（最小値をとるxはもうちょい下めの数だな）
        right = mid1
    else:
        # 下限を上げる（最小値をとるxはもうちょい上めの数だな）
        left = mid2
ans = float('inf')
for i in range(left, right + 1):
    ans = min(ans, f(i))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
alta = []
for i in range(N):
    alta.append(A[i] - (i + 1))
plus = min(alta)
for i in range(N):
    alta[i] -= plus

def f(x):
    sum = 0
    for i in alta:
        sum += abs(x - i)
    return sum

left, right = 0, max(alta)
while abs(right - left) > 1:
    mid1 = (right * 2 + left) / 3
    mid2 = (right + left * 2) / 3
    if f(mid1) >= f(mid2):
        # 上限を下げる（最小値をとるxはもうちょい下めの数だな）
        right = mid1
    else:
        # 下限を上げる（最小値をとるxはもうちょい上めの数だな）
        left = mid2
print(min(f(0), f(int(left)), f(int(left) + 1), f(int(left) + 2), f(max(alta))))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
alta = []
for i in range(N):
    alta.append(A[i] - (i + 1))
plus = min(alta)
for i in range(N):
    alta[i] -= plus

def f(x):
    sum = 0
    for i in alta:
        sum += abs(x - i)
    return sum

left, right = 0, max(alta)
while abs(right - left) > 1:
    mid1 = (right * 2 + left) / 3
    mid2 = (right + left * 2) / 3
    if f(mid1) >= f(mid2):
        # 上限を下げる（最小値をとるxはもうちょい下めの数だな）
        right = mid1
    else:
        # 下限を上げる（最小値をとるxはもうちょい上めの数だな）
        left = mid2
print(min(f(int(left)), f(int(left) + 1), f(int(left) + 2)))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

N = ii()
A = li()

#max_a = max(A)
hosei = max(A) - N
hosei_2 = (-1) * hosei
ans = 0
ans_2 = 0
for i in range(N):
    ans += abs(hosei+i+1 - A[i])
    ans_2 += abs(hosei_2+i+1 - A[i])

print(min(ans, ans_2))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

N = ii()
A = li()

#max_a = max(A)
hosei = max(A) - N
hosei_2 = (-1) * hosei
ans = 0
ans_2 = 0
for i in range(N):
    ans += abs(hosei+i+1 - A[i])
    ans_2 = abs(hosei_2+i+1 - A[i])

print(min(ans, ans_2))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

N = ii()
A = li()

#max_a = max(A)
hosei = max(A) - N
ans = 0
for i in range(N):
    ans += abs(hosei+i+1 - A[i])

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import collections

N = int(input())
A = list(map(int, input().split()))
ans = 10**18
dists_A2i = []

for i in range(1, N+1):
    dist_A2i = A[i-1] - i
    dists_A2i.append(dist_A2i)

c = collections.Counter(dists_A2i)

max_c_list = [key for key, value in c.items() if value == max(c.values())]

dists_A2i = np.array(dists_A2i)

print(dists_A2i)
print(max_c_list)

for max_c in max_c_list:
    check_dists_A2i = abs(dists_A2i - max_c)
    ans = min(ans, sum(check_dists_A2i))

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_plus = sum(A)//n
b_minus = -(-sum(A)//n)

ans_plus = 0
ans_minus = 0

for i in range(n):
    ans_plus += abs(A[i]-b_plus)
    ans_minus += abs(A[i]-b_minus)

print(min(ans_plus, ans_minus))

Submission status: Wrong Answer

Solution code:
class SplayNode:
    """Splay木のノードを定義
    メンバ変数: 値、サイズ、親へのポインタ、左右の子へのポインタ
    """
    def __init__(self, val):
        self.val = val
        self.size = 1
        self.parent, self.right, self.left = None, None, None


class SplayTree:
    """Splay木を定義"""
    def __init__(self):
        self.root = None

    def __getitem__(self, ind: int):  # O(logN)
        return self.get_ptr(ind, self.root).val
        
    def __setitem__(self, ind: int, val):  # O(logN)
        ptr = self.get_ptr(ind, self.root)
        ptr.val = val

    def __len__(self):  # O(1)
        return self.root.size if self.root is not None else 0

    def update(self, ptr):
        """部分木の情報を更新する"""
        ptr.size = 1
        if ptr.left is not None:
            ptr.size += ptr.left.size
        if ptr.right is not None:
            ptr.size += ptr.right.size

    def state(self, ptr):
        """スプレー操作を行うときの状況判定
        親が存在しない: 0
        左の兄弟が存在する: 1
        右の兄弟が存在する: -1
        """
        if ptr.parent is None:
            return 0
        if ptr.parent.left == ptr:
            return 1
        if ptr.parent.right == ptr:
            return -1

    def splay(self, ptr):
        """ptrが根になるようにスプレー操作を行う"""
        while self.state(ptr) != 0:
            if self.state(ptr.parent) == 0:
                # zigステップ
                self.rotate(ptr)
            elif self.state(ptr) == self.state(ptr.parent):
                # zig-zigステップ
                self.rotate(ptr.parent)
                self.rotate(ptr)
            else:
                # zig-zagステップ
                self.rotate(ptr)
                self.rotate(ptr)
        self.root = ptr

    def rotate(self, ptr):
        """木の回転を行う"""
        p = ptr.parent
        pp = p.parent
        if p.left == ptr:
            c = ptr.right
            ptr.right = p
            p.left = c
        else:
            c = ptr.left
            ptr.left = p
            p.right = c
        if pp is not None and pp.left == p: pp.left = ptr
        if pp is not None and pp.right == p: pp.right = ptr
        ptr.parent = pp
        p.parent = ptr
        if c is not None:
            c.parent = p
        self.update(p)
        self.update(ptr)

    def get_ptr(self, ind, root):
        """ind番目のポインタを取得する"""
        ptr = root
        while True:
            if ptr.left is None:
                l_size = 0
            else:
                l_size = ptr.left.size
            if ind < l_size:
                ptr = ptr.left
            if ind == l_size:
                self.splay(ptr)
                return ptr
            if ind > l_size:
                ptr = ptr.right
                ind = ind - l_size - 1

    def merge(self, lroot, rroot):
        if lroot is None:
            self.root = rroot
            return rroot
        if rroot is None:
            self.root = lroot
            return lroot
        lroot = self.get_ptr(lroot.size - 1, lroot)
        lroot.right = rroot
        rroot.parent = lroot
        self.update(lroot)
        return lroot
      
    def split(self, left_cnt, root):
        if left_cnt == 0:
            return None, root
        if left_cnt == root.size:
            return root, None
        root = self.get_ptr(left_cnt, root)
        lroot = root.left
        rroot = root
        rroot.left = None
        lroot.parent = None
        self.update(rroot)
        return lroot, rroot
      
    def insert(self, ind, val):
        """ind番目の値valの要素を挿入する"""
        lroot, rroot = self.split(ind, self.root)
        new_ptr = SplayNode(val)
        self.merge(self.merge(lroot, new_ptr), rroot)
    
    def delete(self, ind):
        """indの要素を削除する"""
        root = self.get_ptr(ind, self.root)
        lroot = root.left
        rroot = root.right
        if lroot is not None:
            lroot.parent = None
        if rroot is not None:
            rroot.parent = None
        root.relf = None
        root.left = None
        self.update(root)
        return self.merge(lroot, rroot), root

    def add(self, val):
        if self.root is None:
            self.insert(0, val)
            return
        ptr = self.root 
        ind = 0
        while True:
            if val < ptr.val:
                if ptr.left is None:
                    self.insert(ind, val)
                    return
                ptr = ptr.left
            else:
                ind += 1
                if ptr.left is not None:
                    ind += ptr.left.size
                if ptr.right is None:
                    self.insert(ind, val)
                    return
                ptr = ptr.right


n = int(input())
a = list(map(int,input().split()))
sp = SplayTree()
for i in range(n):
    sp.insert(i, a[i])
for i in range(n):
    sp[i] = sp[i] - (i + 1)

ave = sp[n // 2]
ans = 0

for i in range(n):
  ans += abs(sp[i] - ave)
  
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from statistics import median

    n, *a, = map(int, open(0).read().split())
    a = [x - i for i, x in enumerate(a, 1)]
    a.sort()
    m = median(a)
    ans = sum([abs(x - m) for x in a])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from statistics import median
    n, *a, = map(int, open(0).read().split())
    a = [x - i for i, x in enumerate(a, 1)]
    m = median(a)
    ans = sum([abs(x - m) for x in a])
    print(ans)


if __name__ == '__main__':
    main()