题目描述

给定一个序列。要求把这个序列分成连续的四份，记这四份内数字和分别为 $a,b,c,d$ ，最小化 $a,b,c,d$ 的极差。

输入格式

第一行输入 $N$

第二行输入 $A_1$ $A_2$ $...$ $A_N$

输出格式

输出一个整数代表四段的极差。

5
3 2 4 1 2

2

10
10 71 84 33 6 47 23 25 52 64

36

7
1 2 3 1000000000 4 5 6

999999994

提示

• $4\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ A_i\ \leq\ 10^9$

样例 1 解释

$a,b,c,d=(3),(2),(4),(1,2)$ 时极差最小。