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: Accepted

Solution code:
N=int(input())
ls=[int(s) for s in input().split()]
ls=[ls[i]-i for i in range(N)]
ls.sort()
ans=0
if N%2==1:
  x=ls[(N-1)//2]
  for i in range((N-1)//2):
    ans+=x-ls[i]
  for i in range((N-1)//2,N):
    ans+=ls[i]-x
else:
  x=(ls[N//2]+ls[N//2-1])//2
  for i in range(N//2):
    ans+=x-ls[i]
  for i in range(N//2,N):
    ans+=ls[i]-x
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
min_total = 10**9

x = []
for i in range(N):
    x.append(A[i] - (i + 1))
x.sort()
b = x[N // 2]
total = 0
for i in range(N):
    total += abs(A[i] - (b + i + 1))
print(total)

Submission status: Accepted

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

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

a.sort()
b = a[n // 2]

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))
Bs = []
for i in range(N):
  b = As[i]-i-1
  Bs.append(b)
Bs.sort()
m = Bs[N//2]
r = sum(map(lambda B: abs(B-m), Bs))
print(r)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc102/tasks/arc100_a
# C - Linear Approximation

N = int(input().split()[0])
a_list = list(map(int, input().split()))
min_b = float('inf')
max_a = max(a_list)

work_list = [a - (i + 1) for i, a in enumerate(a_list)]
w = sorted(work_list)[int(N / 2)]
ans = sum([abs(x - w) for x in work_list])
print(ans)

Submission status: Accepted

Solution code:


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

N = int(input())
A = list(map(int, input().split()))
a = [0] * len(A)

# bの値は中央値
# https://qiita.com/Noiri/items/291ae9bf4a2eacab6f5f
for i in range(N):
    a[i] = A[i]-i-1

a.sort()
b = a[N // 2 - 1] if (N % 2 == 0) else a[(N + 1) // 2 - 1]

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

print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))

    for i in range(N):
        a[i] -= i+1
    a = sorted(a)
    s = a[N//2]
    ans = 0
    for i in range(N):
        ans += abs(s - a[i])
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
from collections import  Counter
import statistics
import math
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
a_li = na()
for i in range(n):
    a_li[i] = a_li[i] - (i + 1)
m1 = statistics.median_high(a_li)
#m2 = statistics.median_high(a_li)
ans1 = 0
#ans2 = 0
for i in range(n):
    ans1 += abs(a_li[i] - m1)
    #ans2 += abs(a_li[i] - m2)
print(ans1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
from collections import  Counter
import statistics
import math
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
a_li = na()
for i in range(n):
    a_li[i] = a_li[i] - (i + 1)
m1 = statistics.median_low(a_li)
#m2 = statistics.median_high(a_li)
ans1 = 0
#ans2 = 0
for i in range(n):
    ans1 += abs(a_li[i] - m1)
    #ans2 += abs(a_li[i] - m2)
print(ans1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
from collections import  Counter
import statistics
import math
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
a_li = na()
for i in range(n):
    a_li[i] = a_li[i] - (i + 1)
m1 = statistics.median_low(a_li)
m2 = statistics.median_high(a_li)
ans1 = 0
ans2 = 0
for i in range(n):
    ans1 += abs(a_li[i] - m1)
    ans2 += abs(a_li[i] - m2)
print(min(ans1, ans2))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
A=[]
for i in range(n):
  A.append(a[i]-i-1)
A.sort()
b=0
c=0
ans=0
Ans=0
if n%2!=0:
  b=n//2
  for i in range(n):
    ans+=abs(A[i]-A[b])
  print(ans)
else:
  b=n//2
  c=(n//2)-1
  for i in range(n):
    ans+=abs(A[i]-A[b])
    Ans+=abs(A[i]-A[c])
  print(min(ans,Ans))

Submission status: Accepted

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

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

ans = sum(b)

for i in range(n-1):
    ans = min(ans,ans-(b[i+1]-b[i])*(n-2*i-2))

print(ans)

Submission status: Accepted

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

a_i = sorted([a[i] - (i+1) for i in range(n)])

b = a_i[(n)//2]

ans = sum([abs(a_i[i] - b) for i in range(n)])

print(ans)

Submission status: Accepted

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

tmp=[As[i-1]-i for i in range(1,n+1)]
import statistics
b=statistics.median(tmp)
ans=[abs(As[i-1]-b-i) for i in range(1,n+1)]

print(int(sum(ans)))

Submission status: Accepted

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

a2 = [ x-i for i,x in enumerate(a)]
a2.sort()

ans = sum( abs(x - a2[n//2]) for x in a2)
print(ans)

Submission status: Accepted

Solution code:
# YouTube解説
N = int(input())
A = [int(a) for a in input().split()]

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

A.sort()
b = A[len(A) // 2]

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
n, *a = map(int, stdin.read().split())
t = list(sorted(a[i] - (i + 1) for i in range(n)))
b = t[len(t) // 2]
print(sum(abs(a[i] - (b + i + 1)) for i in range(n)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import random

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

def sorrow_value(A,b):
    value = 0
    for i in range(N):
        value += abs(A[i]-b)
    return value

def quick_sort(array):
    low_array = []
    high_array = []
    len_array = len(array)
    if len_array <= 1:
        return array
    pivot = random.choice(array)
    pivot_count = 0
    for i in range(len_array):
        if pivot > array[i]:
            low_array.append(array[i])
        elif pivot < array[i]:
            high_array.append(array[i])
        else:
            pivot_count += 1
    low_array = quick_sort(low_array)
    high_array = quick_sort(high_array)
    return low_array + [pivot]*pivot_count + high_array

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

if len(A)%2 == 0:
    if A[int(N/2)]-A[int(N/2-1)] >= 1:
        print(sorrow_value(A,A[int(N/2)]))
    else:
        print(min(sorrow_value(A,A[int(N/2)]),sorrow_value(A,A[int(N/2-1)])))
else:
    print(sorrow_value(A,A[int(N/2)]))

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N = I()
A = III()

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

A.sort()

if N%2==0:
    A = list(map(lambda x: x-A[N//2], A))
else:
    A = list(map(lambda x: x-A[(N-1)//2], A))


A = list(map(abs,A))

print(sum(A))

Submission status: Accepted

Solution code:

N = int(input())

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

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

ans = 0
diff.sort()
if N %2 == 1:
    idx = N//2
    b = diff[idx]
    for i in range(N):
        ans += abs(diff[i] - b)
else:
    idx = N // 2 
    b1 = diff[idx]
    b2 = diff[idx-1]
    tmp1 = tmp2 = 0
    for i in range(N):
        tmp1 += abs(diff[i] - b1)
        tmp2 += abs(diff[i] - b2)
    ans = min(tmp1, tmp2)

print(ans)

Submission status: Accepted

Solution code:
import math
import sys
import queue
from collections import Counter
from itertools import accumulate
from fractions import gcd
from functools import reduce

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

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

mod = 1000000007

"""
# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

if __name__ == "__main__":
    N = int(sys.stdin.readline())
    L = list(map(int, sys.stdin.readline().split()))
    L2 = [L[i] - (i + 1) for i in range(N)]
    L2.sort()
    if N % 2 == 0:
        b = L2[(N // 2) - 1]
    else:
        b = L2[(N // 2)]

    print(sum(abs(l - b) for l in L2))

Submission status: Accepted

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

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

#print(A)

A = sorted(A)

if N%2 == 1:
    b = A[(N-1)//2]
else:
    b = A[N//2] + A[N//2-1]
    b = b // 2

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

print(ans)

Submission status: Accepted

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

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

a.sort()
b = a[n // 2]

ans = 0
for ai in a:
    ans += abs(ai - b)

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
from statistics import median, mean
N = int(input())
A = list(map(int, input().split()))
B = A[:]
for i in range(1, N + 1):
    B[i-1] = B[i-1] - i
b = median(B)
ans = 0
for i in range(N):
    ans += abs(A[i] - b - i - 1)
print(int(ans))

Submission status: Accepted

Solution code:
import sys
from collections import deque
from functools import reduce
import copy


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    nums = string_to_int(inputs[0])
    N = len(nums)
    for i in range(N):
        nums[i] -= (i+1)
    nums.sort()
    total = reduce(lambda x, y: x + y, nums, 0)
    half = N // 2
    sub = nums[half]
    total = reduce(lambda acc, x: acc + abs(x - sub), nums, 0)
    return total


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    input()
    ret = solve(inputs(1))
    print(ret)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = input().split()
    B = [int(A[i])-(i+1) for i in range(len(A))]
    B = sorted(B)

    m = len(B)
    prefix = [0]
    for i in range(m):
        prefix.append(prefix[-1]+B[i])

    min_v = float('inf')
    for i in range(m):
        b = B[i]
        v = -b*(N-2*i)
        v += prefix[-1] - prefix[i]*2
        min_v = min(min_v, v)
    return min_v

if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

for i, a in enumerate(A):
    A_.append(a - i - 1)

b = sorted(A_)[N//2]

for a_ in A_:
    result += abs(a_ - b)

print(result)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(inp)-(i+1) for i,inp in enumerate(input().split())]
a.sort()

if n%2==1:
    b=a[int(n*0.5)]
    ans=sum([abs(x-b) for x in a])
else:
    b1=a[int(n*0.5)]
    b2=a[int(n*0.5)-1]
    ans1=sum([abs(x-b1) for x in a])
    ans2=sum([abs(x-b2) for x in a])
    ans=min(ans1, ans2)

print(ans)

Submission status: Accepted

Solution code:
#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n = int(input())
    al = list(map(int, input().split()))
    for i in range(n):
        al[i] = al[i] - (i + 1)
    al.sort()

    b = al[(n-1)//2]
    ans = sum([abs(a - b) for a in al])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n = int(input())
    al = list(map(int, input().split()))
    for i in range(n):
        al[i] = al[i] - (i + 1)
    al.sort()

    if n % 2 == 0:
        b = (al[(n-1)//2] + al[n//2])//2
    else:
        b = al[(n-1)//2]
    ans = sum([abs(a - b) for a in al])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

dist = []

for i in range(N):
    dist.append(A[i] - (i + 1))

b = sorted(dist)[N//2]

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = [a - i - 1 for i, a in enumerate(A)]
C = sorted(B)
m = C[N // 2]
D = [c - m for c in C]
print(sum([abs(d) for d in D]))

Submission status: Accepted

Solution code:
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = sorted([ai - (i + 1) for i, ai in enumerate(a)])
    b_center = b[n // 2]
    return sum([abs(bi - b_center) for bi in b])


if __name__ == "__main__":
    print(solve())

Submission status: Accepted

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

m = [0]*n

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

m.sort()
if n%2 == 0:
  p = n//2-1
else:
  p = (n-1)//2

ans = 0
for j in range(n):
  ans += abs(m[j] - m[p])

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from statistics import median

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [0] * N

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

    b = int(median(B))
    sumB = 0
    for i in range(N):
        sumB += abs(B[i] - b)

    print(sumB)


main()

Submission status: Accepted

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

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


a.sort()

if(n%2 == 1):
  b = a[int(n/2)]

else:
  t = 0
  for i in a:
    t += abs(i)
  ave = t/n

  p = int(n/2)
  if(abs(a[p] - ave) <= abs(a[p-1] -ave)):
    b = a[p]
  else:
    b = a[p-1]

k = list(map(lambda x:abs(x-b),a))

print(sum(k))

Submission status: Accepted

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

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

A.sort()

import math

if N % 2 == 1:
    a = A[N // 2]
else:
    a = (A[(N // 2) - 1]+ A[(N // 2)]) // 2

# a1 = math.ceil(sum(A) / N)
# a2 = math.floor(sum(A) / N)

ans = sum([abs(x - a) for x in A])
print(ans)

Submission status: Accepted

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

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


def f(b):
    return sum([abs(a-b)for a in aa])

print(f(aa[n//2]))

Submission status: Accepted

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]
f = 0
for i in range(n):
    f += abs(B[i] - b)
print(f)

Submission status: Accepted

Solution code:
from statistics import median

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

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

def calc_score(b):
    score = 0
    for a in A_star:
        score += abs(a - b)
    return score

print(calc_score(int(median(A_star))))

Submission status: Accepted

Solution code:
from statistics import median

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

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

def calc_score(b):
    score = 0
    for a in A_star:
        score += abs(a - b)
    return score

def decide_direction(b):
    score0 = calc_score(b)
    score1 = calc_score(b + 1)
    if score0 > score1:
        return 1
    else:
        return -1

b = int(median(A_star))
direction = decide_direction(b)
pre_score = calc_score(b)

while True:
    b += direction
    score = calc_score(b)
    if score >= pre_score:
        print(pre_score)
        break
    else:
        pre_score = score

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=[a-i for i,a in enumerate(A)]
b=sorted(B)[N//2]
print(sum([abs(bb-b) for bb in B]))

Submission status: Accepted

Solution code:
import statistics

N = int(input())
lst = list(map(int, input().split()))
update_lst = [lst[i] - (i+1) for i in range(len(lst))]
median = statistics.median(update_lst)
ans = [abs(i - median) for i in update_lst]
print(int(sum(ans)))

Submission status: Accepted

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

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

A.sort()
# print (A)
# max_count = 0
# tmp_count = 0
# tmp = A[0]
# candidate = A[0]
# for i in A:
#     if tmp == i:
#         tmp_count += 1
#     else:
#         if tmp_count > max_count:
#             max_count = tmp_count
#             candidate = tmp
#         tmp_count = 1
#         tmp = i

# if tmp_count > max_count:
#     candidate = tmp
# print (candidate)
ans = 0
for i in A:
    ans += abs(i - A[N//2])
print (ans)

Submission status: Accepted

Solution code:
from math import floor,ceil
N = int(input())
a_list = list(map(int,input().split()))

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

a_list.sort()

b = a_list[N//2]

diff = 0
for a in a_list:
    diff += abs(b-a)
print(diff)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
total = 0
for i in range(n):
    a[i] = a[i] - (i + 1)
if n == 1:
    print(0)
    exit()
a.sort()
if n % 2 == 0:
    ave = a[int(n/2)]
    for i in range(n):
        total += abs(a[i] - ave)
    print(total)
else:
    total2 = 0
    ave = a[int(n/2)]
    for i in range(n):
        total += abs(a[i] - ave)
    ave = a[int((n + 1)/2)]
    for i in range(n):
        total2 += abs(a[i] - ave)
    if total2 >= total:
        print(total)
    else:
        print(total2)

Submission status: Accepted

Solution code:
import itertools
import collections

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

n = getint()
a = getints()

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

a = list(sorted(a))
mid = a[n//2]

res = 0
for i in range(n):
    res += abs(a[i]-mid)

print(res)

Submission status: Accepted

Solution code:
# ABC102-C
import numpy as np
import statistics
import collections
N = int(input())
A = list(map(int, input().split()))
B = np.array(range(1, N+1))
A = np.array(A)
C = A - B
b = np.median(C)
print(int(np.sum(abs(C - b))))

Submission status: Accepted

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

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

A.sort()
b = A[N // 2]
ans = 0
for a in A :
    ans += abs(a - b)
print(ans)

Submission status: Accepted

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

B.sort()
#print(B)
if len(A)%2==1:
    for i in range(N):
        total+=abs(A[i]-(B[len(B)//2]+i+1))
        #print(B[len(B)//2+1],total)
else:
    for i in range(N):
        total+=abs(A[i]-(B[len(B)//2]+i+1))
print(total)

Submission status: Accepted

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

if n == 1:
    print(0)
    exit()

val = []

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

val.sort()
#print(val)

#idx = [(val[0],0)]
idx = []
cnt = 1
for i in range(n-1):
    if val[i] == val[i+1]:
        #cnt += 1
        if i == n-2:
            idx.append((val[i+1],i+2))
        continue
    else:
        if i == n-2:
            idx.append((val[i],i+1))
            idx.append((val[i+1],i+2))
        else:
           idx.append((val[i],i+1)) 
        #cnt = 1
        
ans_val = 0
ans2_val = 0
ans3_val = 0

flag2 = False
flag3 = False

for i in range(len(idx)):
    if idx[i][1] >= (n+1) // 2:
        ans_val = idx[i][0]
        """
        #print(i-1)
        if i-1 >= 0:
            flag2 = True
            ans2_val = idx[i-1][0]
        
        if i+1 <= len(idx)-1:
            flag3 = True
            ans3_val = idx[i+1][0]
        """
        break

#print(idx,ans_val,ans2_val)
#exit()
     
ans = 0
ans2 = 10**20
ans3 = 10**20
for i in range(n):
    ans += abs(a[i]-ans_val-i)
    if flag2 == True:
        ans2 += abs(a[i]-ans2_val-i)
    if flag3 == True:
        ans3 += abs(a[i]-ans3_val-i)
    


print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
import statistics
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
data = [0] * len(A)

for ind, i in enumerate(A):
    data[ind] = i - (ind+1)

med = statistics.median(data)

ans = 0

for  j in data:
    ans += abs(j - med)
    
print(int(ans))

Submission status: Accepted

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

l = [l[x]-(x+1) for x in range(n)]
l.sort()

b = l[n//2]

l = [abs(l[x]-b) for x in range(n)]

print(sum(l))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = [it - (idx + 1) for idx, it in enumerate(A)]
S = []

B.sort()
if N%2 == 1:
    b = B[(N-1)//2]
else:
    b = (B[(N-1)//2] + B[(N-1)//2 + 1]) // 2
    
S = sum([abs(i-b) for i in B])
    
print(S)

Submission status: Accepted

Solution code:
n=input()
num=list(map(int,input().split()))
sorted_num=sorted([num[i]-i for i in range(len(num))])
# bがこの数値だと、ぴったり重なる。
b=sorted_num[len(sorted_num)//2]
print(sum([abs(b-i) for i in sorted_num]))

Submission status: Accepted

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

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

X.sort()
ans = 0
for i in range(N):
	ans += abs(X[i]-X[N//2])

print(ans)

Submission status: Accepted

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

for i in range(n): #Bi
    lst[i] -= i+1

lst.sort()
if n%2 == 0:
    k = n//2
    b = (lst[k] + lst[k-1])/2
else:
    k = (n-1)//2
    b = lst[k]

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

print(int(ans))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))

b = np.median((A - np.arange(1, N+1)))
ans = np.abs(A - b - np.arange(1, N+1)).sum()

print(int(ans))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))

b = np.median((A - np.arange(1, N+1)))
ans = np.inf
for i in [b-1, b, b+1]:
    ans = min(np.abs(A - i - np.arange(1, N+1)).sum(), ans)

print(int(ans))

Submission status: Accepted

Solution code:
n,*l=map(int,open(0).read().split())
a=sorted([l[i]-i-1for i in range(n)])
f=lambda x:sum(abs(l[i]-i-1-x)for i in range(n))
print(min(f(a[n//2]),f(a[n//2+(n>1)])))

Submission status: Accepted

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

lst = list()
for i, a in enumerate(A):
    lst.append(a - i - 1)

lst.sort()
b = lst[N // 2]

ans = sum([abs(e - b) for e in lst])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = [A[i]-i-1 for i in range(N)]
B.sort()
C = sorted(B,reverse = True)
s = 0
for i in range(N):
    if B[i] > C[i]:
        s += B[i]-C[i]
print(s)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import statistics
n=int(input())
l=list(map(int,input().split()))
l=[l[i]-(i+1) for i in range(n)]
a=statistics.median_low(l)
b=0
if n%2==0:b=statistics.median_high(l)
print(min(sum([abs(i-a) for i in l]),sum([abs(i-b) for i in l])))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

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

arr.sort()

mean=int(sum(arr)/n)
mid1=arr[n//2]
mid2=arr[(n-1)//2]

ans = [0,0,0]

for i in range(n):
    ans[0] += abs(arr[i]-mean)
    ans[1] += abs(arr[i]-mid1)
    ans[2] += abs(arr[i]-mid2)

print(int(min(ans)))

Submission status: Accepted

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

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

import statistics
import math
a = math.floor(statistics.median(li))
b = math.ceil(statistics.median(li))

num_a,num_b = 0,0
for i in range(n):
    num_a += abs(li[i]-(a))
    num_b += abs(li[i]-(b))
print(min(num_a,num_b))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [0] * n
 
s1 = 0
s2 = 0
 
for i in range(n):
    b[i] = a[i] - i
b.sort()
 
b1 = b[n//2]
b2 = b[n//2-1]
 
for i in range(n):
    s1 += abs(a[i] - b1 - i)
 
for i in range(n):
    s2 += abs(a[i] - b2 - i)
 
print(min(s1, s2))

Submission status: Accepted

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

soretedAlist = sorted(A_list)

#print(soretedAlist)
#print(5//2)
#print(soretedAlist[N//2])
result =0
for a in soretedAlist:
    result += abs(a - soretedAlist[N//2])
print(result)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
tmp = sorted([A[i-1]-i for i in range(1,N+1)])
B = tmp[N//2]
print(sum([abs(t-B) for t in tmp]))

Submission status: Accepted

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

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


buff = math.ceil(sum(A)/N)
buff2 = sum(A)//N
buff3 = sum(A)//N-1
A.sort()
buff3 = A[N//2]
ans = 0
for i in range(N):
    ans += abs(A[i]-buff)

ans2 = 0
for i in range(N):
    ans2 += abs(A[i]-buff2)

ans3 = 0
for i in range(N):
    ans3 += abs(A[i]-buff3)
print(min(ans, min(ans2, ans3)))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = [A[i]-i for i in range(N)]
S = sorted(B)

res = 0
if N%2 == 1:
    b = S[(N-1)//2]#中央値
    for i in range(N):
        res += abs(B[i]-b)
else:
    medint1 = N//2
    medint2 = N//2-1
    med1 = S[medint1]
    med2 = S[medint2]
    t1 = 0
    t2 = 0
    for i in range(N):
        t1 += abs(B[i]-med1)
        t2 += abs(B[i]-med2)
    res = min(t1,t2)
print(res)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= i+1
b = sorted(a)
center1 = b[n//2]
center2 = 0
if not n == 1:
    center2 = b[n//2+1]
buf1 = 0
buf2 = 0
for i in range(n):
    buf1 += abs(b[i]-center1)
    buf2 += abs(b[i]-center2)
print(int(min(buf1, buf2)))

Submission status: Accepted

Solution code:
from functools import reduce
import math
import collections

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input())
    A = list(int(_) for _ in input().split())
    A_fixed = []
    for i in range(N):
        A_fixed.append(A[i]-i-1)
    cnt = 0
    A_fixed.sort()
    b = A_fixed[N//2]
    for i in range(N):
        cnt += abs(b-A_fixed[i])
    # print(A_fixed)
    # print(b)
    print(cnt)    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import math

N = int(input())
A = list(map(int, input().split()))
B = [0] * (N)
for i in range(N):
  B[i] = A[i] - (i+1)
B.sort()
  
if N%2 == 0:
  median_l = B[N//2-1]
  median_r = B[N//2]
  ans_l = 0
  ans_r = 0
  for i in range(N):
    ans_l += abs(A[i]-(median_l+i+1))
    ans_r += abs(A[i]-(median_r+i+1))
  print(min(ans_l, ans_r))
else:
  median = B[N//2]
  ans = 0
  for i in range(N):
    ans += abs(A[i]-(median+i+1))
  print(ans)

Submission status: Accepted

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

Submission status: Accepted

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