458. The Monochrome Picture
Time limit per test: 0.25
Memory limit: 65536
An artist Kalevich is very ambitious and he has many different achievements over the years of his work. Kalevich became extremely famous when he first produced the largest digital picture in the world, setting a new world record in digital painting. It was a great victory with a very unusual image — a billion pixels in width, and... only one pixel in height. The win changed the entire Kalevich's life, so starting from that memorable moment all his digital masterpieces have the height of 1 pixel.
Recently Kalevich was invited to an exhibition in order to demonstrate the best picture he has ever painted. The picture is n
pixels in width, 1 pixel in height, and it is called "The Monochrome Snake". As you have already guessed, the painting is indeed monochrome, so the i
-th pixel is characterized by a single integer ci
from 0 to 106
that is a grayscale representation of its color.
Many visitors at the exhibition have never seen any pictures with colors different from the standard 24-bit RGB, so they look at Kalevich's masterpiece with a great suspicion. Kalevich realized that the visitors do not like monochrome pictures at all, and what is even worse, if the colors of two adjacent pixels in a monochrome picture differ exactly by one, the visitors get angry and go away. Kalevich feels really nervous about this, so he wants to improve his painting in order to please the exigent visitors and keep them at the exhibition. At the same time he wants to preserve the idea of the picture — the snake should be still recognizable, so the only change he wants to make is to delete some pixels here and there. When he deletes a pixel, the width of the painting decreases by 1 of course. Kalevich will be satisfied with the result if |ri
| ≠q 1 for all i
-1, where r
is the final masterpiece and m
is its length.
Your task is to help Kalevich and write a program that will help him to delete the minimum number of pixels from the picture, so that the resulting masterpiece does not have any two adjacent pixels with the colors that differ exactly by one.
The first line of input contains a single integer n
(1 ≤ n
). The second line of input contains n
integers separated by spaces — pixel colors c1
(0 ≤ ci
To the first line of output print the minimum number of pixel deletions t
that are needed to satisfy Kalevich's requirements. To the second line print m
integer numbers (m
) — the masterpiece that is left after t
If there are many solutions, you may output any of them.
4 2 2 1 1 1
4 1 1 1
1 2 3 2 1
1 3 1