单点时限: 1.0 sec
内存限制: 1024 MB
对于一个长度为 $n$ 的数组，其合法划分需要将数组划分成若干个区间并满足以下条件：
例如 $n=5$ 时，${[1,2],[3,3],[4,5] }$，${[1,3],[4,5] }$ 就是合法的划分，而 ${[1,2],[4,5] }$，${[1,5] }$ 就是不合法的划分。
Antiamuny 定义一个区间的价值为区间内所有元素之和，一个划分的优秀值为划分内的最大区间价值和最小区间价值之差。
现在，Antiamuny 想知道，对于给定的数组可以得到的最小的优秀值是多少，请你写个程序帮帮他。
第一行包含一个整数 $n$ ($2 \leq n \leq 100$)，表示数组的长度。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^6$)，中间以空格分隔，分别表示数组的每个元素。
在一行输出一个整数，表示可以得到的最小的优秀值。
6 3 1 4 5 3 1
1
8 3 7 6 9 1 2 4 9
4
样例一： ${[1,3],[4,6]}$ 是一个可行的划分,各个区间的价值分别为 $8,9$ 。
样例二： ${[1,2],[3,3],[4,4],[5,7],[8,8]}$ 是一个可行的划分，各个区间的价值分别为 $10,6,9,7,9$ 。