Problem Description

Maddy is preparing to rebuild a clock tower.
Maddy has a sequence $\{a_i\}$ of length $n$. Now she wants to transform a sequence $\{h_i\}$ of length $n$ that is initially all 0 into $\{a_i\}$ using the minimum number of operations. Each operation works as follows:

• Maddy chooses a position $k$ ($1 \le k \le n$) and a direction $d \in \{L, R\}$.
• If $d = L$, then for all $1 \le i \le k$, set $h_i$ to $|i - k| + 1$.
• If $d = R$, then for all $k \le i \le n$, set $h_i$ to $|i - k| + 1$.
• Note that each operation completely overwrites the corresponding interval.

Please help her find the minimum number of operations needed. If it is impossible to achieve the goal using the operations above, report that there is no solution.

Input Format

The first line contains an integer $T$ ($1 \le T \le 10^5$), denoting the number of test cases.
For each test case, the first line contains an integer $n$ ($1 \le n \le 10^5$), denoting the length of the sequence.
The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), denoting the target sequence $\{a_i\}$ that Maddy wants to construct.
It is guaranteed that $\sum n \le 3 \times 10^5$ over all test cases.

Output Format

For each test case, if the goal can be achieved using the operations above, output one integer on a line, denoting the minimum number of operations Maddy needs.
Otherwise, output one integer $-1$ on a line.

4
6
1 2 1 1 2 3
3
3 3 3
6
1 1 1 1 1 1
11
1 2 1 3 4 1 2 1 1 2 3

3
-1
6
6

Hint

Explanation for Sample 1

For the 1st sample, the operations can be described as:

1. Choose $k = 4$, $d = R$, then $\{h_i\} = \{0, 0, 0, 1, 2, 3\}$.
2. Choose $k = 3$, $d = L$, then $\{h_i\} = \{3, 2, 1, 1, 2, 3\}$.
3. Choose $k = 1$, $d = L$, then $\{h_i\} = \{1, 2, 1, 1, 2, 3\}$.

It is easy to see that this is a minimum sequence of operations.
For the 2nd sample, it is easy to see that no matter what operations Maddy performs, $h_2$ can never become 3.

Translated by ChatGPT 5