AT_utpc2023_a.Again Make UTPC

给定一个长度为 $N$ 的字符串 $S$，$S$ 的每个字符均为 U、T、P、C 之一。

你可以进行如下操作任意多次（也可以不操作）：

• 任选一组整数对 $(i, j)$，满足 $1 \leq i \leq j \leq N$。将 $S$ 中第 $i$ 个字符到第 $j$ 个字符按字母升序排序。

请判断能否通过若干次（可为 0 次）上述操作，使字符串 $S$ 满足以下条件：

• $S$ 包含连续的子串 UTPC。

对于 $T$ 个测试用例，请对每个案例给出答案：若可行，输出最少需要的操作次数；否则输出 -1。

输入以以下格式从标准输入读入。$\mathrm{case}_i$ 表示第 $i$ 个测试用例。

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

每个测试用例如下：

$N$ $S$

输出 $T$ 行，第 $i$ 行输出第 $i$ 个测试用例的答案。若可以使字符串 $S$ 满足条件，则输出所需操作的最小次数；否则输出 $-1$。

样例解释 1

对于第 1 个测试用例，只需进行如下 2 次操作。若操作次数小于 2，则无法满足条件。

• 选择 $(i, j) = (1, 4)$，字符串变为 CCUUTPUCUC。
• 选择 $(i, j) = (7, 10)$，字符串变为 CCUUTPCCUU。

对于第 2 个测试用例，无论如何操作，都无法满足条件。

对于第 3 个测试用例，不需要任何操作即可满足条件。

约束条件

• $T, N$ 为整数
• $1 \leq T \leq 2 \times 10^5$
• $1 \leq N \leq 2 \times 10^5$
• $S$ 仅包含 U、T、P、C，长度为 $N$
• 所有测试用例中 $N$ 的总和不超过 $2 \times 10^5$

由 ChatGPT 5 翻译