T3 划分划分

时间：$1s$

空间：$256M$

题目描述

小$W$ 有一个 $n$ 个元素的序列 { $a$ }，请你找到三元组 $1\le i<j<k< n$。

记录 $A=a_1+a_2+...+a_i$，$B=a_{i+1}+a_{i+2}+...+a_j$，$C=a_{j+1}+a_{j+2}+...+a_k$，$D=a_{k+1}+a_{k+2}+...+a_n$。

令 $A,B,C,D$ 中的最大值为 $E$，$A,B,C,D$ 中的最小值为 $F$，要求最小化并输出 $E-F$ 的值。

输入格式

第一行包含一个正整数 $n$ $(4≤𝑛≤500)$，表示数组中元素个数。

第二行包含 $n$ 个正整数 $a_1,a_2,a_3,...,a_n$（$-10^9≤a_i≤10^9$）

输出格式

输出一行，包含一个整数，表示答案。

5
3 2 4 1 2

2

10
10 71 84 33 6 47 23 25 52 64

36

样例提示

样例 $1$ ：最小的划分方案之一为$[3],[2],[4],[1,2]$