题目描述

Maddy 准备重建一座钟塔……
Maddy 有一个长度为 $n$ 的序列 $\{a_i\}$，现在她希望通过最少的操作来让一个长度为 $n$ 初始全为 0 的序列 $\{h_i\}$ 变为 $\{a_i\}$，其中每次操作的规则如下：

• Maddy 选择一个坐标 $k$ ($1 \le k \le n$) 和一个方向 $d \in \{L, R\}$。
• 若 $d = L$，对于所有 $1 \le i \le k$，令 $h_i$ 变为 $|i - k| + 1$。
• 若 $d = R$，对于所有 $k \le i \le n$，令 $h_i$ 变为 $|i - k| + 1$。
• 注意每次操作都会完全覆盖所对应的区间。

请帮助她求出最少所需的操作次数，若不可能通过上述操作达成目的，请报告无解。

输入格式

第一行输入一个整数 $T$ ($1 \le T \le 10^5$)，表示数据组数。
每组测试数据的第一行输入一个整数 $n$ ($1 \le n \le 10^5$)，表示序列长度。
随后一行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)，表示 Maddy 希望构造得到的序列 $\{a_i\}$。
保证所有测试数据输入中的 $\sum n \le 3 \times 10^5$。

输出格式

对于每组测试数据，若可以通过上述操作达成目的，则输出一行一个整数，表示 Maddy 所需要进行最少的操作次数。
反之则输出一行一个整数 $-1$。

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

提示

样例 1 解释

对于第 1 个样例，其操作过程可表示为：

1. 选择 $k = 4$，$d = R$，序列 $\{h_i\} = \{0, 0, 0, 1, 2, 3\}$；
2. 选择 $k = 3$，$d = L$，序列 $\{h_i\} = \{3, 2, 1, 1, 2, 3\}$；
3. 选择 $k = 1$，$d = L$，序列 $\{h_i\} = \{1, 2, 1, 1, 2, 3\}$。

容易发现这即是最少步数的操作序列了。
对于第 2 个样例，容易发现无论 Maddy 进行任何操作，$h_2$ 都不可能变为 3。