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: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A = [A[_] - (_ + 1) for _ in range(N)]
AA = sorted(A)
ans = 0
ans1 = 0
if N % 2 != 0:
    center = N // 2
    num = AA[center]
    for i in range(N):
        ans += abs(AA[i]-num)
    print(ans)
else:
    center = len(AA) // 2
    for i in range(N):
        ans += abs(AA[i]- num)
        ans1 += abs(AA[i]-(num + 1))
    print(min(ans, ans1))

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
for i in range(n):
  a[i] -= (i+1)
ave = sum(a) // n
foi i in range(n):
  a[i] = abs(a[i] - ave)
print(sum(a))

Submission status: Runtime Error

Solution code:
macro_rules! input {
    ($ttype:ty) => {
        {
            let mut input = String::new();
            let _= std::io::stdin().read_line(&mut input);
            input.trim().parse::<$ttype>().unwrap()
        }
    };

    ($($ttype:ty),*) => {
        {
            use std::io::BufRead;
            let mut input = String::new();
            let stdin = std::io::stdin();
            let _ = stdin.lock().read_line(&mut input);
            let mut iter = input.trim().split_whitespace();
            (
                $(iter.next().unwrap().parse::<$ttype>().unwrap(),)*
            )
        }
    };

    ($ttype:ty; $x:expr) => {
        {
            use std::io::BufRead;
            let mut input = String::new();
            let stdin = std::io::stdin();
            let _ = stdin.lock().read_line(&mut input);
            let v: Vec<$ttype> = input
                .trim()
                .split_whitespace()
                .map(|x| x.parse().unwrap())
                .collect();
            v
        }
    };

    ($ttype:ty; $x:expr; $y:expr) => {
        {
            use std::io::BufRead;
            let mut matrix = Vec::with_capacity($y);
            for _ in 0..$y {
                let mut input = String::new();
                let stdin = std::io::stdin();
                let _ = stdin.lock().read_line(&mut input);
                let v: Vec<$ttype> = input
                    .trim()
                    .split_whitespace()
                    .map(|x| x.parse().unwrap())
                    .collect();
                matrix.push(v);
            }
            matrix
        }
    };
}

fn read_vec() -> Vec<i32> {
    let mut input = String::new();
    let _ = std::io::stdin().read_line(&mut input);
    input.trim().split_whitespace().map(|x| x.parse().unwrap()).collect()
}

fn main() {
    let n = input!(usize);
    let a_list = read_vec();
    let mut b_list = a_list
        .iter()
        .enumerate()
        .map(|(i, x)| x - (i as i32 + 1))
        .collect::<Vec<i32>>();
    b_list.sort();

    let median = if n % 2 == 0 {
        (b_list[n/2-1] + b_list[n/2]) / 2
    } else {
        b_list[n/2]
    };

    let result = b_list
        .iter()
        .map(|x| (x - median).abs())
        .fold(0, |acc, x| acc + x);
    println!("{}", result);
}

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    a_list = map(lambda x: int(x), input().split(' '))
    b_list = [x - i for i, x in zip(range(1, n+1), a_list)]
    b_list.sort()
    median = 0
    if n % 2 == 0:
        median = (b_list[n/2-1] + b_list[n/2]) / 2
    else:
        median = b_list[n//2]
    result = sum([x - median for x in b_list])
    print(result)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# Linear Approximation
from statistics import median
n = int(input())
a = list(map(int, input().split()))
b = []
_sum = 0
for i in range(n):
    b.append(a[i] - i - 1)
print(med)
for i in range(n):
    _sum += abs(b[i] - med)
print(int(_sum))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def f(x,i,n):
    sadness = 0
    for j in range(n):
        sadness += abs(x[j]-i)
    return(sadness)
N = int(input())
H = [int(i) for i in input().split()]
for i in range(N):
    H[i] -= i+1
H = sorted(H)
k = N // 2
print(min(f(H,H[k-1],N),f(H,H[k],N),f(H,H[k+1],N)))

Submission status: Runtime Error

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

def sadness(x,y):
  s = 0
  for i in range(len(y)):
    s += abs(y[i]-x)
  return s

if n%2 == 0:
  print(sadness(a[n/2],b))
else:
  print(sadness(a[(n-1)/2],b))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import statistics

N = int(input())
A = [int(c) for c in input().split()]
A = [abs(n - (b+i+1)) for i, n in enumerate(A)]

b = int(statistics.median(A))
print(sum([abs(n - b) for n in A]))

Submission status: Runtime Error

Solution code:
import statistics as stc

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

#a[i]-(b+1) = a[i]-i-b
a_ = [a[i]-(i+1) for i in range(len(a))]

b=stc.median(a)

def sad(a,b):
    score=0
    for i in range(1,len(a)+1):
        #score+= abs(a[i]-(b+i))
        score+= abs(a_[i]-b)

res = sad(a,b)
print(res)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
fun main(args : Array<String>) {
    val N = readLine()!!.toInt()
    val A = readLine()!!.split(" ").map { it.toInt() }
    val B = (1..N).map {
        val index = it - 1
        A.get(index) - it
    }.toMutableList()
    B.sort()

    val median = B.get(N / 2)
    val answer = B.map { Math.abs(it - median) }.sum()

    println(answer)
}

Submission status: Runtime Error

Solution code:
fun main(args : Array<String>) {
    val N = readLine()!!.toInt()
    val A = readLine()!!.split(" ").map { it.toInt() }
    val B = (1..N).map {
        val index = it - 1
        A.get(index) - it
    }.sorted()

    val median = B.get(N / 2)

    val answer = B.map { Math.abs(it - median) }.sum()

    print(answer)
}

Submission status: Runtime Error

Solution code:
N = int(input())
a = list(int(i) for i in input().split())
for i in range(N):
  a[i] = a[i]-i
a.sort()
if N%2==0:
  b=int((a[int(N/2)]+a[int(N/2+1)])/2)
else:
  b=a[int((N+1)/2)]
sum_1=0
sum_2=0
sum_3=0
for i in range(N):
  sum_1 += abs(a[i]-b)
b-=1
for i in range(N):
  sum_2 += abs(a[i]-b)
b+=2
for i in range(N):
  sum_3 += abs(a[i]-b)
print(min(sum_1,sum_2,sum_3))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
for i in range(N):
    A[i] = A[i] - i - 1
A = sorted(A)
medN = N//2

x = 0
for i in range(N):
    x = x + abs(A[i] - A[halfN])
print(x)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
for i in range(N):
    A[i] = A[i] - i
sorted(A)
halfN = int(N/2)
x = 0
list = []
for j in range(-1,2):
    for i in range(N):
        x = x + abs(A[i] - A[halfN+j])
    list.append(x)
    x = 0
print(min(list))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input))
b = []
for i in range(n):
    b.append(a[i] - i -1)
print(b)

ans_sum = 10**9
ans = 0

for k in range(min(b), max(b)):
    sum = 0
    for i in range(n):
        sum = sum + abs(b[i]-k)
    if sum < ans_sum:
        ans_sum = sum
print(ans_sum)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input))
b = []
for i in range(n):
    b.append(a[i] - i -1)
print(b)

ans_sum = 10**9
ans = 0

for k in range(min(b), max(b)):
    sum = 0
    for i in range(n):
        sum = sum + abs(b[i]-k)
    if sum < ans_sum:
        ans_sum = sum
        ans = k +1
print(ans)
print(ans_sum)

Submission status: Runtime Error

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]

for i in range(n):
    a[i] = abs(a[i]-b)
print(sum(a))

Submission status: Runtime Error

Solution code:
n = int(input())

k = list(int(i) for i in input().split())  


q = []
for x in range(n):
  q.append(abs(k[x]-(x+1)))

  
print(sum(set(q))

Submission status: Runtime Error

Solution code:
import statistics

n = int(input())
a = [int(n) for n in input().split(" ")]

sub_a = [a_n - i - 1 for i, a_n in enumerate(a)]
median = statistics.median(sub_a)
print(sum([abs(sub_a-median) for sub_a_n in sub_a]))

Submission status: Runtime Error

Solution code:
import math
import statistics
import numpy as np
size = int(input())
A = np.array(list(map(int,input().split())))
i = np.array(list(range(1,size+1)))

remain_list = A-i
median = statistics.median(remain_list)
print(sum(remain_list - median))A

Submission status: Runtime Error

Solution code:
import math
import statistics
import numpy as np
size = int(input())
A = np.array(list(map(int,input().split())))
i = np.array(list(range(1,size+1)))

remain_list = A-i
median = statistics.median(remain_list)
print(sum(remain_list - median))A

Submission status: Runtime Error

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

#b=(N(N+1) - 2sig(Ai))/2N
#まず数列の総計を求める
sum=0
for a in list:
   sum=sum+a

b=N*N + N
b=b-1*sum
b=b/(2*N)

#bに一番近い整数を求める
seisubu=int(b)
shosubu=b-int(b)

if shosubu < 0.5:
	b=int(b)
else:
	b=int(b)+1

#悲しみを求める
i=1
sad=0
for a in line:
	if a-(b+i) < 0:
		sad=sad+(b+i)-a
	else:
		sad=sad+a-(b+i)
		
	i=i+1
	
print(sad)

Submission status: Runtime Error

Solution code:
import statistics

n = input()
a = list(map(int, input().split()))
b = list()
for i, num in enumerate(a):
  b.append(num - i)
print(int(statistics(b))

Submission status: Runtime Error

Solution code:
from statistics import mode
N = int(input())
a = list(map(int, input().split()))
for i in range(N):
    a[i] = a[i] - (i + 1)
if len(a) == len(set(a)):
    b = 0
else:
    b = mode(a)
for i in range(N):
    a[i] = abs(a[i] - b)
print(sum(a))

Submission status: Runtime Error

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

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

A.sort()
print(A)
if N % 2 == 0:
    median = A[N//2]
else:
    median = A[(N + 1)//2]

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

Submission status: Runtime Error

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

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


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

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

print(min(sum_list))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
1.	n = int(input())
2.	a = list(map(int, input().split()))
3.	tmp = [a[x] - (x+1) for x in range(0,n)]
4.	tmp.sort()
5.	b = tmp[n // 2]
6.	print(sum((abs(tmp[i] - b) for i in range(0,n))))

Submission status: Runtime Error

Solution code:
import copy
from statistics import mean, median,variance,stdev
N=int(input())
li = list(map(int,input().split()))

for i in range(0,N):
	li[i] = li[i] - i -1
a = []
d = copy.copy(li)
if len(li) %2 == 1:
    m = median(li)
    k = 0
    for j in range(0,N):
        k = k + abs(li[j]-m)
else:
    c = copy.copy(li)
    c.sort()
    o = []
    for i in range(c[len(c)//2],c[len(c)//2+1]):
        k = 0
        for j in range(N):
            k = k + abs(li[j]-i)
        o.append(k)
    k = min(o)
print(k)

Submission status: Runtime Error

Solution code:
import copy
N=int(input())
li = list(map(int,input().split()))
for i in range(0,N):
	li[i] = li[i] - i -1
a = []
d = copy.copy(li)
while len(d) >= 3:
	del d[max(d)]
	del d[min(d)]
for i in range(min(d),max(d)+1):
	k = 0
	for j in range(N):
		k = k + abs(li[j]-i)
	a.append(min(k))

Submission status: Runtime Error

Solution code:
import copy
N=int(input())
li = list(map(int,input().split()))
for i in range(0,N):
	li[i] = li[i] - i -1
a = []
d = copy.copy(li)
while len(d) >= 3:
	del d[max(d)]
	del d[min(d)]
for i in range(min(d),max(d)+1):
	k = 0
	for j in range(N):
		k = k + abs(li[j]-i)
	a.append(k)
print(a)

Submission status: Runtime Error

Solution code:
import math

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

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

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

print(str(loss))

Submission status: Runtime Error

Solution code:
import math

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

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

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

print(str(loss))

Submission status: Runtime Error

Solution code:
import statistics

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

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

b = median_low(A)
ans = 0

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

print(ans)

Submission status: Runtime Error

Solution code:
import math

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

b_ = array2[n//2]
b_1 = array2[n//2+1]
b_2 = array2[n//2-1]

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

Submission status: Runtime Error

Solution code:
n = int(input())
a_list = list(map(int,input().split()))
b = 0
while:
  x = 0
  y = 10000000000000000000000000000000000
  b = b + 1
  for i in range(n-1):
    x = x + abs(a_list[i] - b - i)
  if x <= y:
    y = x
  else:
    break
print(y)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 桁数の入力
a = int(input())
# スペース区切りの整数の入力
b = input().split()
b = list(map(int, b))
c = list(range(1, a + 1))
d = []
for i, j in zip(b, c):
    d.append(i-j)

d.sort()
e = d[a // 2]
f = 0
for i in range(5):
    f += abs(d[i] - e)
print(f)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans1 = 0
ans2 = 0
 
diff = []
for i, index in enumerate(a,1):
    diff.append(abs(i - index))
 
diff.sort()
if n % 2 == 1:
    b = diff[len(diff) // 2]
    for i in diff:
        ans1 += abs(i - b)
 
    print(ans1)
else:
    b1 = diff[len(diff) // 2 - 1]
    b2 = diff[len(diff) // 2]
    for i in diff:
        ans1 += abs(i -b1)
        ans2 += abs(i -b2)
    print(min(ans1.ans2))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
diff = []
for i, index in enumerate(a,1):
    diff.append(i-index)

diff.sort()
if n % 2 == 1:
    ans = 0
    b = diff[n // 2]
    for i in diff:
        ans += abs(i - b)
    print(ans)
else:
    ans1,ans2 = 0
    b1 = diff[n // 2 - 1]
    b2 = diff[n // 2]
    for i in diff:
        ans1 += abs(i -b1)
        ans2 += abs(i -b2)
    print(min(b1.b2))

Submission status: Runtime Error

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

diff = []
for i, index in enumerate(a,1):
    diff.append(i-index)

diff.sort()
if n % 2 == 1:
    b = diff[n // 2]
    for i in diff:
        ans1 += abs(i - b)
    print(ans1)
else:
    b1 = diff[n // 2 - 1]
    b2 = diff[n // 2]
    for i in diff:
        ans1 += abs(i -b1)
        ans2 += abs(i -b2)
    print(min(b1.b2))

Submission status: Runtime Error

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

diff = []
for i, index in enumerate(a,1):
    diff.append(abs(i - index))

diff.sort()
if n % 2 == 1:
    b = diff[len(diff) // 2]
    for i in diff:
        ans1 += abs(i - b)

    print(ans1)
else:
    b1 = diff[len(diff) // 2 - 1]
    b2 = diff[len(diff) // 2]
    for i in diff:
        ans1 += abs(i -b1)
        ans2 += abs(i -b2)
    print(min(b1.b2))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def sadness(l, b):
    sad = 0
    for i, a in enumerate(l, 1):
        sad += abs(a - (b+i))
    return sad

if __name__ == '__main__':
    n = int(input())
    l = list(map(int, input().split()))

    # y=x+b
    # rough estimate
    if len(l) > 5:
        ls = l[0:5]

    diffset = set()
    for i, a in enumerate(l, 1):
        #print("{} {}".format(i, a))
        diff = i-a
        diffset.add(diff)

    s = set()
    for i in range(max(diffset)+1):
        s.add(sadness(l, i*-1))
    if max(diffset) == 0:
        s.add(sadness(l, 0))

    print("{}".format(min(s)))

Submission status: Runtime Error

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

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

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


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


def search(max_b, min_b):

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

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

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

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

Submission status: Runtime Error

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

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

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

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

sad_list = [(b, calc_sadness(points, b)) for b in b_list]
sad_list.sort(key=lambda x:x[1])

peak_sads = sorted(sad_list[:2], key=lambda x:x[0])

min_sad = 10000000000
for b in range(peak_sads[0][0], peak_sads[1][0]+1):
    sadness = calc_sadness(points, b)
    if sadness < min_sad:
        min_sad = sadness

print(min_sad)

Submission status: Runtime Error

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

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

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

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

sad_list = [(b, calc_sadness(points, b)) for b in b_list]
sad_list.sort(key=lambda x:x[1])

peak_sads = sorted(sad_list[:2], key=lambda x:x[0])
    
sadness_list = [calc_sadness(points, b) for b in range(peak_sads[0][0], peak_sads[1][0]+1)]

print(min(sadness_list))

Submission status: Runtime Error

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

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

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

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

sad_list = [(b, calc_sadness(points, b)) for b in b_list]
sad_list.sort(key=lambda x:x[1])

peak_sads = sorted(sad_list[:2], key=lambda x:x[0])

sadness_list = []
for b in range(peak_sads[0][0], peak_sads[1][0]+1):
    sadness_list.append(calc_sadness(points, b))

print(min(sadness_list))

Submission status: Runtime Error

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

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

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

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

sad_list = [(b, calc_sadness(points, b)) for b in b_list]
sad_list.sort(key=lambda x:x[1])

peak_sads = sorted(sad_list[:2], key=lambda x:x[0])

sadness_list = []
for b in range(peak_sads[0][0], peak_sads[1][0]+1):
    sadness_list.append(calc_sadness(points, b))

print(min(sadness_list))

Submission status: Runtime Error

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

def sunuke(b):
    ret = 0
    sub = 1
    for a in A:
        ret += abs(a - (b+ sub))
        sub += 1
    return ret


B = []

sub = 1
for a in A:
    b = a - sub
    B.append(b)
    sub += 1

B.sort()
b1 = N // 2
b2 = b1 + 1

b1_s = sunuke(B[b1])
b2_s = sunuke(B[b2])
if b1_s < b2_s:
    print(b1_s)
else:
    print(b2_s)

Submission status: Runtime Error

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

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

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

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

M=[]

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

M.sort()

if N%2==0:
	med1=N//2
	med2=N//2+1
	if N <= med2:
		med2 = med1
	ans=min(calcVal(M[med1]),calcVal(M[med2]),calcVal(0))

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


print(ans)

Submission status: Runtime Error

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

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

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

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

M=[]

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

M.sort()

if N%2==0:
	med1=N//2
	med2=N//2+1
	ans=min(calcVal(M[med1]),calcVal(M[med2]))

else:
	med=(N+1)//2
	ans = calcVal(M[med])


print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
N = input()
AList = list(map(int, input().split()))
listnum = 1000000000

low = -1000000000
high = 1000000000

mode = 1
a1 = 0
a2 = 0
while(True):
    p1 = math.floor((abs(low) + abs(high))/3) + low
    p2 = high - math.floor((abs(low) + abs(high))/3) 

    for j in range(1,int(N)+1):
        a1 += abs(AList[j-1] -(p1 + j))
    for j in range(1,int(N)+1):
        a2 += abs(AList[j-1] -(p2 + j))

    if a1 == a2 or abs(a1-a2) == 1:
        print(min(a1,a2))
        sys.exit()
    elif a1 < a2:
        high = p2
    else:
        low = p1        
    a1 = 0
    a2 = 0

Submission status: Runtime Error

Solution code:
input_list = []
index = 1
for i in input().split():
    item = int(i) - index
    input_list.append(item)
    index += 1

input_list.sort()
b = input_list[N//2]
print(sum(map(lambda x: abs(x-b), input_list)))

Submission status: Runtime Error

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

A_sorted = sorted([A[i] - (i+1) for i in range(N)])
b = A_sorted[int((len(A)-1)/2)]
b2 = A_sorted[int((len(A)-1)/2 + 1)]

sad_1 = sum([abs(A_sorted[i] - b) for i in range(N)])
sad_2 = sum([abs(A_sorted[i] - b2) for i in range(N)])

print(min(sad_1, sad_2))

Submission status: Runtime Error

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

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

ans = 10**100
for i in [n//2-1, n//2, n//2+1]:
    ans = min(ans, sum([abs(A[j]-A[i]) for j in range(n)]))

print(ans)

Submission status: Runtime Error

Solution code:
from statistics import median, median_low, median_high
n = int(input())
an = input().split()
list = []

for i in range(n):
    t = int(an[i])
    cn = t - (i+1)
    list.append(cn)

list.sort()

median = median(list)
median_low = median_low(list)
median_high = median_high(list)

if median -median_low > median_high - median:
    b = median_high

else:
    b = median_low

abs = 0
for r in range(n):
    abs = abs + abs(int(an[r]) -b - (r+1))

print(abs)

Submission status: Runtime Error

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

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

An.sort()

m = N-1
if (m % 2 == 0):
    m = m//2
    cent = (An[m] + An[m + 1]) // 2
else:
    cent = An[(m+1)//2]

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

print(ans)

Submission status: Runtime Error

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

p = sorted([v - (i + 1) for i, v in enumerate(A)])

res = min(sum(map(abs, [i - p[N//2] for i in p])), sum(map(abs, [i - p[N//2-1] for i in p])), sum(map(abs, [i - p[N//2+1] for i in p])))
print(int(res))

Submission status: Runtime Error

Solution code:
from statistics import median, median_low, median_high
n = int(input())
an = input().split()
list = []

for i in range(n+1):
    t = int(an[i])
    cn = t - (i+1)
    list.append(cn)

list.sort()
median = median(list)
median_low = median_low(list)
median_high = median_high(list)

if median -median_low > median_high - median:
    res = median_high


else:
    res = median_low

print(res)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
def devide2a(x):
    
def devide2b(y):
    if x % 2 == 0:
        return int(n / 2)
    else:
        return int((n - 1) / 2)
for j in range(n):
    a[j] = a[j] - (j + 1)
a.sort()
if x % 2 == 0:
    print(sum(a[n / 2:]) - sum(a[:n / 2])
else:
    print(sum(a[(n + 1) / 2:]) - sum(a[:(n - 1) / 2])

Submission status: Runtime Error

Solution code:
import statistics
import math
N = int(input())
AS = input().split()
AS = [int(i) for i in AS]
BS = [int(AS[j-1] - j) for  i in range(1,N+1)]
b = int('{0:8.0f}'.format(statistics.median(BS)))
result_a = 0
result_b = 0
result_c = 0
for j in range (1, N+1):
    result_a += abs(int(AS[j-1]) - b - j)
for j in range (1, N+1):
    result_b += abs(int(AS[j-1]) - b - 1 - j)
for j in range (1, N+1):
    result_c += abs(int(AS[j-1]) - b + 1 - j)
print (int(min(result_a,result_b,result_c)))

Submission status: Runtime Error

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

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

An.sort()

m = N-1
if (m % 2 == 0):
    cent = (An[m//2] + An[m//2 + 1]) // 2
else:
    cent = An[(m+1)//2]

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

print(ans)

Submission status: Runtime Error

Solution code:
import statistics
import math
N = int(input())
AS = input().split()
AS = [int(i) for i in AS]
BS = [int(AS[j-1] - j) for  i in range(1,N+1)]
b = int('{0:8.0f}'.format(statistics.median(BS)))
result_a = 0
result_b = 0
result_c = 0
for j in range (1, N+1):
    result_a += abs(int(AS[j-1]) - b - j)
for j in range (1, N+1):
    result_b += abs(int(AS[j-1]) - b - 1 - j)
for j in range (1, N+1):
    result_c += abs(int(AS[j-1]) - b + 1 - j)
print (min(result_a,result_b,result_c))

Submission status: Runtime Error

Solution code:
def median(l):
    n = len(l)
    ls = sorted(l)
    if n == 1: return ls[0]
    if n%2 == 0:
        m1 = ls[int(n/2)-1]
        m2 = ls[int(n/2)]
        return (m1+m2)/2
    
    return ls[int(n/2)-1]

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

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

A_m = median(A_)
A_m1 = math.floor(A_m)
A_m2 = math.ceil(A_m)

A_b = [sum([abs(a - i) for a in A_]) for i in (A_m1, A_m2)]

print(min(A_b))