题目描述

王老师有一个长度为 $N$ 的序列 $A$。

他将执行三次剪切操作，将 $A$ 序列分割成四个非空连续子序列 $B, C, D, E$，剪切点可以随意选择。

$P, Q, R, S$ 分别表示序列 $B, C, D, E$ 的元素之和，当 $P, Q, R, S$ 中的最大值与最小值的差值越小，王老师就越兴奋。请你设计一种分割方法，使得王老师兴奋到极点。

输入格式

第一行一个正整数 $N (4 \le N \le 2 \times 10^5)$。

第二行 $N$ 个正整数 $A_i (1 \le A_i \le 10^9)$。

输出格式

输出王老师兴奋到极点时，$P, Q, R, S$ 中的最大值与最小值的差值。

5
3 2 4 1 2

2

剪切方法为 $(3), (2), (4), (1, 2)$，$P = 3, Q = 2, R = 4, S = 1 + 2 = 3$，最大值与最小值的差值为 $2$。可以证明，王老师不可能更兴奋了。

10
10 71 84 33 6 47 23 25 52 64

36

7
1 2 3 1000000000 4 5 6

999999994