Minimizing Difference in Team Powers

DreamGrid and BaoBao are playing a game. There are \(n\) soldiers in the game numbered from \(1\) to \(n\). The \(i\)th soldier has a power value of \(a_i\). They must partition these soldiers into teams following these rules:

• A team consists of either 1 or 2 soldiers.
• Every soldier must belong to exactly one team.
• If a team contains 2 soldiers, and they are the \(i\)th and \(j\)th soldiers, then \(|i - j| = 1\) (i.e. they must be consecutive).

The power value of a team is defined as the sum of its members' power values. For fairness, they want to minimize the difference between the maximum team power value and the minimum team power value over all teams. Formally, if the team powers are \(p_1, p_2, \dots, p_k\), you need to partition the soldiers so that the value

\[ \Delta = \max_{1 \le i \le k} p_i - \min_{1 \le i \le k} p_i \]

is minimized. Compute and output the minimum possible \(\Delta\).

inputFormat

The first line contains a single integer \(n\) (the number of soldiers).

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) representing the power values of the soldiers.

outputFormat

Output a single integer --- the minimum possible difference between the maximum and minimum team power values among all valid partitions.

sample

3
1 2 3

0

</p>