Other solutions can work, but we provide a solution closest to the full solution.

The idea is that if we see a filled in item ~x~ at position ~i~, then we have some interval where all values ~\ge x~ must be. For instance, if we have a ~4~ in slot ~2~, then assuming our peak is on the right and ~N = 7~, the interval ~[2, 5]~ must contain all numbers from ~4~ to ~7~. Furthermore, the interval ~[3, 5]~ must contain all numbers from ~5~ to ~7~.

Of course these intervals depend on where the peak is. For this subtask, we can simply consider two possible peaks. If a valid solution exists, then a solution exists where the peak is either directly to the left of the largest element, or directly to the right of it (or the peak is pre-determined). Proof is left as an exercise to the reader.

With all our intervals, we need to check that there are no partial overlaps, or equivalently that the intervals contain each other. This is because if we had partial overlaps, the constraints given by two items in the array conflict. Also, we can add the interval ~[1, N]~ to our set, since all of our intervals have to be contained in that.

We can use a set and a counter of "infractions" to keep track of whether or not the intervals are properly formed, but of course, for this subtask, other methods exist for this step.

The ideas here are very similar. Now we are given the peak, and are asked to simulate efficiently. We can keep using our set. If we use the same ideas outlined in the solution for subtask 1, this subtask is relatively doable.

The main problem here is how to deal with the peak. The lemma proposed in the first subtask still holds, but peak updates change far too many things for us to rely on pointing towards a peak.

Instead, we can point each interval towards the larger of the two filled-in neighbours. This makes updates very local, and allows us to perform them efficiently.

There is one more case to consider. See the following example:

0 0 3 0 5 4

Here the interval given by ~5~ incorrectly points towards ~4~, causing our algorithm to output NO. How do we fix this?

If we ever reach such a case, we can try to fix it by considering the largest element, which will not have a clear direction. We can try pointing the interval the other way, and checking if that gives us a valid solution. If it does, then we output YES as required.

When implementing, take care to consider how to update intervals so that they always point towards the larger neighbour. Note that solutions not using sets likely exist, but are potentially more challenging to implement.

This problem, although it seems very innocent, is deceptively hard to solve. There are a large number of greedy solutions for the first subtask that simply do not work. Taking the time to find the right model is imperative.

Special thanks go to zhouzixiang2004, without whom this problem would not exist. The solution writeup given here is based on his approach.