We can use dynamic programming to solve this task. Let ~A_i~ be the color of the ~i^\text{th}~ marble. Let our state be described with 3 items: ~(l, r, count)~ that gives the minimal number of marbles we need to insert into subsequence ~\{A_l, A_{l+1}, \dots, A_r\}~ so that it disappears, with the added bonus that we can insert ~count~ copies of marble ~A_l~ on the beginning of the sequence.

For example, let ~A = \{\underline{1, 3, 3, 3, 2}, 3, 1, 1, 1, 3\}~. State ~[\underline 0][\underline 4][\mathbf 3]~ denotes the minimal number of marbles we need to insert into ~\{\mathbf 1, \mathbf 1, \mathbf 1, 1, 3, 3, 3, 2\}~ so that the entire subsequence disappears.

There are three transitions for each state:

• Add a duplicate of the first marble to the beginning of the sequence. This gives ~[l][r][X] = [l][r][X+1] + 1~.
• If ~X = k-1~, we can delete all marbles on the beginning of the sequence, including the first marble of our subsequence. This gives ~[l][r][X] = [l+1][r][0]~ for ~X = k-1~.
• Third and most complex case is merging the first marble with some later marble. We expect to merge our first marble (~A_l~) with some marble ~A_j~ assuming ~A_l = A_j~. This merger gives ~[l][r][X] = [l+1][j-1][0] + [j][r][X+1]~.

For each state, we must of course find the minimum of all possible transitions.