CF1905C.Largest Subsequence

Given is a string $s$ of length $n$. In one operation you can select the lexicographically largest$^\dagger$ subsequence of string $s$ and cyclic shift it to the right$^\ddagger$.

Your task is to calculate the minimum number of operations it would take for $s$ to become sorted, or report that it never reaches a sorted state.

$^\dagger$A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds:

• $a$ is a prefix of $b$, but $a \ne b$;
• In the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.

$^\ddagger$By cyclic shifting the string $t_1t_2\ldots t_m$ to the right, we get the string $t_mt_1\ldots t_{m-1}$.

给定一个长度为 $n$ 的字符串 $s$。在一次操作中，你可以选择字符串 $s$ 的字典序最大$^\dagger$的子序列，并将其向右循环移位$^\ddagger$。

你的任务是计算使 $s$ 变为升序排列所需的最少操作次数；若 $s$ 永远无法变为升序排列，则报告这一点。

$^\dagger$ 字符串 $a$ 字典序小于字符串 $b$，当且仅当以下条件之一成立：

• $a$ 是 $b$ 的前缀，但 $a \ne b$；
• 在 $a$ 与 $b$ 首次出现不同字符的位置上，$a$ 中该位置的字母在字母表中早于 $b$ 中对应位置的字母。

$^\ddagger$ 将字符串 $t_1t_2\ldots t_m$ 向右循环移位后，得到字符串 $t_mt_1\ldots t_{m-1}$。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the string $s$.

The second line of each test case contains a single string $s$ of length $n$, consisting of lowercase English letters.

It is guaranteed that sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示字符串 $s$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，由小写英文字母组成。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output a single integer — the minimum number of operations required to make $s$ sorted, or $-1$ if it's impossible.

对于每个测试用例，输出一个整数——使 $s$ 变为有序所需的最少操作次数；如果不可能，则输出 $-1$。

In the first test case, the string $s$ is already sorted, so we need no operations.

In the second test case, doing one operation, we will select cb and cyclic shift it. The string $s$ is now abc which is sorted.

In the third test case, $s$ cannot be sorted.

In the fourth test case we will perform the following operations:

• The lexicographically largest subsequence is zca. Then $s$ becomes abzc.
• The lexicographically largest subsequence is zc. Then $s$ becomes abcz. The string becomes sorted.

Thus, we need $2$ operations.

在第一个测试用例中，字符串 $s$ 已经是有序的，因此无需任何操作。

在第二个测试用例中，执行一次操作：我们选择子串 cb 并对其作循环移位，字符串 $s$ 变为 abc，此时已有序。

在第三个测试用例中，字符串 $s$ 无法被排序。

在第四个测试用例中，我们将执行以下操作：

• 字典序最大的子序列是 zca，于是 $s$ 变为 abzc。
• 字典序最大的子序列是 zc，于是 $s$ 变为 abcz，此时字符串已有序。

因此，总共需要 $2$ 次操作。