Piano

Mouse Peter is passionate about playing the piano. He chooses increasingly longer and more demanding pieces to play which he then practices for hours. Of special importance when successfully playing a piece is an impeccable fingering.

For the sake of simplicity we will consider a piece that consist only of one note at a time and that can be played with just the right hand. Only the white keys of the keyboard are used. These white keys are enumerated from left to right from 1 to 50 (7 octaves).

We define a 'fingering' as follows: Beside each note, Peter indicates with which finger he plays that note by writing down a number from the set ${1,2,3,4,5}$.

  1. Thumb
  2. Index finger
  3. Middle Finger
  4. Ring finger
  5. Little finger

Now, Peter would like to find the most elegant fingering for his piece. A fingering is considered elegant if it can be played with as little movements of the hand as possible. In order to determine a fingering's elegance, he uses following simple method:

A note earns one point of elegance in the following cases:

  • The note is the first one of the piece.
  • Or the difference between the numbers of the current and the previous note is equal to the difference between the numbers of the current and previous finger. Mathematically: For keys $k_i$ and $k_{i+1}$ fingers $f_i$ and $f_{i+1}$ the following equation must hold: $k_i - k_{i+1} = f_i - f_{i+1}$. Intuitively this means that Peter can place his hand such that there is one finger per key while playing the $i$-th and $i+1$-th note.

In all other cases the note earns no point of elegance.

Task

Find a fingering which maximizes the points of elegance.

Input

The input consists of two lines. The first line contains an integer $N$, the number of notes in the piece. The second line contains $N$ integers $k_i$ ($1 \leq t_i \leq 50$), the keys for notes of the piece.

Output

The output should contain two lines. In the first line, output the optimal number of points of elegance. In the second line, output $N$ numbers $f_i$ ($1 \leq f_i \leq 5$), separated by spaces, which describe an optimal fingering. If multiple solutions exist, output any of them.

Constraints

  • For test cases worth 40% of all points, it holds that $1 \le N \le 10$.
  • For test cases worth 60% of all points, it holds that $1 \le N \le 1\,000$.
  • For test cases worth 100% of all points, it holds that $1 \le N \le 1\,000\,000$.

Example 1 - Hänschen klein (C'=3)

1)

InputOutput

13
7 5 5 6 4 4 3 4 5 6 7 7 7

13
5 3 3 4 2 2 1 2 3 4 5 5 5

Example 2 - Alle meine Entchen (C'=5)

InputOutput

27
5 6 7 8 9 9 10 10 10 10 9 10 10 10 10 9 8 8 8 8 7 7 6 6 6 6 5

25
1 2 3 4 5 5 5 5 5 5 4 5 5 5 5 4 3 3 3 3 2 2 1 1 1 1 1

Example 3 - Australian National Anthem (C'=1, C"=8)

InputOutput

28
5 8 5 3 5 8 8 8 10 9 8 7 8 9 5 8 5 3 1 5 5 6 10 9 8 7 6 5

22
1 4 1 1 3 2 2 2 4 3 2 1 2 3 1 4 1 3 1 5 5 1 5 4 3 2 1 1

 AustraliaFair.png

Submission

1) The notation C'=3 stands for the note number of the middle C. It simply helps you if you want to play the song yourself, but is not relevant for the task itself.