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-ri+1| ≠ 1 for all i=1... m-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.
Warn: 本題有 specialjudge
There are at most 50 test cases, terminated by EOF.
Each test case contain 2 line. The first line of input contains a single integer n (1 ≤ n ≤ 105). The second line of input contains n integers separated by spaces — pixel colors c1, c2,..., cn (0 ≤ ci ≤ 106).
For each test case, print the minimum number of pixel deletions t that are needed to satisfy Kalevich's requirements in the first line. And print m integer numbers (m = n-t) — the masterpiece that is left after t pixel deletions in the second line.
If there are many solutions, you may output any of them.
6 4 2 2 1 1 1 5 1 2 3 2 1
2 4 1 1 1 2 1 3 1
Migrated from old NTUJ.
sgu458
| No. | Testdata Range | Score |
|---|