时空限制

时间限制 $1\text{s}$，内存限制 $512\text{MB}$。

题目描述

给定长度为 $n$ 的序列 $\{a\}$，请你找到三元组 $1 \leq i < j < k \leq n$。

记录 $A=a_1+... + a_i$，$B=a_{i+1}…+a_{j-1}$，$C=a_{j+1}+…+a_{k-1}$，$D=a_k+…+a_n$​。

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

输入格式

第一行包含 $1$ 个正整数，表示 $n$。

第二行包含 $n$ 个正整数，第 $i$ 个正整数表示 $a_i$。

输出格式

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

输入样例1

5
3 2 4 1 2

样例输出1

2

样例解释1

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

输入样例2

10
10 71 84 33 6 47 23 25 52 64

输出样例2

36

数据范围

对于 $20\%$ 的数据，$1 \leq n \leq 100$。

对于 $60\%$ 的数据，$1 \leq n \leq 1000$​。

对于 $100\%$ 的数据，$1 \leq n \leq 10^5,1 \leq a_i \leq 10^9$。