【CZYZOI 2017.04.20 B】 game

内存限制: 256 MiB 时间限制: 1000 ms
标准输入输出

题目描述

Alice和Bob发明了一种新的博弈游戏。

给出长度为 nn 的数列 v[1..n]v[1..n] ,Alice先手Bob后手依次删除其中的一个元素直到只剩下 22 个元素 aabbans=abans=|a-b|

Alice希望 ansans 尽可能小而Bob希望 ansans 尽可能大。

请问Alice能取得的答案最小值是多少。

输入格式

第一行一个整数 nn 表示初始的数字个数。

接下来一行 nn 个数,v[i]v[i] 表示第 ii 个初始的数字

输出格式

仅一行,输出一个整数表示Alice能取得的答案最小值。

样例

输入样例1

6
0 1 7 3 31 15

输出样例1

7

输入样例2

2
73 37

输出样例2

36

数据范围与提示

对于 20%20\% 的数据,n10n\le10

对于 100%100\% 的数据 n200000n\le200000n and 1=0n \ and \ 1=00x[i]1090\le x[i]\le10^9