← 返回题目列表

Codeforces · 1454/F

F. 数组分区

中文机器翻译题面 查看原题

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。

设 $$$min(l, r)$$$ 为 $$$a_l, a_{l + 1}, \ldots, a_r$$$ 中的最小值,$$$max(l, r)$$$ 为 $$$a_l, a_{l + 1}, \ldots, a_r$$$ 中的最大值。

您的任务是选择三个正整数(大于 $$$0$$$)$$$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$$$)。

输出

对于每个测试用例,如果 $$$a$$$ 不存在满足问题陈述中的条件的分区,则在唯一的行中打印答案:NO。否则,在第一行打印 YES,并在第二行打印三个整数 $$$x$$$、$$$y$$$ 和 $$$z$$$ ($$$x + y + z = n$$$)。

如果有多个答案,您可以打印任何答案。

示例

输入 #1

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

输出 #1

YES
6 1 4
NO
YES
2 5 2
YES
4 1 2
YES
1 1 3
YES
2 1 4