单点时限: 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≤n≤100)，表示数组的长度。
第二行包含 n 个整数 a1,a2,…,an (1≤ai≤106)，中间以空格分隔，分别表示数组的每个元素。
在一行输出一个整数，表示可以得到的最小的优秀值。
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 。