平分

• 题目描述

给出一个长度为 $n$ 的数组 $a$ ，然后把它分成非空四个部分 $\text B$ 、$\text C$ 、$\text D$ 、$\text E$ ，四个部分的和分别为 $\text P$ 、$\text Q$ 、 $\text R$ 、$\text S$ ，现在的目标是如何分成四个部分，使得 $\text {max \{P,Q,R,S\}-min\{P,Q,R,S\}}$ 的值最小。

• 输入

第一行两个整数 $\text N$（ $1 \le N \le 10^6$）。

第二行N个正整数 $a_i$，其中 $1 \le ai \le 10^9$。

• 输出

一行一个整数，表示所求答案。

• 样例输入

【样例输入1】

5
3 2 4 1 2

【样例输入2】

10
10 71 84 33 6 47 23 25 52 64

【样例输入3】

7
1 2 3 1000000000 4 5 6

• 样例输出

【样例输出1】

2

【样例输出2】

36

【样例输出3】

999999994

• 提示

【样例1解释】 分成四部分为 $\text{ B=\{3\}, C=\{2\}, D=\{4\}, E=\{1, 2\}}$,最大值为 $4$ ，最小值为 $2$ ，所以差值为 $4-2=2$。