P2556 [AHOI2002] Black-and-White Image Compression

While taking an elective in basic genetics, Xiao Keke did a home experiment related to image processing. She knows that an entire image is actually a sequence of image points (called pixels). Assume the number of pixels in the sequence is always a multiple of 8, so every eight pixels can be converted into a number called a byte, thereby converting the pixel sequence representing the image into a sequence of bytes. A byte is an 8-bit binary number (of course, for convenience, people often write it in decimal). The eight pixels, from earlier to later, correspond to the eight bits of the byte from the most significant bit to the least significant bit. Use 0 for a white pixel and 1 for a black pixel. This representation is called the bitmap method. For example, the byte sequence 210, 0, 255 represents $8 \times 3 = 24$ pixels. Since their binary forms are 11010010, 00000000, 11111111, the colors of these 24 pixels in order are: black, black, white, black, white, white, black, white, white, white, white, white, white, white, white, white, black, black, black, black, black, black, black, black. Xiao Keke thought: there are many runs of consecutive pixels with the same color in an image; maybe using another way to express the image could reduce the data size. Her idea is to divide the pixels into several segments by color, where all pixels in the same segment have the same color, and every consecutive run of same-color pixels belongs to a single segment. It is also known that the maximum length of each segment is less than 128. Each pixel segment is represented by one binary byte. The most significant bit indicates the color of the pixels in the segment, and the lower seven bits indicate the number of pixels in the segment. Note: segments of length 0 do not exist. This representation is called the pixel segment method. For example, the pixel sequence corresponding to the bitmap byte sequence 210, 0, 255 can be divided into seven segments: 11, 0, 1, 00, 1, 000000000, 11111111. If represented by the pixel segment method, the binary byte sequence should be 10000010, 00000001, 10000001, 00000010, 10000001, 00001001, 10001000, and the corresponding decimal byte sequence is 130, 1, 129, 2, 129, 9, 136. Can the pixel segment method effectively reduce the amount of image data? Xiao Keke does not know how to prove it mathematically, so she decides to experiment on the images at hand to see whether this method really works. Please write a program to perform the conversion of image information to assist Xiao Keke in this experiment.

The file contains one line describing an image. The first number is a positive integer $n$, indicating that the image has $n$ pixels. It is followed by $\frac{n}{8}$ bytes in decimal form, representing the bitmap information of the image. Adjacent numbers are separated by a single whitespace character.

Output on a single line the image information encoded by the pixel segment method. All numbers should be in decimal, and adjacent numbers should be separated by a single whitespace character.

$1 \le n \le 8 \times 10^4$. Translated by ChatGPT 5