题目描述

小程找到一个长度为 $n$ 的整数数组 $a$，并决定将它按非递减顺序排序。

为此，小程可以执行任意多次如下操作：先取出数组的第一个元素，并将它插入到数组末尾；然后将这个元素不断与前一个元素交换位置，直到它变成第一个元素，或者直到它严格大于前一个元素为止。注意，这两个动作共同构成一次完整操作，在一次操作中必须同时执行这两步。

例如，如果对数组 $[4,3,1,2,6,4]$ 执行一次操作，数组会按如下方式变化：

• [4,3,1,2,6,4];
• [3,1,2,6,4,4];
• [3,1,2,6,4,4];
• [3,1,2,4,6,4].

小程没有时间执行太多操作，因此他希望你帮忙判断：将数组排序为非递减顺序所需的最少操作次数。如果无法做到，则输出 $-1$。

输入格式

第一行包含一个整数 $t \ (1 \le t \le 10^4)$，表示测试用例数量。每个测试用例第一行包含一个整数 $n \ (1 \le n \le 2 \cdot 10^5)$，表示数组长度；第二行包含 $n$ 个整数 $a_1,a_2,a_3,\dots,a_n \ (1 \le a_i \le 10^9)$ 表示数组元素。保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示将数组排序所需的最少操作次数；如果无法完成排序，则输出 $-1$。

输入样例

5
5
6 4 1 2 5
7
4 5 3 7 8 6 2
6
4 3 1 2 6 4
4
5 2 4 2
3
2 2 3

输出样例

2
6
-1
-1
0