由于某些原因，本体暂不开启捆绑。

题目描述

你有一个 $n$ 个数的序列 $\lbrace a_i\rbrace$，你需要将序列划分为若干段，保证每一段的长度为 $1$ 或 $2$。定义每一段的权值是段内数的和，你需要最小化所有权值的极差。

输入格式

第一行一个正整数 $n$ 表示猫猫的个数。

第二行 $n$ 个正整数 $a_i$ 表示第 $i$ 只猫猫的可爱程度。

输出格式

一行一个正整数表示答案。

样例 1

10
8 6 3 4 9 2 7 2 9 3

6

样例解释 1

分组方式为 $[8],[6],[3,4],[9,2],[7,2],[9,3]$，此时 $b_1=8,b_2=6,b_3=7,b_4=11,b_5=9,b_6=12$。此时极差为 $b_6-b_2=12-6=6$。

样例 2/3/4

见下发文件中 cccix/cccix*.in 与 cccix/cccix*.out。

数据范围

本题采用捆绑测试。

• Subtask 1（5 pts）：$n\leq 5$。
• Subtask 2（5 pts）：$a_i$ 均相等。
• Subtask 3（15 pts）：$n \leq 15$。
• Subtask 4（25 pts）：$n \leq 10^3$。
• Subtask 5（50 pts）：无特殊限制。

对于所有数据，$1 \leq n \leq 10^5$，$1 \leq a_i \leq 10^9$。