Minimizing the Instability of High‐Level Paladins

You are given n high–level paladins numbered from \(1,2,\dots,n\). Each paladin has a spiritual energy value \(a_i\). A positive \(a_i\) means that the paladin has \(a_i\) points more energy than optimal, while a negative \(a_i\) means that the paladin needs \(-a_i\) points more energy to reach peak performance.

You may repeatedly perform the following energy transmission operation on any paladin \(i\) with \(2\le i\le n-1\):

\[ (a_{i-1},a_i,a_{i+1})\leftarrow(a_{i-1}+a_i,\;-a_i,\;a_{i+1}+a_i)\]

In other words, if \(a_i\ge0\) then paladins \(i-1\) and \(i+1\) each extract \(a_i\) points of energy from paladin \(i\); if \(a_i.

The instability of a group of paladins is defined as \[ \max_{1\le i\le n}{\{|a_i|\}}. \] Your goal is to use the operation as many times as you like (in any order) to minimize the instability. That is, choose a sequence of operations so that when no more operations are performed the maximum absolute value among all the paladins' energies is as small as possible.

Note: The energy transmission operation affects three consecutive paladins by flipping the central paladin’s energy (i.e. multiplying by \(-1\)) and adding the (original) energy of the operated paladin to its two immediate neighbours. Only paladins \(2,3,\dots,n-1\) can be chosen for the operation.

inputFormat

The first line contains an integer \(n\) (1 \(\le n\le\) small as allowed by your algorithm) --- the number of paladins.

The second line contains \(n\) integers \(a_1,a_2,\dots,a_n\) (each \(|a_i|\) can be large), representing the initial energy values.

outputFormat

Output a single integer: the minimal possible instability \(\max_{1\le i\le n} |a_i|\) achievable after an arbitrary number of energy transmission operations.

sample

3
-5 2 4

4