Given an array ~S~ of ~N~ ordered integers each between ~0~ and ~4~, we must replace the ~0~'s with other numbers between ~1~ and ~4~ such that no two adjacent numbers are the same, and that the resulting array is lexicographically smallest. You may be tempted to try some recursive solution, but this is unnecessarily complicated and may very well exceed the time limit. Instead, we can take advantage of the second requirement to construct a greedy solution.

Note that for any given ~i~ between ~1~ and ~N~ such that ~S_i = 0~, it is always more important to minimize the value at ~i~ than any index greater than ~i~. This is because the goal is to ultimately find a solution which minimizes the lexicographical rank of the entire array, and earlier indices take precedence. Now note that it will always be possible to fill in any ~0~-value in the array, no matter what its neighbouring values are (at most ~2~ of the ~4~ possible values will be prohibited). This makes it so we don't have to worry about the "consequences" of our decisions – namely, whether the current choice will eventually lead to no possible way to fill in a cell later on. Putting these two observations together, we know that as long as we minimize the current value, there will always be an answer which is lexicographically smallest.

Now, we can loop through each unassigned scene in order from ~1~ to ~N~ and try to assign it the smallest value in the range ~1 \dots 4~ which is unequal to that of the previous scene (if any) and also unequal to that of the following scene (if it exists and is pre-assigned to a setting). We must be careful to not access the array out of bounds at the border iterations. This greedy process (implemented below) takes ~4N~ steps, which means that it runs in ~\mathcal O(N)~ time.