Consider solving the problem independently for each color. We can do this by considering all of the positions that are marked by a certain color (the total number of positions is N across all colors).

It is always optimal to take a contiguous subarray of positions in the position array for a color. With the first sample input as an example, the positions array for color 1 would look something like {1, 3, 4, 7, 8}. If we wanted to take positions 1, 3, and 7, it would clearly be inoptimal to not take 4 as we are already deleting between 3 and 7.

English Comment

55403403