题目描述

ak机所在的游戏公司准备在年会上开展抽奖活动。他们购买了若干个奖品，每个奖品都有一个价格，用一个正整数数组表示。在抽奖环节，公司准备设置一等奖、二等奖和三等奖，每个等级设置一个奖品，并将所有奖品分成三份大礼包。公司希望尽可能地减小一等奖和三等奖之间的价格差异，同时满足一等奖总价格大于二等奖总价格，二等奖总价格大于三等奖总价格。

为了实现这一目标，公司需要找到一种合适的分配方案。具体来说，假设一等奖总价格为 $x$，二等奖总价格为 $y$，三等奖总价格为 $z$，则 $x>y>z>0$。同时，假设奖品的总数量为 $n$，用正整数数组 $array$ 表示每个奖品的价格。

现在的问题是他们不知道如何分配奖品，才能使得一等奖和三等奖之间的价格差最小，你能帮帮他们吗？

输入描述

第一行：正整数 $n(3\le n\le 15)$ ，表示奖品的数量

第二行：$n$个整数 $array[i](1\le array[i]\le 10^4)$ ，表示每件奖品的价格

输出描述

一个非负整数，表示一等奖和三等奖的差值，没有方案返回 $0$

样例

样例1

输入

3
5 4 2

输出

3

样例解释

分配方案只有一种[5,4,2]

样例2

输入

4
10 5 4 2

输出

5

样例解释

分配方案有 [10,9,2}] ， [10,7,4] ， [10,6,5] ，[15,4,2] ， [14,5,2] ， [12,5,4]
一等奖和三等奖差值最小的方案是 [10,6,5]