Let ~a_1, a_2, \dots, a_N~ be the sequence of elevations.

Without minimizing the maximum elevation

We can mostly ignore the constraint that all elevations are positive, provided our elevations are not too far apart. This is because once we have generated a sequence satisfying the requirements, we can increase or decrease each element of ~a~ by the same amount such that all elements of ~a~ are positive.

Let us define a sequence ~b_1, b_2, \dots, b_{N-1}~ such that ~b_i = a_{i+1}-a_i~. In other words, ~b~ is the difference array of ~a~. Note that the requirement that ~a_l, a_{l+1}, \dots, a_r~ is increasing is equivalent to the requirement that ~b_l, b_{l+1}, \dots, b_{r-1}~ are positive. Similarly, the requirement that ~a_l, a_{l+1}, \dots, a_r~ is decreasing is equivalent to the requirement that ~b_l, b_{l+1}, \dots, b_{r-1}~ are negative. Finally, since no two adjacent elements of ~a~ can equal, ~0~ cannot be present in sequence ~b~.

For the solution without minimizing the maximum element of ~a~, it suffices to set the corresponding elements of ~b~ to ~1~ for each increasing requirement, and all other elements of ~b~ to ~-1~. We can then reconstruct ~a~ as the prefix sum sequence of ~b~, and apply the required shift such that all elements of ~a~ are positive. If there are two conflicting requirements such that an element of ~b~ must be both positive and negative, then there is no solution.

Minimizing the maximum elevation

Now, we will try to find a solution which minimizes the maximum element of ~a~. As we will see later, there is an edge case regarding whether the maximum elevation can be ~2~. Depending on the implementation, it may be easier to initially test whether ~1, 2, 1, 2, \dots~ or ~2, 1, 2, 1, \dots~ are valid sequences of ~a~. The rest of the solution handles the case where these sequences are invalid (and that the requirements do not contradict each other so that a solution exists).

Furthermore, let us merge overlapping intervals of the same type. For example, if we know that subarray from ~1~ to ~3~ is increasing, and that the subarray from ~3~ to ~5~ is increasing, then the subarray from ~1~ to ~5~ is increasing.

Let ~K~ be the maximum value of ~r_i-l_i+1~ amongst all merged requirements. Clearly, no solution with a maximum elevation of less than ~K~ exists.

We conjecture that there is a solution with a maximum elevation of ~\max(3, K)~. We will process the requirements from left to right. For each increasing requirement between ~l_i~ and ~r_i~, we can set the corresponding subarray to any increasing sequence such that ~a_{l_i} = 1~ and ~a_{r_i} = K~. For each decreasing requirement between ~l_i~ and ~r_i~, we can set the corresponding subarray to any decreasing sequence such that ~a_{l_i} = K~ and ~a_{r_i} = 1~. For any element of ~a_i~ which has not yet been determined, we can set it to any value which is not equal to its neighbours; this is always possible since we have at least ~3~ unique values to work with.

However, this solution is flawed due to an edge case. If the subarray ~[1, 3]~ is increasing and the subarray ~[4, 6]~ is decreasing, then our algorithm would return ~a = [1, 2, 3, 3, 2, 1]~, which is not allowed. Specifically, our algorithm is incorrect when two requirements have two adjacent subarrays and are of different types. Then, we should replace our earlier construction with the following:

Instead of making all increasing subarrays span between ~1~ and ~K~, for each subarray from left to right, we should try to construct any increasing subarray such that the final element of the subarray is minimized. Similarly, for all decreasing subarrays, we should try to construct any decreasing subarray such that the final element of the subarray is as large as possible. If the leftmost element of the subarray has already been determined when we process it, then we can overwrite this element. All elements still have to be between ~1~ and ~K~.

This construction handles all cases where there exists a solution with the maximum element equal to ~K~. However, this is not always possible, as demonstrated by the previous edge case. Hence, if our construction fails, we should repeat the construction, but with the condition that all elements have to be between ~1~ and ~K+1~. Note that we are always guaranteed that a solution with the maximum element equal to ~K+1~ exists; for example, ignoring overwriting values, we could enforce that for each increasing requirement between ~l_i~ and ~r_i~, we can set the corresponding subarray to any increasing sequence such that ~a_{l_i} = 1~ and ~a_{r_i} = K~, and for each decreasing requirement between ~l_i~ and ~r_i~, we can set the corresponding subarray to any decreasing sequence such that ~a_{l_i} = K+1~ and ~a_{r_i} = 2~.

Subtask ~1~ was designed to reward naïve implementations which run in ~\mathcal{O}(NM)~ time. This can be sped up using a sweepline to solve subtask ~2~ in ~\mathcal{O}(N+M)~ or ~\mathcal{O}(N+M \log M)~ time.