RLE Compression

RLE (run-length encoding) is a simple compression scheme for sequences that contain long stretches of the same repeated character. Encoding a sequence produces its code; the idea is to replace a block of identical characters (such as aaaaa) with information about which character repeats and how many times.

Fix an alphabet of n characters, written as the integers Sigma = {0, 1, ..., n - 1}. A sequence and its code are both strings over Sigma. Encoding relies on a distinguished repetition mark, which is itself one of the characters of Sigma and is denoted e. Initially e = 0, but it may change while a code is being read.

A code is decoded from left to right. Let e be the current repetition mark.

• Any character a different from e stands for itself (a single character a).
• When the current mark e appears, the next two characters x and y form a group with e, interpreted as exactly one of three cases:
  • if x = e, the group (e, e, y) expands to y + 1 copies of e;
  • otherwise, if y = 0, the group (e, x, 0) with x != e changes the repetition mark to x from this point on and outputs nothing;
  • otherwise, the group (e, x, y) with x != e and y > 0 expands to y + 3 copies of x.

The repetition mark changes only in the middle case; the other two groups leave it unchanged.

For example, let n = 4. The sequence 1 0 0 2 2 2 2 2 2 3 3 3 3 3 0 3 0 2 0 0 0 0 can be encoded as 1 0 0 1 0 2 3 0 3 2 0 1 0 0 3 0 2 1 0 1. Reading this code with e = 0: the leading 1 stands for itself; 0 0 1 produces 0 0; 0 2 3 produces six 2s; 0 3 2 produces five 3s; 0 1 0 switches the mark to 1; then 0 3 0 2 stand for themselves; and finally 1 0 1 (now with mark 1) produces four 0s.

The same sequence can be encoded in many ways, and different codes may have different lengths. You are given a code; determine the length of a shortest code that decodes to the same sequence.

Write a program that reads the alphabet size and a code, decodes it to obtain a sequence, and prints the length of a shortest code that decodes to that sequence.

The first line contains an integer n (2 <= n <= 30): the alphabet size. The second line contains an integer m (1 <= m <= 100): the length of the code. The third line contains m integers from {0, 1, ..., n - 1}, separated by single spaces: the code of a sequence.

Print a single integer: the least number of characters in a code that decodes to the same sequence as the given code.