时空限制

2S/512M

题目描述

有 $n$ 根木棒，第 $i$ 根木棒的长度为 $l_i$，强度为 $a_i$。

你需要从中选择下标互不相同的三根木棒。如果它们的长度能够围成一个非退化三角形，则称这次选择是合法的。这里，非退化三角形是指任意两边长度之和严格大于第三边。

一次合法选择的不稳定度定义为所选三根木棒中最大强度与最小强度之差。

请你求出所有合法选择中的最小不稳定度。若不存在合法选择，输出 $-1$。

格式

输入格式

本题包含多组测试用例。

第一行包含一个正整数 $T$，表示测试用例的数量。

对于每组测试用例：

• 第一行包含一个整数 $n$，表示木棒数量；
• 第二行包含 $n$ 个正整数 $l_1, l_2, \dots, l_n$，表示每根木棒的长度；
• 第三行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示每根木棒的强度。

输出格式

对于每组测试用例，输出一行一个整数，表示最小不稳定度；若不存在合法选择，输出 $-1$。

样例

样例输入 #1

4
5
1 2 3 4 10
1 2 4 7 8
4
1 1 2 3
5 2 9 4
5
2 3 4 5 100
7 7 7 7 1
7
1 2 8 9 10 20 21
1 100 20 23 25 28 30

样例输出 #1

5
-1
0
5

样例解释 #1

对于第一组测试用例，选择长度分别为 $2,3,4$ 的三根木棒，可以围成一个非退化三角形。它们的强度分别为 $2,4,7$，因此不稳定度为 $7-2=5$，且不存在不稳定度更小的合法选择。

对于第二组测试用例，不存在能够围成非退化三角形的三根木棒，因此输出 $-1$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，满足 $1 \le T \le 10^4$，$3 \le n \le 2 \times 10^5$，$1 \le l_i, a_i \le 10^9$，所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。