题目描述

三个好朋友正在分蛋糕。

一共有 n 个不同大小的蛋糕，现要将这 n 个蛋糕分给三个人（蛋糕不能切），每个人的愉悦程度定义为这个人拿到的蛋糕数。

找到一种方法使得愉悦度的最大值与最小值之差尽可能小。

输入格式

第一行输入一个整数 n，表示蛋糕总数。

第二行输入 n 个整数 $a_i$，表示每个蛋糕的大小。

输出格式

输出最优方案中，分到蛋糕最多的人与蛋糕最少的人之差。

样例

5
1 3 2 2 4

0

6
3 2 5 2 4 3

1

10
20 1 15 17 11 2 15 3 16 3

1

限制与数据范围

对于30%的数据, $1 \leq n \leq 10$

对于另外20%的数据, $1 \leq a_i \leq 3$

对于另外20%的数据，$1 \leq a_i \leq 10$

对于100%的数据，$3 \leq n \leq 25, 1 \leq a_i \leq 10^7$