Codeforces Round 942 (Div. 1) |
---|
Finished |
Little R is a magician who likes non-decreasing arrays. She has an array of length $$$n$$$, initially as $$$a_1, \ldots, a_n$$$, in which each element is an integer between $$$[1, m]$$$. She wants it to be non-decreasing, i.e., $$$a_1 \leq a_2 \leq \ldots \leq a_n$$$.
To do this, she can perform several magic tricks. Little R has a fixed array $$$b_1\ldots b_m$$$ of length $$$m$$$. Formally, let's define a trick as a procedure that does the following things in order:
Little R wonders how many tricks are needed at least to make the initial array non-decreasing. If it is not possible with any amount of tricks, print $$$-1$$$ instead.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1\le t\le 10^4$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\leq n \leq 10^6$$$, $$$1 \leq m \leq 10^6$$$) — the length of the initial array and the range of the elements in the array.
The second line of each test case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq m$$$) — the initial array.
The third line of each test case contains $$$m$$$ integers $$$b_1, \ldots, b_m$$$ ($$$1 \leq b_i \leq m$$$) — the fixed magic array.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, output a single integer: the minimum number of tricks needed, or $$$-1$$$ if it is impossible to make $$$a_1, \ldots, a_n$$$ non-decreasing.
35 81 6 3 7 12 3 5 8 7 1 5 63 31 3 22 1 310 102 8 5 4 8 4 1 5 10 106 7 2 6 3 4 1 1 3 5
3 -1 3
In the first case, the initial array $$$a_1, \ldots, a_n$$$ is $$$[1, 6, 3, 7, 1]$$$. You can choose $$$S$$$ as follows:
In the second case, it is impossible to make $$$a_1, \ldots, a_n$$$ non-decreasing.
Name |
---|