题目描述

黄师傅、叶师傅、陈师傅三位粉刷匠，最近接到一项任务安排，要求对街道的某一面墙进行粉刷维护，为此他们需要合理分配好负责的区域；

可以将这面墙横向分划成 $n$ 块区域，每一块区域由于高低等问题，所需要的工作量也不同，所以需要你帮他们划分好各自的工作区间，但有如下规则：

1. 每个人负责的区间必须是连续的
2. 三个人的工作量极差值要最小（极差值：最大值与最小值的差）
3. 三个人一定要把 $n$ 块区域的工作都处理完

输入格式

第一行：一个正整数 $n$
第二行：$n$ 个正整数 $a_i$，依次表示从左到右每一块区域的工作量

输出格式

一个正整数，表示三个人工作量的最小极差值

样例

5
2 2 3 6 5

2

样例解释
划分结果为 $[2, 2, 3]$，$[6]$，$[5]$，工作量和分别为 $7$、$6$、$5$，极差值为 $7 - 5 = 2$，这是最小的极差值。

数据范围

• 对于 $40\%$ 的数据：$3 \le n \le 300$；
• 对于 $100\%$ 的数据：$3 \le n \le 5000$，$1 \le a_i \le 10$。