Problem:


Score : 600 points

Problem Statement

Snuke has an integer sequence A of length N.

He will make three cuts in A and divide it into four (non-empty) contiguous subsequences B, C, D and E.
The positions of the cuts can be freely chosen.

Let P,Q,R,S be the sums of the elements in B,C,D,E, respectively.
Snuke is happier when the absolute difference of the maximum and the minimum among P,Q,R,S is smaller.
Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S.

Constraints

4 \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

Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S.

Sample Input 1

5
3 2 4 1 2

Sample Output 1

2

If we divide A as B,C,D,E=(3),(2),(4),(1,2), then P=3,Q=2,R=4,S=1+2=3.
Here, the maximum and the minimum among P,Q,R,S are 4 and 2, with the absolute difference of 2.
We cannot make the absolute difference of the maximum and the minimum less than 2, so the answer is 2.

Sample Input 2

10
10 71 84 33 6 47 23 25 52 64

Sample Output 2

36

Sample Input 3

7
1 2 3 1000000000 4 5 6

Sample Output 3

999999994



Sample input:
5
3 2 4 1 2


Sample output:
2

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = pow(10,10)
for i in range(1, N - 3):
	for j in range(i + 1, N - 2):
		for k in range(j + 1, N):
			B = list(A[:i])
			C = list(A[i:j])
			D = list(A[j:k])
			E = list(A[k:])
			P = sum(B)
			Q = sum(C)
			R = sum(D)
			S = sum(E)
			ans = min(ans, temp = max(P, Q, R, S) - min(P, Q, R, S))
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
 
A=list(map(int,input().split()))
 
fourdivide=sum(A)//4
P=Q=R=S=0
Pflag=Qflag=Rflag=0
Pindex=Qindex=Rindex=0
Ppre=Qpre=Rpre=Spre=0
answer=10**9

def intr(a,b,c):
	global answer
	d=sum(A)-a-b-c
	answer=min(answer,max(a,b,c,d)-min(a,b,c,d))
	print(a,b,c,d)

for i in range(N):
	if Pflag==0 and i<=N-4:
		P+=A[i]
		if P>=fourdivide:
			Pflag=1
			Pindex=i
			if i!=0:
				Ppre=P-A[i]
	elif Qflag==0 and i<=N-3:
		Q+=A[i]
		if Q>=fourdivide:
			Qflag=1
			Qindex=i
			Qpre=Q-A[i]
	elif Rflag==0 and i<=N-2:
		R+=A[i]
		if R>=fourdivide:
			Rflag=1
			Rindex=i
			Rpre=R-A[i]            

intr(P,Q,R)
if Rpre!=0:
	intr(P,Q,Rpre)
Rflag=0
QpreR=QpreRpre=0

for i in range(Qindex,N):
	if Rflag==0 and i<=N-2:
		QpreR+=A[i]
		if QpreR>=fourdivide:
			Rflag=1
			Rindex=i
			QpreRpre=QpreR-A[i]

if Qpre!=0 and QpreR!=0:
	intr(P,Qpre,QpreR)
if Qpre!=0 and QpreRpre!=0:
	intr(P,Qpre,QpreRpre)

Qflag=0
Rflag=0
PpreQ=PpreQpre=0
PpreR=PpreRpre=0

if Ppre!=0:
	for i in range(Pindex,N):
		if Qflag==0 and i<=N-3:
			PpreQ+=A[i]
			if PpreQ>=fourdivide:
				Qflag=1
				Qindex=i
				PpreQpre=PpreQ-A[i]
		elif Rflag==0 and N-2:
			PpreR+=A[i]
			if PpreR>=fourdivide:
				Rflag=1
				Rindex=i
				PpreRpre=PpreR-A[i]
	if Ppre!=0 and PpreQ!=0 and PpreR!=0:
		intr(Ppre,PpreQ,PpreR)
	if Ppre!=0 and PpreQ!=0 and PpreRPre!=0:
		intr(Ppre,PpreQ,PpreRpre)
	Rflag=0
	PpreQpreR=PpreQpreRpre=0
	for i in range(Qindex,N):
		if Rflag==0 and i<=N-2:
			PpreQpreR+=A[i]
			if PpreQpreR>=fourdivide:
				Rflag=1
				Rindex=i
				PpreQpreRpre=PpreQpreR-A[i]
	if Ppre!=0 and PpreQpre!=0 and PpreQpreR!=0:
		intr(Ppre,PpreQpre,PpreQpreR)
	if Ppre!=0 and PpreQpre!=0 and PpreQpreRpre!=0:
		intr(Ppre,PpreQpre,PpreQpreRpre)
      



print(answer)

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    A = []
    data = input().split()
    for i in range(N):
        A.append(int(data[i]))
    S = sum(A)
    m = S // 4
    B = [[]]
    t = 0; part = 0
    partsum = 0
    while t < N:
        if partsum + A[t] > m:
            partsum = 0
            part += 1
            B.append([])
        B[part].append(A[t])
        partsum += A[t]
        t += 1
    P = [sum(B[i]) for i in range(4)]
    print(max(P) - min(P))
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    A = []
    data = input().split()
    for i in range(N):
        A.append(int(data[i]))
    S = sum(A)
    m = S // 4
    B = [[]]
    t = 0; part = 0
    partsum = 0
    while t < N:
        if partsum + A[t] > m:
            part += 1
            B.append([])
        B[part].append(A[t])
        t += 1
    P = [sum(B[i]) for i in range(4)]
    print(max(P) - min(P))
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
	N = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	def ano_helper(BCDE):
		BCDE = BCDE + [s - sum(BCDE)]
		BCDE.sort()
		return abs(BCDE[-1] - BCDE[0])
	def helper(BCDEs, inds):
		if len(BCDEs[0]) == 4:
			return BCDEs
		ret_BCDEs = []
		ret_inds = []
		for candidate in range(len(BCDEs)):
			BCDE = BCDEs[candidate]
			ind = inds[candidate]
			ave = sum(A[ind:]) / (5 - len(BCDE))
			temp = A[ind]
			ind += 1
			while ind < N and temp + A[ind] < ave:
				temp += A[ind]
				ind += 1
			ret_BCDEs.append(BCDE + [temp])
			ret_inds.append(ind)
			if ind <= N - 1:
				ret_BCDEs.append(BCDE + [temp + A[ind]])
				ret_inds.append(ind + 1)
		return helper(ret_BCDEs, ret_inds)
	print(sorted([ano_helper(i[1:]) for i in helper([[0]], [0])])[0])
	return 0
	#BCDE = []
	#ind = 0
	#su = []
	#tempBCDE = [[]]
	#while len(BCDE[-1]) < 4:
	#	temp = 0
	#	ret = []
	#	while temp < (s - su) / (4 - len(BCDE)):
	#		te = A[ind]
	#		temp += te
	#		ret.append(te)
	#		su += te
	#		ind += 1
	#	tempBCDE.append(ret)
	#print(BCDE)
main()

Submission status: Runtime Error

Solution code:
def main():
	N = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	def ano_helper(BCDE):
		BCDE = BCDE + [s - sum(BCDE)]
		BCDE.sort()
		return abs(BCDE[-1] - BCDE[0])
	def helper(BCDEs, inds):
		if len(BCDEs[0]) == 4:
			return BCDEs
		ret_BCDEs = []
		ret_inds = []
		for candidate in range(len(BCDEs)):
			BCDE = BCDEs[candidate]
			ind = inds[candidate]
			ave = sum(A[ind:]) / (5 - len(BCDE))
			temp = A[ind]
			ind += 1
			while ind < N and temp + A[ind] < ave:
				temp += A[ind]
				ind += 1
			ret_BCDEs.append(BCDE + [temp])
			ret_inds.append(ind)
			if ind <= N - 1:
				ret_BCDEs.append(BCDE + [temp + A[ind]])
				ret_inds.append(ind + 1)
		return helper(ret_BCDEs, ret_inds)
	print(helper([[0]], [0]))
	print(sorted([ano_helper(i[1:]) for i in helper([[0]], [0])])[0])
	return 0
	#BCDE = []
	#ind = 0
	#su = []
	#tempBCDE = [[]]
	#while len(BCDE[-1]) < 4:
	#	temp = 0
	#	ret = []
	#	while temp < (s - su) / (4 - len(BCDE)):
	#		te = A[ind]
	#		temp += te
	#		ret.append(te)
	#		su += te
	#		ind += 1
	#	tempBCDE.append(ret)
	#print(BCDE)
main()

Submission status: Runtime Error

Solution code:
def main():
	N = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	def ano_helper(BCDE):
		BCDE = BCDE + [s - sum(BCDE)]
		BCDE.sort()
		return abs(BCDE[-1] - BCDE[0])
	def helper(BCDEs, inds):
		if len(BCDEs[0]) == 4:
			return BCDEs
		ret_BCDEs = []
		ret_inds = []
		for candidate in range(len(BCDEs)):
			BCDE = BCDEs[candidate]
			ind = inds[candidate]
			ave = sum(A[ind:]) / (5 - len(BCDE))
			temp = A[ind]
			ind += 1
			while ind < N and temp + A[ind] <= ave:
				temp += A[ind]
				ind += 1
			ret_BCDEs.append(BCDE + [temp])
			ret_inds.append(ind)
			if ind <= N - 1:
				ret_BCDEs.append(BCDE + [temp + A[ind]])
				ret_inds.append(ind + 1)
		return helper(ret_BCDEs, ret_inds)
	print(helper([[0]], [0]))
	print(sorted([ano_helper(i[1:]) for i in helper([[0]], [0])])[0])
	return 0
	#BCDE = []
	#ind = 0
	#su = []
	#tempBCDE = [[]]
	#while len(BCDE[-1]) < 4:
	#	temp = 0
	#	ret = []
	#	while temp < (s - su) / (4 - len(BCDE)):
	#		te = A[ind]
	#		temp += te
	#		ret.append(te)
	#		su += te
	#		ind += 1
	#	tempBCDE.append(ret)
	#print(BCDE)
main()

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
a = list(map(int,input().split()))

def split(a,sp):
    return [a[sp[k]:sp[k+1]] for k in range(len(sp)-1)]

def su(a_sp):
    return [np.sum(aa) for aa in a_sp]
    
def ev(sp_su):
    score = np.max(sp_su) - np.min(sp_su)
    return score

def ev_all(a,sp):
    a_sp = split(a,sp)
    sp_su = su(a_sp)
    score = ev(sp_su)
    return score

import copy

lef = int(np.ceil(n/4))
mid = int(np.ceil(n/4 * 2))
rig = int(np.ceil(n/4 * 3))
sp = [0,lef,mid,rig,n]

pre_score = 10000000000
pre_sps = [sp]
all_ex = []
owari = 0
while True:
    scores = []
    params = []

    for i in [-1,1]:
        for k in range(3):
            sp_ex = copy.deepcopy(sp)
            sp_ex[k+1] += i
            score = ev_all(a,sp_ex)
            scores.append(score)
            params.append(sp_ex)

    cand = np.where(scores == np.min(scores))[0]
    if len(cand) == 1:
        all_ex.append(1)
    ok = 0
    for c in cand:
        sp = params[c]
        if check(sp,pre_sps) == 0:
            all_ex.append(0)
            ok = 1
            break
    if ok == 0:
        all_ex.append(1)
        sp = pre_sps[(np.array(all_ex) == 0)[-1]]
            
    pre_sps.append(sp)
    if np.min(scores) <= pre_score:
        pre_score = np.min(scores)
    else:
        break
    if owari == 1:
        break
print(int(pre_score))

Submission status: Runtime Error

Solution code:
def main():
	N = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	def ano_helper(BCDE):
		BCDE = BCDE + [s - sum(BCDE)]
		BCDE.sort()
		return abs(BCDE[-1] - BCDE[0])
	def helper(BCDEs, inds):
		if len(BCDEs[0]) == 4:
			return BCDEs
		ret_BCDEs = []
		ret_inds = []
		for candidate in range(len(BCDEs)):
			BCDE = BCDEs[candidate]
			ind = inds[candidate]
			ave = sum(A[ind:]) / (5 - len(BCDE))
			temp = 0
			while temp + A[ind] < ave:
				temp += A[ind]
				ind += 1
			ret_BCDEs.append(BCDE + [temp])
			ret_inds.append(ind)
			if ind <= N - 1:
				ret_BCDEs.append(BCDE + [temp + A[ind]])
				ret_inds.append(ind + 1)
		return helper(ret_BCDEs, ret_inds)
	print(sorted([ano_helper(i[1:]) for i in helper([[0]], [0])])[0])
	return 0
	#BCDE = []
	#ind = 0
	#su = []
	#tempBCDE = [[]]
	#while len(BCDE[-1]) < 4:
	#	temp = 0
	#	ret = []
	#	while temp < (s - su) / (4 - len(BCDE)):
	#		te = A[ind]
	#		temp += te
	#		ret.append(te)
	#		su += te
	#		ind += 1
	#	tempBCDE.append(ret)
	#print(BCDE)
main()

Submission status: Runtime Error

Solution code:
def main():
	N = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	def ano_helper(BCDE):
		BCDE = BCDE + [s - sum(BCDE)]
		BCDE.sort()
		return abs(BCDE[-1] - BCDE[0])
	def helper(BCDEs, inds):
		if len(BCDEs[0]) == 4:
			return BCDEs
		ret_BCDEs = []
		ret_inds = []
		for candidate in range(len(BCDEs)):
			BCDE = BCDEs[candidate]
			ind = inds[candidate]
			ave = sum(A[ind:]) / (5 - len(BCDE))
			temp = 0
			while temp + A[ind] <= ave:
				temp += A[ind]
				ind += 1
			ret_BCDEs.append(BCDE + [temp])
			ret_inds.append(ind)
			if ind <= N - 1:
				ret_BCDEs.append(BCDE + [temp + A[ind]])
				ret_inds.append(ind + 1)
		return helper(ret_BCDEs, ret_inds)
	print(sorted([ano_helper(i[1:]) for i in helper([[0]], [0])])[0])
	return 0
	#BCDE = []
	#ind = 0
	#su = []
	#tempBCDE = [[]]
	#while len(BCDE[-1]) < 4:
	#	temp = 0
	#	ret = []
	#	while temp < (s - su) / (4 - len(BCDE)):
	#		te = A[ind]
	#		temp += te
	#		ret.append(te)
	#		su += te
	#		ind += 1
	#	tempBCDE.append(ret)
	#print(BCDE)
main()

Submission status: Runtime Error

Solution code:
def main():
	N = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	def ano_helper(BCDE):
		BCDE = BCDE + [s - sum(BCDE)]
		BCDE.sort()
		return abs(BCDE[-1] - BCDE[0])
	def helper(BCDEs, inds):
		if len(BCDEs[0]) == 4:
			return BCDEs
		ret_BCDEs = []
		ret_inds = []
		for candidate in range(len(BCDEs)):
			BCDE = BCDEs[candidate]
			ind = inds[candidate]
			ave = sum(A[ind:]) / (5 - len(BCDE))
			temp = 0
			while temp + A[ind] < ave:
				temp += A[ind]
				ind += 1
				if ind == N:
					break
			ret_BCDEs.append(BCDE + [temp])
			ret_inds.append(ind)
			if ind < N:
				ret_BCDEs.append(BCDE + [temp + A[ind]])
				ret_inds.append(ind + 1)
		return helper(ret_BCDEs, ret_inds)
	print(sorted([ano_helper(i[1:]) for i in helper([[0]], [0])])[0])
	return 0
	#BCDE = []
	#ind = 0
	#su = []
	#tempBCDE = [[]]
	#while len(BCDE[-1]) < 4:
	#	temp = 0
	#	ret = []
	#	while temp < (s - su) / (4 - len(BCDE)):
	#		te = A[ind]
	#		temp += te
	#		ret.append(te)
	#		su += te
	#		ind += 1
	#	tempBCDE.append(ret)
	#print(BCDE)
main()

Submission status: Runtime Error

Solution code:
def main():
	N = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	def ano_helper(BCDE):
		BCDE = BCDE + [s - sum(BCDE)]
		BCDE.sort()
		return abs(BCDE[-1] - BCDE[0])
	def helper(BCDEs, inds):
		if len(BCDEs[0]) == 4:
			return BCDEs
		ret_BCDEs = []
		ret_inds = []
		for candidate in range(len(BCDEs)):
			BCDE = BCDEs[candidate]
			ind = inds[candidate]
			ave = sum(A[ind:]) / (5 - len(BCDE))
			temp = 0
			while temp + A[ind] < ave:
				temp += A[ind]
				ind += 1
			ret_BCDEs.append(BCDE + [temp])
			ret_BCDEs.append(BCDE + [temp + A[ind]])
			ret_inds.append(ind)
			ret_inds.append(ind + 1)
		return helper(ret_BCDEs, ret_inds)
	print(sorted([ano_helper(i[1:]) for i in helper([[0]], [0])])[0])
	return 0
	#BCDE = []
	#ind = 0
	#su = []
	#tempBCDE = [[]]
	#while len(BCDE[-1]) < 4:
	#	temp = 0
	#	ret = []
	#	while temp < (s - su) / (4 - len(BCDE)):
	#		te = A[ind]
	#		temp += te
	#		ret.append(te)
	#		su += te
	#		ind += 1
	#	tempBCDE.append(ret)
	#print(BCDE)
main()

Submission status: Runtime Error

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

S = B[N-1]
Q = S/4
p,q,r = 0,0,0
for i in range(N):
	if abs(B[i] - 1*Q)<abs(B[p] - 1*Q):
		p = i
	if abs(B[i] - 2*Q)<abs(B[q] - 2*Q):
		q = i
	if abs(B[i] - 3*Q)<abs(B[r] - 3*Q):
		r = i

p_0 = max(0,p-1)
q_0 = max(0,q-1,p)
r_0 = max(0,r-1,q)
L = [0,0,0,0]
out = S
for i in range(3):
	p = p_0 + i
	for j in range(3):
		q = q_0 + j
		for k in range(3):
			r = r_0 + k
			L = [B[p],B[q]-B[p],B[r]-B[q],B[N-1]-B[r]]
			pre = max(L)-min(L)
			if pre<out:
				if p < q and q < r :
					out = pre

print(out)

Submission status: Runtime Error

Solution code:
#define _USE_MATH_DEFINED
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

//typedef
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef vector<ii> vii;
typedef unsigned long long ull;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
template<typename T,typename Comp=less<T>>
using ordered_set = tree<T,null_type,Comp,rb_tree_tag,tree_order_statistics_node_update>;
//macros
#define sz(x) int((x).size())
#define fi first
#define se second
#define g(i,t) get<i>(t)
#define gcd __gcd
//functions
template<typename T>
T sq(T a) { return a*a; }
template<typename Arg>
Arg min(const Arg& arg) { return arg; }
template<typename Arg,typename ...Args>
auto min(const Arg& arg,const Args&... args)
{
  auto m = min(args...);
  return arg < m ? arg : m;
}
template<typename Arg>
Arg max(const Arg& arg) { return arg; }
template<typename Arg,typename ...Args>
auto max(const Arg& arg,const Args&... args)
{
  auto m = max(args...);
  return arg > m ? arg : m;
}
inline int bcount(int x)
{
  int r=0;
  __asm__ volatile("POPCNT %1, %0;" : "=r"(r) : "r"(x) );
  return r;
}
inline int clz(int x)
{
  int r=0;
  __asm__ volatile("LZCNT %1, %0;" : "=r"(r) : "r"(x) );
  return r;
}
inline int ctz(int x)
{
  int r=0;
  __asm__ volatile("TZCNT %1, %0;" : "=r"(r) : "r"(x) );
  return r;
}
//constants
constexpr ll LINF = 1e18+42;
constexpr ll INF = 1e9+42;
constexpr ll MOD = 1e9+7;
constexpr ld EPS = 1e-9;
//I/O
#ifdef EVAL
ifstream in("input.txt");
ofstream out("output.txt");
#define cin in
#define cout out
#endif
template<typename Arg>
void read(Arg& arg) { cin>>arg; }
template<typename ...Types>
void read(pair<Types...>&);
template<typename ...Types>
void read(tuple<Types...>&);
template<typename ...Types>
void read(vector<Types...>&);
template<typename ...Types>
void read(deque<Types...>&);
template<typename ...Types>
void read(array<Types...>&);
template<typename ...Types>
void read(list<Types...>&);
template<typename ...Types>
void read(forward_list<Types...>&);
template<size_t I=0,typename Tuple>
typename enable_if<I >= tuple_size<Tuple>::value>::type
  read_tuple(Tuple&) {}
template<size_t I=0,typename Tuple>
typename enable_if<I < tuple_size<Tuple>::value>::type
  read_tuple(Tuple& x)
{
  read(get<I>(x));
  read_tuple<I+1>(x);
}
template<typename ...Types>
void read(pair<Types...>& x) { read_tuple(x); }
template<typename ...Types>
void read(tuple<Types...>& x) { read_tuple(x); }
template<typename ...Types>
void read(vector<Types...>& x) { for(typename vector<Types...>::reference i : x) read(i); }
template<typename ...Types>
void read(valarray<Types...>& x) { for(typename valarray<Types...>::reference i : x) read(i); }
template<typename ...Types>
void read(deque<Types...>& x) { for(typename deque<Types...>::reference i : x) read(i); }
template<typename ...Types>
void read(array<Types...>& x) { for(typename array<Types...>::reference i : x) read(i); }
template<typename ...Types>
void read(list<Types...>& x) { for(typename list<Types...>::reference i : x) read(i); }
template<typename ...Types>
void read(forward_list<Types...>& x) { for(typename forward_list<Types...>::reference i : x) read(i); }
template<typename Arg,typename ...Args>
void read(Arg& arg,Args&... args) { read(arg); read(args...); }
template<typename Arg>
void print_var(const Arg& arg) { cout<<arg; }
template<typename ...Types>
void print_var(const pair<Types...>&);
template<typename ...Types>
void print_var(const tuple<Types...>&);
template<typename ...Types>
void print_var(const vector<Types...>&);
template<typename ...Types>
void print_var(const valarray<Types...>&);
template<typename ...Types>
void print_var(const array<Types...>&);
template<typename ...Types>
void print_var(const list<Types...>&);
template<typename ...Types>
void print_var(const forward_list<Types...>&);
template<typename ...Types>
void print_var(const deque<Types...>&);
template<typename ...Types>
void print_var(const set<Types...>&);
template<typename ...Types>
void print_var(const multiset<Types...>&);
template<typename ...Types>
void print_var(const map<Types...>&);
template<typename ...Types>
void print_var(const multimap<Types...>&);
template<typename ...Types>
void print_var(const unordered_set<Types...>&);
template<typename ...Types>
void print_var(const unordered_multiset<Types...>&);
template<typename ...Types>
void print_var(const unordered_map<Types...>&);
template<typename ...Types>
void print_var(const unordered_multimap<Types...>&);
template<typename ...Types>
void print_var(const stack<Types...>&);
template<typename ...Types>
void print_var(const priority_queue<Types...>&);
template<typename ...Types>
void print_var(const queue<Types...>&);
template<size_t I=0,typename Tuple>
typename enable_if<I >= tuple_size<Tuple>::value>::type
  print_tuple(const Tuple&)
{
  if
#if __cplusplus >= 201703
  constexpr
#endif
    (I == 0) cout.put('(');
  cout.put(')');
}
template<size_t I=0,typename Tuple>
typename enable_if<I < tuple_size<Tuple>::value>::type
  print_tuple(const Tuple& x)
{
  if
#if __cplusplus >= 201703
  constexpr
#endif
    (I == 0) cout.put('(');
  else cout.write(", ",2);
  print_var(get<I>(x));
  print_tuple<I+1>(x);
}
template<typename List>
void print_list(const List& x)
{
  cout.put('[');
  bool first = true;
  for(typename List::const_reference i : x)
  {
    if(!first) cout.write(", ",2);
    first = false;
    print_var(i);
  }
  cout.put(']');
}
template<typename Set>
void print_set(const Set& x)
{
  cout.put('{');
  bool first = true;
  for(typename Set::const_reference i : x)
  {
    if(!first) cout.write(", ",2);
    first = false;
    print_var(i);
  }
  cout.put('}');
}
template<typename Map>
void print_map(const Map& x)
{
  cout.put('{');
  bool first = true;
  for(typename Map::const_reference i : x)
  {
    if(!first) cout.write(", ",2);
    first = false;
    print_var(i.first);
    cout.put(':');
    print_var(i.second);
  }
  cout.put('}');
}
template<typename Stack>
void print_stack(const Stack& x)
{
  Stack y(x);
  cout.put('[');
  bool first = true;
  while(!y.empty())
  {
    if(!first) cout.write(", ",2);
    first = false;
    print_var(y.top());
    y.pop();
  }
  cout.put(']');
}
template<typename ...Types>
void print_var(const queue<Types...>& x)
{
  queue<Types...> y(x);
  cout.put('[');
  bool first = true;
  while(!y.empty())
  {
    if(!first) cout.write(", ",2);
    first = false;
    print_var(y.front());
    y.pop();
  }
  cout.put(']');
}
template<typename ...Types>
void print_var(const pair<Types...>& x) { print_tuple(x); }
template<typename ...Types>
void print_var(const tuple<Types...>& x) { print_tuple(x); }
template<typename ...Types>
void print_var(const vector<Types...>& x) { print_list(x); }
template<typename ...Types>
void print_var(const valarray<Types...>& x) { print_list(x); }
template<typename ...Types>
void print_var(const array<Types...>& x) { print_list(x); }
template<typename ...Types>
void print_var(const list<Types...>& x) { print_list(x); }
template<typename ...Types>
void print_var(const forward_list<Types...>& x) { print_list(x); }
template<typename ...Types>
void print_var(const deque<Types...>& x) { print_list(x); }
template<typename ...Types>
void print_var(const set<Types...>& x) { print_set(x); }
template<typename ...Types>
void print_var(const multiset<Types...>& x) { print_set(x); }
template<typename ...Types>
void print_var(const map<Types...>& x) { print_map(x); }
template<typename ...Types>
void print_var(const multimap<Types...>& x) { print_map(x); }
template<typename ...Types>
void print_var(const unordered_set<Types...>& x) { print_set(x); }
template<typename ...Types>
void print_var(const unordered_multiset<Types...>& x) { print_set(x); }
template<typename ...Types>
void print_var(const unordered_map<Types...>& x) { print_map(x); }
template<typename ...Types>
void print_var(const unordered_multimap<Types...>& x) { print_map(x); }
template<typename ...Types>
void print_var(const stack<Types...>& x) { print_stack(x); }
template<typename ...Types>
void print_var(const priority_queue<Types...>& x) { print_stack(x); }
template<typename Arg>
void print(const Arg& arg) { print_var(arg); cout.put('\n'); }
template<typename Arg,typename ...Args>
void print(const Arg& arg,const Args&... args) { print_var(arg); cout.put(' '); print(args...); }
template<typename Arg>
void print_raw(const Arg& arg) { cout<<arg; }
template<typename ...Types>
void print_raw(const pair<Types...>&);
template<typename ...Types>
void print_raw(const tuple<Types...>&);
template<typename ...Types>
void print_raw(const vector<Types...>&);
template<typename ...Types>
void print_raw(const valarray<Types...>&);
template<typename ...Types>
void print_raw(const array<Types...>&);
template<typename ...Types>
void print_raw(const list<Types...>&);
template<typename ...Types>
void print_raw(const forward_list<Types...>&);
template<typename ...Types>
void print_raw(const deque<Types...>&);
template<typename ...Types>
void print_raw(const set<Types...>&);
template<typename ...Types>
void print_raw(const multiset<Types...>&);
template<typename ...Types>
void print_raw(const map<Types...>&);
template<typename ...Types>
void print_raw(const multimap<Types...>&);
template<typename ...Types>
void print_raw(const unordered_set<Types...>&);
template<typename ...Types>
void print_raw(const unordered_multiset<Types...>&);
template<typename ...Types>
void print_raw(const unordered_map<Types...>&);
template<typename ...Types>
void print_raw(const unordered_multimap<Types...>&);
template<typename ...Types>
void print_raw(const stack<Types...>&);
template<typename ...Types>
void print_raw(const priority_queue<Types...>&);
template<typename ...Types>
void print_raw(const queue<Types...>&);
template<size_t I=0,typename Tuple>
typename enable_if<I >= tuple_size<Tuple>::value>::type
  print_raw_tuple(const Tuple&) {}
template<size_t I=0,typename Tuple>
typename enable_if<I < tuple_size<Tuple>::value>::type
  print_raw_tuple(const Tuple& x)
{
  if
#if __cplusplus >= 201703
  constexpr
#endif
    (I != 0) cout.put(' ');
  print_raw(get<I>(x));
  print_raw_tuple<I+1>(x);
}
template<typename List>
void print_raw_list(const List& x)
{
  bool first = true;
  for(typename List::const_reference i : x)
  {
    if(!first) cout.put(' ');
    first = false;
    print_raw(i);
  }
}
template<typename Stack>
void print_raw_stack(const Stack& x)
{
  Stack y(x);
  bool first = true;
  while(!y.empty())
  {
    if(!first) cout.put(' ');
    first = false;
    print_raw(y.top());
    y.pop();
  }
}
template<typename ...Types>
void print_raw(const queue<Types...>& x)
{
  queue<Types...> y(x);
  bool first = true;
  while(!y.empty())
  {
    if(!first) cout.put(' ');
    first = false;
    print_raw(y.front());
    y.pop();
  }
}
template<typename ...Types>
void print_raw(const pair<Types...>& x) { print_raw_tuple(x); }
template<typename ...Types>
void print_raw(const tuple<Types...>& x) { print_raw_tuple(x); }
template<typename ...Types>
void print_raw(const vector<Types...>& x) { print_raw_list(x); }
template<typename ...Types>
void print_raw(const valarray<Types...>& x) { print_raw_list(x); }
template<typename ...Types>
void print_raw(const array<Types...>& x) { print_raw_list(x); }
template<typename ...Types>
void print_raw(const list<Types...>& x) { print_raw_list(x); }
template<typename ...Types>
void print_raw(const forward_list<Types...>& x) { print_raw_list(x); }
template<typename ...Types>
void print_raw(const deque<Types...>& x) { print_raw_list(x); }
template<typename ...Types>
void print_raw(const set<Types...>& x) { print_raw_list(x); }
template<typename ...Types>
void print_raw(const multiset<Types...>& x) { print_raw_list(x); }
template<typename ...Types>
void print_raw(const map<Types...>& x) { print_raw_list(x); }
template<typename ...Types>
void print_raw(const multimap<Types...>& x) { print_raw_list(x); }
template<typename ...Types>
void print_raw(const unordered_set<Types...>& x) { print_raw_list(x); }
template<typename ...Types>
void print_raw(const unordered_multiset<Types...>& x) { print_raw_list(x); }
template<typename ...Types>
void print_raw(const unordered_map<Types...>& x) { print_raw_list(x); }
template<typename ...Types>
void print_raw(const unordered_multimap<Types...>& x) { print_raw_list(x); }
template<typename ...Types>
void print_raw(const stack<Types...>& x) { print_raw_stack(x); }
template<typename ...Types>
void print_raw(const priority_queue<Types...>& x) { print_raw_stack(x); }
template<typename Arg,typename ...Args>
void print_raw(const Arg& arg,const Args&... args) { print_raw(arg); print_raw(args...); }
#ifdef DEBUG
void print_dbg(string) { cout.put('\n'); }
template<typename Arg,typename ...Args>
void print_dbg(string name,const Arg& arg,const Args&... args)
{
  typename string::size_type idx = 0;
  for(stack<char> stk; idx<name.size() && (name[idx]!=',' || !stk.empty()); ++idx)
  {
    if(name[idx]=='\\')
    {
      ++idx;
      continue;
    }
    if(name[idx]=='\'' || name[idx]=='\"')
    {
      if(!stk.empty() && stk.top()==name[idx])
        stk.pop();
      else
        stk.push(name[idx]);
    }
    if((stk.empty() || (stk.top()!='\'' && stk.top()!='\"')) && (name[idx]=='{' || name[idx]=='('))
      stk.push(name[idx]);
    if(name[idx]==')' || name[idx]=='}')
      stk.pop();
  }
  print_raw(name.substr(0,idx),": ");
  print(arg);
  print_dbg(name.substr(idx==name.size() ? 0 : idx+1),args...);
}
#define dbg(...) print_dbg(#__VA_ARGS__,__VA_ARGS__)
#else
#define dbg(...) asm("nop")
#endif
template<typename ...Args>
void print_case(size_t t,const Args&... args) { cout<<"Case #"<<t<<": "; print_raw(args...); cout.put('\n'); }
// END I/O

int main()
{
  int N; read(N);
  vector<ll> V(N);
  read(V);
  vector<ll> T(V);
  sort(T.begin(),T.end());
  ll r = LINF;
  for(int j=(N-1)/2; j<=(N+1)/2; j++)
  {
    ll b = T[j]-j;
    ll t = 0;
    for(int i=0; i!=N; i++)
      t += V[i] > (b+i) ? V[i]-(b+i) : (b+i)-V[i];
    r = min(r,t);
  }
  print(r);
  return 0;
}