We first consider how to judge whether \(a\) can be generated.

We reverse the process so that each modification changes an interval to any value, and we denote it as this modification “covers” the interval.

Then we can build up a greedy process:

• If all uncovered elements in \([l_i,r_i]\) have the same value, then cover them.

The process ends when no more intervals can be selected. Obviously, \(a\) can be generated if and only if all elements are covered.

Now we can solve the problem by an interval DP. To transit, consider calculating the invalid ones. Now there will be some elements left uncovered.

Find all maximal covered intervals \([p_1,q_1]\dots [p_k,q_k]\), they form \(k\) independent subproblems. All we need to do is to make sure that “no more intervals can be selected”.

In the DP state, maintain the rightmost uncovered element with value different from the rightmost uncovered element in the interval. It’s sufficient to judge the validity.

Time complexity: \(O(n^4)\). \(O(n^5)\) solutions with small constant may pass.