P16218 [ECUSTPC 2025] 钟塔

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$。

### 样例 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。