CF1454F Array Partition

给定一个包含 $n$ 个整数的数组 $a$。 定义 $min(l, r)$ 表示 $a_l, a_{l + 1}, \ldots, a_r$ 中的最小值，$max(l, r)$ 表示 $a_l, a_{l + 1}, \ldots, a_r$ 中的最大值。 你的任务是选择三个正整数 $x$、$y$ 和 $z$，使得： - $x + y + z = n$； - $max(1, x) = min(x + 1, x + y) = max(x + y + 1, n)$。 换句话说，你需要将数组 $a$ 分成三个连续且非空的部分，覆盖整个数组，并且第一个部分的最大值等于第二个部分的最小值，且等于第三个部分的最大值（或者判断不存在这样的划分）。 在所有满足条件的三元组（划分）中，你可以任选一个。 你需要回答 $t$ 个独立的测试用例。

输入的第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$），表示测试用例的数量。接下来是 $t$ 个测试用例。 每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$），表示 $a$ 的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），其中 $a_i$ 是 $a$ 的第 $i$ 个元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$（$\sum n \le 2 \cdot 10^5$）。

对于每个测试用例，如果不存在满足条件的划分，输出一行 NO。否则，第一行输出 YES，第二行输出三个整数 $x$、$y$ 和 $z$（$x + y + z = n$）。 如果有多组答案，可以输出任意一组。

由 ChatGPT 4.1 翻译