CF2237B.Annoying the Ghost

Ja the Ghost is playing with rubber ducks. He has $n$ piles of rubber ducks arranged in a row, where the $i$-th pile contains $a_i$ ducks. Quack the Duck gives Ja a strictly increasing sequence $b_1,b_2,\ldots,b_n$ and commands him to make the piles $a_1,a_2,\ldots,a_n$ become exactly this sequence.

Ja performs the process in the following two stages:

1. Ja may add any number of ducks to each pile.

   Formally, for each pile $i$, he chooses a non-negative integer $x_i$ and replaces $a_i$ with $a_i+x_i$.

2. Ja may repeatedly swap two adjacent piles.

   Formally, he may perform the following operation any number of times, possibly zero: choose an index $i$ such that $1\le i\le n-1$, and swap the values of $a_i$ and $a_{i+1}$.

A process is called valid if, after both stages end, the sequence of pile sizes is exactly $b_1,b_2,\ldots,b_n$.

Find the minimum possible number of operations performed in the second stage among all valid processes. If there is no valid process, output $-1$.

幽灵杰正在玩橡皮鸭。他有 $n$ 堆橡皮鸭排成一行，其中第 $i$ 堆包含 $a_i$ 只鸭子。鸭子呱呱给了杰一个严格递增的序列 $b_1,b_2,\ldots,b_n$，并命令他将鸭堆序列 $a_1,a_2,\ldots,a_n$ 变为该序列。

杰按以下两个阶段执行操作：

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$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2000$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1\le n\le 2000$) — the number of piles of rubber ducks.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1\le a_i\le 10^9$) — the initial number of rubber ducks in each pile.

The third line contains $n$ integers $b_1,b_2,\ldots,b_n$ ($1\le b_1 \lt b_2 \lt \cdots \lt b_n\le 10^9$) — the final number of rubber ducks in each pile.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output a single integer — the minimum possible number of operations performed in the second stage among all valid processes. If there is no valid process, output $-1$.

对于每个测试用例，输出一个整数——在所有有效过程中第二阶段执行的最少操作次数。若不存在有效过程，则输出 $-1$。

In the first test case, Ja only needs the first stage. He can set $x_1=0,x_2=1,x_3=3$, so the piles become $1,3,5$. No swaps are needed, so the answer is $0$.

In the second test case, Ja needs both stages. He can set $x_1=0,x_2=1,x_3=0$, so the piles become $2,3,1$. Then he can perform two swaps: $$ [2,3,1]\to [2,1,3]\to [1,2,3]. $$ The pile with $1$ duck must move from the third position to the first position, so at least two swaps are necessary. Therefore the answer is $2$.

In the third test case, it is impossible. The first pile initially contains $5$ ducks, but every number in the target sequence is at most $4$. Since Ja can only add ducks and cannot remove them, this pile cannot become equal to any number in the target sequence. Therefore the answer is $-1$.

In the fourth test case, no ducks need to be added. Ja only needs to reorder the piles into increasing order. The minimum number of adjacent swaps is $15$.

In the fifth test case, no ducks need to be added. Again, Ja only needs to reorder the piles into increasing order. The minimum number of adjacent swaps is $12$.

在第一个测试用例中，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$。