给你一个长度为 $$$n$$$ 的数组 $$$a$$$。对于整数 $$$k$$$,我们称其为 小猪 当且仅当可以通过执行任意次数(可能为零)以下操作以非降序对 $$$a$$$ 进行排序:
- 首先,选择两个索引 $$$i$$$ 和 $$$j$$$ ($$$1 \le i \lt j \le n$$$) 使得 $$$|a_i - a_j| \ge k$$$;
- 然后,交换 $$$a_i$$$ 和 $$$a_j$$$。
你需要确定最大的 小猪 整数$$$k$$$。如果这样的整数不存在,则输出$$$-1$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — $$$a$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。
输出
对于每个测试用例,输出一个整数 - 最大的 小猪 整数$$$k$$$。
如果这样的整数不存在,则输出$$$-1$$$。
示例
输入复制
51151 2 3 4 531 4 252 1 5 4 361 1 4 5 1 4
输出复制
-1-1223
注意
在第一个和第二个测试用例中,无论 $$$k$$$ 有多大,您始终可以通过不执行任何操作来按非降序对 $$$a$$$ 进行排序。
在第三个测试用例中,最大的 小猪 $$$k$$$ 是 $$$2$$$。我们可以在第一个操作中选择 $$$i=2$$$ 和 $$$j=3$$$,因为 $$$|a_2-a_3|=|4-2|=2 \ge k$$$,并且 $$$a$$$ 按非降序排序。可以证明没有 小猪 存在大于 $$$2$$$ 的整数。