#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.
Vihaan may also perform either of the following operations at any time:
  • 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:

  1. Push the first $1$ to the front: $$[] \to [\color{red}{1}].$$ Then, immediately pop it: $$[1] \to [].$$
  2. Push the second $1$ to the front: $$[] \to [\color{red}{1}].$$ Then, immediately pop it: $$[1] \to [].$$
  3. Push the last $1$ to the back: $$[] \to [\color{red}{1}].$$
Thus, no malfunctions are required.

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:

  1. Push $1$ to the back: $$[] \to [\color{red}{1}].$$
  2. Push $4$ to the back: $$[1] \to [1,\color{red}{4}].$$
  3. Make the deque malfunction and insert $2$ between $1$ and $4$: $$[1,4] \to [1,\color{red}{2},4].$$
  4. Make the deque malfunction and insert $3$ between $2$ and $4$: $$[1,2,4] \to [1,2,\color{red}{3},4].$$
It can be shown that no sequence of operations using fewer than $2$ malfunctions can obtain the desired deque. Thus, the minimum is $2$.

In the fourth test case, Vihaan can perform the following operations:

  1. Push the first occurrence of $4$ to the front: $$[] \to [\color{red}{4}].$$ Then, immediately pop it: $$[4] \to [].$$
  2. Push $3$ to the back: $$[] \to [\color{red}{3}].$$
  3. Push the second occurrence of $4$ to the back: $$[3] \to [3,\color{red}{4}].$$
  4. Push $2$ to the front: $$[3,4] \to [\color{red}{2},3,4].$$
  5. Push $1$ to the front: $$[2,3,4] \to [\color{red}{1},2,3,4].$$
Thus, no malfunctions are required.

Source

Imported from Codeforces — Codeforces Round 1122 (Div. 3).