CF2237B Annoying the Ghost

Ja the Ghost 在玩橡皮鸭。 他有 $n$ 堆橡皮鸭排成一排，第 $i$ 堆中有 $a_i$ 只鸭子。Quack the Duck 给 Ja 一个严格递增的序列 $b_1, b_2, \ldots, b_n$ 并命令他把这 $n$ 堆橡皮鸭变为这个序列。 Ja 的操作过程分为两个阶段： 1. 他可以往每一堆中加入任意数量的鸭子。具体而言，对每一堆 $i$，他可以选择一个非负整数 $x_i$，将 $a_i$ 替换为 $a_i + x_i$。 2. 他可以反复交换两堆相邻的橡皮鸭。具体而言，他可以进行如下操作若干次（可以为零次）：选择一个下标 $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 < b_2 < \cdots < b_n \le 10^9$），表示目标序列。 保证所有测试数据的 $n$ 之和不超过 $2000$。

对每组测试数据输出一行，每行一个整数——所有合法过程中第二阶段最少的操作次数。如果无法完成，输出 $-1$。

在第一个测试用例中，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] $$ 只有一只鸭子的那堆需要从第三个位置移动到第一个位置，最少需要两次交换，所以答案为 $2$。 在第三个测试用例中，无法完成。第一堆初始有 $5$ 只鸭子，而目标序列中每个数最大为 $4$。由于 Ja 只能添加橡皮鸭，不能减少，所以无法让这堆等于目标中任意一个数。因此答案为 $-1$。 在第四个测试用例中，无需添加鸭子，只需要将橡皮鸭堆按递增序列重新排序，将需要 $15$ 次相邻交换。 在第五个测试用例中，同样不用加鸭子，最少需要 $12$ 次相邻交换。 由 ChatGPT 5 翻译