只有地藏知晓的哀叹

• 时间限制：1.5 秒
• 内存限制：256 MB

题目描述

戎璎花正在玩垒石头的游戏。她把 n 堆石子摆成一排，其中第 i 堆里有 a_i 颗石子。魂魄妖梦给了她一个严格递增的序列 b_1, b_2, …, b_n，并希望她让 n 堆石子的数量序列恰好变成 b_1, b_2, …, b_n，即最终第 i 堆的石子数必须等于 b_i。

戎璎花分以下两个阶段完成这个过程：

阶段一（加石子）： 她可以在任意一堆石子中添加任意数量的石子。形式上，对每一堆 i，她选择一个非负整数 x_i，将 a_i 替换为 a_i + x_i。

阶段二（交换）： 她可以重复交换相邻的两堆石子。形式上，她可以执行任意多次（可能为零次）如下操作：选择一个满足 1 ≤ i ≤ n−1 的索引 i，交换 a_i 与 a_{i+1} 的值。

如果在两个阶段结束后，石子数量序列恰好等于 b_1, b_2, …, b_n，则称这个过程是有效的。

求所有有效过程中，阶段二所需操作次数的最小值。如果不存在有效过程，则输出 −1。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 t（1 ≤ t ≤ 2000），表示测试用例的数量。

每个测试用例的格式如下：

• 第一行包含一个整数 n（1 ≤ n ≤ 2000）——石子的堆数；
• 第二行包含 n 个整数 a_1, a_2, …, a_n（1 ≤ a_i ≤ 10^9）——每堆石子的初始数量；
• 第三行包含 n 个整数 b_1, b_2, …, b_n（1 ≤ b_1 < b_2 < … < b_n ≤ 10^9）——每堆石子的目标数量。

保证所有测试用例的 n 之和不超过 2000。

输出格式

对每个测试用例，输出一行一个整数——在所有有效过程中，阶段二可能执行的最小操作次数；如果不存在有效过程，则输出 −1。

样例

输入：

10
3
1 2 2
1 3 5
3
2 2 1
1 2 3
2
5 1
2 4
6
6 5 4 3 2 1
1 2 3 4 5 6
7
4 7 1 6 2 5 3
1 2 3 4 5 6 7
2
2 1
2 3
4
3 2 2 1
1 2 3 4
4
4 3 2 1
1 3 4 5
5
1 5 4 3 2
2 3 4 5 6
5
10 3 8 6 9
3 6 8 9 10

输出：

0
2
-1
15
12
0
4
4
3
5

样例解释

测试用例 1： 只需要阶段一。取 x_1 = 0, x_2 = 1, x_3 = 3，石子堆变成 1, 3, 5。不需要交换，所以答案是 0。

测试用例 2： 两个阶段都需要。取 x_1 = 0, x_2 = 1, x_3 = 0，石子堆变成 2, 3, 1；然后进行两次交换：[2,3,1] → [2,1,3] → [1,2,3]。带 1 颗石子的那堆必须从第 3 个位置移到第 1 个位置，至少需要两次交换，因此答案是 2。

测试用例 3： 无解。第 1 堆最初有 5 颗石子，而目标序列中的每个数都不超过 4；由于只能加石子不能减，这堆石子不可能等于目标序列中的任何数。因此答案为 −1。

测试用例 4： 不需要加石子，只要把石子堆重新排成递增顺序。相邻交换的最少次数为 15。

测试用例 5： 同样不需要加石子，只要把石子堆重新排序。相邻交换的最少次数为 12。