B. Annoying the Ghost
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

Input

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

Output

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

Example
Input
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
Output
0
2
-1
15
12
0
4
4
3
5
Note

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