#CF2266H. Deque Malfunction
Deque Malfunction
Problem Description
Vihaan built a deque on his own, but it sometimes malfunctions.
Vihaan wants the final contents of the deque, from front to back, to be $[1,2,\ldots,n]$.
You are given an array $b$ of length $m$. The elements arrive one at a time in the order $b_1,b_2,\ldots,b_m$.
Whenever an element $b_i$ arrives, Vihaan must perform exactly one of the following operations:
- push $b_i$ to the front of the deque.
- push $b_i$ to the back of the deque.
- make the deque malfunction and insert $b_i$ at any position of his choice in the deque.
- remove the element at the front of the deque.
- remove the element at the back of the deque.
After all $m$ elements have arrived and all operations have been performed, the deque must contain exactly $[1,2,\ldots,n]$ in that order.
Determine the minimum number of times the deque must malfunction to create $[1,2,\ldots,n]$, or determine that it is impossible.
Input Format
The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le m \le 2 \cdot 10^5$) — the length of the desired deque and the number of arriving elements.
The second line contains $m$ integers $b_1,b_2,\ldots,b_m$ ($1 \le b_i \le n$) — the order in which the elements arrive.
It is guaranteed that the sum of $m$ over all test cases does not exceed $2 \cdot 10^5$.
Output Format
For each test case, print one integer — the minimum number of times the deque must malfunction.
If it is impossible to obtain the desired deque, print $-1$.
Examples
9
1 3
1 1 1
3 4
2 1 1 2
4 4
1 4 2 3
4 5
4 3 4 2 1
5 8
1 3 2 5 4 3 1 2
6 6
1 6 5 4 3 2
4 6
1 3 2 3 4 3
6 8
2 6 3 5 2 1 4 2
6 8
1 6 2 5 1 5 3 4
0
-1
2
0
1
4
0
2
3
Note
In the first test case, Vihaan can perform the following operations:
- Push the first $1$ to the front: $$[] \to [\color{red}{1}].$$ Then, immediately pop it: $$[1] \to [].$$
- Push the second $1$ to the front: $$[] \to [\color{red}{1}].$$ Then, immediately pop it: $$[1] \to [].$$
- Push the last $1$ to the back: $$[] \to [\color{red}{1}].$$
In the second test case, the value $3$ never appears in $b$, so it is impossible to obtain the desired deque.
In the third test case, Vihaan can perform the following operations:
- Push $1$ to the back: $$[] \to [\color{red}{1}].$$
- Push $4$ to the back: $$[1] \to [1,\color{red}{4}].$$
- Make the deque malfunction and insert $2$ between $1$ and $4$: $$[1,4] \to [1,\color{red}{2},4].$$
- Make the deque malfunction and insert $3$ between $2$ and $4$: $$[1,2,4] \to [1,2,\color{red}{3},4].$$
In the fourth test case, Vihaan can perform the following operations:
- Push the first occurrence of $4$ to the front: $$[] \to [\color{red}{4}].$$ Then, immediately pop it: $$[4] \to [].$$
- Push $3$ to the back: $$[] \to [\color{red}{3}].$$
- Push the second occurrence of $4$ to the back: $$[3] \to [3,\color{red}{4}].$$
- Push $2$ to the front: $$[3,4] \to [\color{red}{2},3,4].$$
- Push $1$ to the front: $$[2,3,4] \to [\color{red}{1},2,3,4].$$
Source
Imported from Codeforces — Codeforces Round 1122 (Div. 3).