We decide from left to right whether to insert a divider at each position. By adopting the strategy of “delaying the insertion of a divider unless necessary,” we can keep the number of dividers at most \(N\).

Specifically, it suffices to look at the gems from left to right and insert dividers as follows.

• If the gem is of a type not seen before, do nothing.
• Otherwise, if the parity of the segment index would be the same as that of the previously seen gem of the same type, insert a divider to its left.

The latter case occurs exactly \(N\) times, so the number of dividers is at most \(N\).