Nice problem.
Playing out with small numbers and sample could help in sequence instantiation.

My solution is only 30 lines of c++ code O(L) though.

Hint: imagine we have sequence which can replace up to L spaces afterall. Then to enlarge our sequence we insert L/2 + 1 in the beginning. Maximum L could be computed via straightforward iteration starting from lax max_L
Example:

seq: 2
max_L: 2

seq: 2, 2/2 + 1 = 2, 2
max_L: 2, 4

seq: 2, 2, 4/2 + 1 = 2, 2, 3
max_L: 2, 4, 10

seq: 2, 2, 3, 10/2 + 1 = 2, 2, 3, 6
max_L: 2, 4, 10, 40

Etc.
GL.