该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

1、每个人负责的区间必须是连续的

2、三个人的工作量极差值要最小（极差值：最大值与最小值的差）

3、三个人一定要把n块区域的工作都处理完

输入格式

第一行：1个正整数 $n$

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

输出格式

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

样例输入/输出

5
2 2 3 6 5

2

样例1解释：划分结果为[2，2，3] ，[6]，[5]，容易检验该分配结果的极差值(2 + 2 + 3) - 5 = 2是最小的

数据规模与提示

对于40%的数据，$3 ≤ n ≤ 300$；

对于100%的数据，$3 ≤ n ≤ 5000，1 ≤ a_i ≤ 10$；