Busy Beaver 在查尔斯河畔有 $N$ 个最喜欢的零食点，标记为 $1, 2, \dots, N$。每天，他都希望在时间 $i$ 到零食点 $i$ 享用零食。多么完美且优化的日常安排！

不幸的是，大雁们有其他的计划。对于每个位置 $i$，一只大雁会在时间 $i$ 占据零食点 $a_i$。Busy Beaver 绝不接受与大雁去往同一个零食点，因此他最终的日程安排 $p_1, p_2, \dots, p_N$ 必须是 $1, 2, \dots, N$ 的一个排列，且对于每个 $1 \le i \le N$，都满足 $p_i \neq a_i$。

Busy Beaver 还希望让自己的生活保持规律。在所有合法的日程安排 $p$ 中，请确定 $p$ 可能拥有的最小逆序对数。如果不存在合法的日程安排，输出 $-1$。

（注：$p$ 中的逆序对数定义为满足 $1 \le i < j \le N$ 且 $p_i > p_j$ 的数对 $(i, j)$ 的个数。）

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 3 \cdot 10^5$)，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $N$ ($1 \le N \le 3 \cdot 10^5$)。

每个测试用例的第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$ ($1 \le a_i \le N$)。

所有测试用例的 $N$ 之和不超过 $3 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数：在所有满足 $p_i \neq a_i$（对所有 $i$）的排列 $p$ 中，最小可能的逆序对数。如果不存在合法的日程安排，输出 $-1$。

样例

输入 1

4
3
2 3 1
4
1 2 3 4
5
1 1 1 1 1
10
1 1 1 1 1 10 10 10 10 10

输出 1

0
2
-1
9

说明

在第一个测试用例中，没有位置满足 $a_i = i$，因此 Beaver 可以使用他原本的日常安排 $p = [1, 2, 3]$，其逆序对数为 $0$。

在第二个测试用例中，一个合法的日程安排是 $p = [2, 1, 4, 3]$，它恰好有 $2$ 个逆序对。

在第三个测试用例中，零食点 $1$ 整天都被占据，因此可怜的 Busy Beaver 无法做出任何安排。真遗憾！