CF1899E Queue Sort

Vlad 找到一个长度为 $n$ 的整数数组 $a$，他想将其按非递减顺序排序。 为此，Vlad 可以任意次数地进行以下操作： - 取出数组的第一个元素，并将其插入到数组末尾； - 将该元素与前一个元素交换，直到它成为第一个元素，或者直到它严格大于前一个元素为止。 注意，这两个动作都属于一次操作，且每次操作必须同时执行这两个动作。 例如，如果对数组 \[ $4, 3, 1, 2, 6, 4$ \] 执行一次操作，变化过程如下： - \[ $\color{red}{4}, 3, 1, 2, 6, 4$ \]； - \[ $3, 1, 2, 6, 4, \color{red}{4}$ \]； - \[ $3, 1, 2, 6, \color{red}{4}, 4$ \]； - \[ $3, 1, 2, \color{red}{4}, 6, 4$ \]。 Vlad 没有时间亲自执行所有操作，所以他请你帮忙计算将数组排序所需的最少操作次数，或者判断是否无法完成排序。

输入的第一行包含一个整数 $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$。

由 ChatGPT 4.1 翻译