Array Partition
Contest: Codeforces Round 686 (Div. 3)
Difficulty rating: 2100
Tags: binary search, data structures, greedy, two pointers

You are given an array $$$a$$$ consisting of $$$n$$$ integers.

Let $$$min(l, r)$$$ be the minimum value among $$$a_l, a_{l + 1}, \ldots, a_r$$$ and $$$max(l, r)$$$ be the maximum value among $$$a_l, a_{l + 1}, \ldots, a_r$$$.

Your task is to choose three positive (greater than $$$0$$$) integers $$$x$$$, $$$y$$$ and $$$z$$$ such that:

- $$$x + y + z = n$$$;
- $$$max(1, x) = min(x + 1, x + y) = max(x + y + 1, n)$$$.

In other words, you have to split the array $$$a$$$ into three consecutive non-empty parts that cover the whole array and the maximum in the first part equals the minimum in the second part and equals the maximum in the third part (or determine it is impossible to find such a partition).

Among all such triples (partitions), you can choose any.

You have to answer $$$t$$$ independent test cases.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of the test case contains one integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the length of $$$a$$$.

The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

Output format:
For each test case, print the answer: NO in the only line if there is no such partition of $$$a$$$ that satisfies the conditions from the problem statement. Otherwise, print YES in the first line and three integers $$$x$$$, $$$y$$$ and $$$z$$$ ($$$x + y + z = n$$$) in the second line.

If there are several answers, you can print any.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
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

Example output:
YES
6 1 4
NO
YES
2 5 2
YES
4 1 2
YES
1 1 3
YES
2 1 4

Editorial:
Let's fix the length of the first block (iterate through $$$i$$$ from $$$0$$$ to $$$n-3$$$). Let's also try to maximize the length of the third block using the second pointer. So, initially the length of the first block is $$$1$$$ and the maximum in the block is $$$a_0$$$ (after that, its length will be $$$2$$$ and the maximum will be $$$max(a_0, a_1)$$$, and so on). Let's move the left border of the third block $$$r$$$ while $$$a_r \le a_0$$$ and the second block have at least one element.
After we expanded the third block, consider some cases: if its maximum is less than $$$a_0$$$, then we don't need to consider this partition (we expanded the third block as much as we can but didn't find the required maximum). Otherwise, its maximum fits our conditions. Then let's find the minimum in the second block. Let it be $$$mn$$$. If $$$mn < mx$$$, this partition is also bad. If $$$mn = mx$$$, this partition is good, and we can just print it. Otherwise, $$$mn > mx$$$, and we need to fix the second block somehow. I claim that we only need to expand it by at most one element. Let's see why is it true. Consider we want to expand it to the right (the other case just uses the same logic). If we expanded our block by one element to the right and the new value in it is less than $$$mx$$$, then this partition is bad, and we can not use it (this is also the reason why we are trying to maximize the length of the third block). Otherwise, this value is always $$$mx$$$, because the first and the third blocks didn't have values greater than $$$mx$$$.
There are some cases in the implementation we need to consider carefully: first, we need to find the minimum in the second block fast enough. This can be done if we store it as a multiset (set with repetitions). Second, we can remove the only maximum in the third (or the first) block by expanding the second one. This can be handled easily if we just store all three blocks (not only the second one) as multisets. And the last case is that we sometimes need to move the left border of the third block to the right. This happens when we expand the first block and the second block becomes empty. So, this happens only $$$O(n)$$$ times in total.
Total time complexity of this solution is $$$O(n \log n)$$$.
There is also another solution from Gassa:
Let us start solving by asking the following question: in which segments will the maximal values end up?
Consider the maximum value $$$m$$$ in the whole array. If there are at least three of them, a valid answer is to pick any maximum except the first and the last as the middle segment. For example, "3 2 3 1 3 2 3" ($$$m = 3$$$) can be partitioned as "3 2[3]1 3 2 3" or as "3 2 3 1[3]2 3", where the middle segment is marked with square brackets. Otherwise, all $$$m$$$ should end up in the middle segment, so that maximums to the left and to the right are less. For example, in "1 2 3 1 3 2 1", we have to put both threes into the middle segment.
Let us now calculate the minimum value $$$v$$$ on the middle segment, considering the numbers between those equal to $$$m$$$. For example, in "1 2[3 1 3]2 1" the value $$$v = \min (3, 1, 3) = 1$$$. All numbers greater than $$$v$$$ should also go into the middle segment, and everything between them, which can result in $$$v$$$ decreasing even more. We have to expand the borders of the middle segment until the minimum value is such $$$v$$$ that there are only values not greater than $$$v$$$ left outside. Continuing with the example, we see that in "1 2[3 1 3]2 1", the middle segment should be expanded to "1[2 3 1 3 2]1". Conversely, if the maximum $$$m$$$ was unique, then $$$v = m$$$, and we didn't have to expand the middle segment at this stage. For example, in "1 2 3 2 1", the current state is "1 2[3]2 1".
If the maximums to the left and to the right are exactly $$$v$$$, we found an answer. Otherwise, any possible middle segment contains the middle segment that we now got. So we have to expand the middle segment, either to the left or to the right. As a result, the value $$$v$$$ may become smaller, which can cause another expansion.
What's left is to decide where to expand when we have a choice. We would like to do it greedily. Indeed, consider three values: the minimum on middle segment $$$v$$$, the maximum on left segment $$$u$$$ and the maximum on right segment $$$w$$$. When we expand the middle segment, each of them can only decrease. And if we find an answer, the equation $$$u = v = w$$$ will be satisfied. So, as we make the minimum of these three values smaller, we have less and less opportunities to make them equal. Thus we can pick the side of expansion after which the value $$$\min (u, v, w)$$$ is larger, and if these are equal, pick any.
For example, in the state "1 3[5 4 5]2 3 1", we have $$$u = 3$$$, $$$v = 4$$$, and $$$w = 3$$$. If we expand to the left, we get "1[3 5 4 5]2 3 1" where $$$u = 1$$$, $$$v = 3$$$, and $$$w = 3$$$. If we expand to the right, we get "1 3[5 4 5 2]3 1" where $$$u = 3$$$, $$$v = 2$$$, and $$$w = 3$$$. Our algorithm will pick expanding to the right, however, there is no valid answer in this example anyway.
Implementation: let us precalculate the maximums on all prefixes and all suffixes of the array. Then we can expand the middle segment by one element in $$$O (1)$$$, and the total running time is linear.