幽灵 Ja 正在玩橡皮鸭。他将 $$$n$$$ 堆橡皮鸭排成一排,其中第 $$$i$$$ 堆包含 $$$a_i$$$ 鸭子。嘎嘎鸭给了贾一个 严格增加 序列 $$$b_1,b_2,\ldots,b_n$$$ 并命令他使桩 $$$a_1,a_2,\ldots,a_n$$$ 恰好变成这个序列。
Ja 分以下两个阶段执行该过程:
- Ja 可以向每堆添加任意数量的鸭子。
正式地,对于每堆 $$$i$$$,他选择一个非负整数 $$$x_i$$$ 并将 $$$a_i$$$ 替换为 $$$a_i+x_i$$$。
- Ja 可以重复交换相邻的两堆。
正式地,他可以执行以下操作任意次数,可能为零:选择一个索引$$$i$$$,使得$$$1\le i\le n-1$$$,并交换$$$a_i$$$和$$$a_{i+1}$$$的值。
一个进程被调用 有效 如果两个阶段结束后,堆大小的序列恰好是$$$b_1,b_2,\ldots,b_n$$$。
找出在 第二阶段 其中 有效 进程。如果没有 有效 进程,输出$$$-1$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 2000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2000$$$) — 橡皮鸭的堆数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$) — 每堆橡皮鸭的初始数量。
第三行包含 $$$n$$$ 整数 $$$b_1,b_2,\ldots,b_n$$$ ($$$1\le b_1 \lt b_2 \lt \cdots \lt b_n\le 10^9$$$) — 每堆橡皮鸭的最终数量。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。
输出
对于每个测试用例,输出一个整数 - 在测试用例中执行的最小可能操作数 第二阶段 其中 有效 进程。如果没有 有效 进程,输出$$$-1$$$。
示例
输入复制
1031 2 21 3 532 2 11 2 325 12 466 5 4 3 2 11 2 3 4 5 674 7 1 6 2 5 31 2 3 4 5 6 722 12 343 2 2 11 2 3 444 3 2 11 3 4 551 5 4 3 22 3 4 5 6510 3 8 6 93 6 8 9 10
输出复制
02-1151204435
注意
在第一个测试用例中,Ja 只需要第一阶段。他可以设置$$$x_1=0,x_2=1,x_3=3$$$,这样一堆堆就变成了$$$1,3,5$$$。不需要交换,所以答案是$$$0$$$。
在第二个测试用例中,Ja 需要两个阶段。他可以设置$$$x_1=0,x_2=1,x_3=0$$$,这样堆就变成了$$$2,3,1$$$。然后他可以执行两次交换: $$[2,3,1]\to [2,1,3]\to [1,2,3].$$ 带有 $$$1$$$ 鸭子的堆必须从第三个位置移动到第一个位置,因此至少需要两次交换。因此答案是$$$2$$$。
在第三个测试用例中,这是不可能的。第一堆最初包含 $$$5$$$ 鸭子,但目标序列中的每个数字最多为 $$$4$$$。由于 Ja 只能添加鸭子而不能删除它们,因此该堆不能等于目标序列中的任何数字。因此答案是$$$-1$$$。
在第四个测试用例中,不需要添加鸭子。 Ja 只需要将这些堆重新排序为递增的顺序。相邻交换的最小数量为$$$15$$$。
在第五个测试用例中,不需要添加鸭子。同样,Ja 只需要将这些堆重新排序为递增的顺序。相邻交换的最小数量为 $$$12$$$。