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

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

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

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