### 问题描述 在一个繁荣的城市里，有三个商家经营着自己的卡牌制作工坊。这个城市非常富有，人们喜欢收集各种卡牌，比如魔法卡、机器卡等等。 有一天，城市里即将举办一场卡牌大展，吸引了全城的卡牌爱好者。商家们想要为此做好准备。 他们知道会有 $n$ 个人前来工坊，请求制作自己定制的卡牌。由于每个人的喜好不同，可能会想要不同的卡牌。为了简单起见，我们将第 $i$ 个人想要的卡牌类型表示为 $a_i$。 每个商家可以提前选择一个整数类型 $x(1\leq x\leq 10^9)$，不同的商家可以选择不同的类型。在为展览做准备期间，商家将完善制作所选类型的技巧，这将使他们能够立即制作相应的卡牌。对于已经选择类型为 $x$ 的商家来说，制作类型为 $y$ 的卡牌需要的时间为 $|x-y|$，因为卡牌与所选类型越相似，商家就越容易完成制作。 到了展览当天，每当下一个人前来工坊请求制作卡牌，商家们就可以选择谁来接受这个工作。同时，商家们非常熟练，可以同时为不同的人工作。 由于人们不喜欢等待，商家们想要选择最佳的类型来进行准备，以便所有人的最大等待时间尽可能短。请输出商家们能够实现的最佳最大等待时间。 ### 输入格式 第一行包含一个整数 $t$，表示测试用例的数量。 接下来是 $t$ 个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$，表示前来工坊请求制作卡牌的人数。 每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,a_3,\ldots,a_n$，表示每个人想要的卡牌类型。 ### 输出格式 输出 $t$ 个数字，每个数字是相应测试用例的答案，即商家们能够实现的最佳最大等待时间。 ### 样例输入 ```txt 5 6 1 7 7 9 9 9 6 5 4 2 1 30 60 9 14 19 37 59 1 4 4 98 73 1 2 6 3 10 1 17 15 11 ``` ### 样例输出 ```txt 0 2 13 0 1 ``` ### 样例说明 在第一个例子中，木匠们可以分别选择图案 $1$、$7$、$9$ 进行准备。 在第二个例子中，木匠们可以分别选择图案 $3$、$30$、$60$ 进行准备。 在第三个例子中，木匠们可以分别选择图案 $14$、$50$、$85$ 进行准备。 ### 评测数据规模 对于 $100$% 的评测数据，$1\leq t\leq 10,1\leq n\leq 2\times 10^5 ,1\leq a_i \leq 10^9$。