### 问题描述 小夜在一次冒险中，发现了一个包含 $N$ 颗魔法石的宝箱。每颗魔法石上都刻着一个非负整数。小夜发现，她可以通过施展一个魔法来改变一些魔法石上的数字： - 小夜可以选择两颗魔法石 $i$ 和 $j$，它们上面刻着的数字相同，然后改变魔法石 $i$ 和 $j$ 之间所有魔法石（包括 $i$ 和 $j$）上的数字为 $A_i$。 小夜希望通过施展这个魔法，使得魔法石上的数字按照非递减的顺序排列。请你帮助小夜计算出，最少需要施展多少次魔法，如果无法通过施展魔法将魔法石上的数字排序，输出 $-1$。 ### 输入格式 第一行输入一个整数 $T$，表示测试用例的数量。 每个测试用例包含两行，第一行包含一个整数 $N$，表示魔法石的数量。第二行包含 $N$ 个整数，表示每颗魔法石上刻的数字。 ### 输出格式 对于每个测试用例，输出一行，表示最少需要施展的魔法次数 如果无法通过施展魔法将魔法石上的数字排序，输出 $-1$。 ### 输入样例 ``` 2 6 1 2 1 3 4 3 3 3 1 2 ``` ### 输出样例 ``` 2 -1 ``` ### 说明 第一个测试用例：第一次施展魔法，选择第一颗和第三颗魔法石，然后将这两颗魔法石之间所有魔法石的数字都改为 $1$，得到新的魔法石序列 $[1,1,1,3,4,3]$。第二次施展魔法，选择第四颗和第六颗魔法石，然后将这两颗魔法石之间所有魔法石的数字都改为 $3$，得到新的魔法石序列 $[1,1,1,3,3,3]$。这样，魔法石上的数字就按照非递减的顺序排列了。 第二个测试用例：无论如何施展魔法，都无法将魔法石上的数字排序。 ### 评测数据范围 $1 \leq T≤10^3$。 $1 ≤ N ≤ 2 \times 10^5$。 $0 ≤ A_i ≤ N$。 所有测试用例中 $N$ 的总和不超过 $2 \times 10^5$。