题目描述

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

输入格式

第一行一个数 $n$。

下一行为这个序列里面的 $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 \le n \le 2 \times 10^5$
• 序列内数都是正整数，且小于等于 $10^9$