0071. Color The Bricks

Имя входного файла:	color.in
Имя выходного файла:	color.out
Ограничение по времени:	1 s
Ограничение по памяти:	64 megabytes

Little Johnie has received a box of bricks as his birthday present. Each brick has some integer number written on it. Johnie has put all bricks in the row so that the numbers on them form the sequence a₁, a₂, …, a_n.

Now he wants to paint all his bricks with various colors. He wants to paint them in such a way that the numbers on the bricks of the same color would form an increasing sequence. That is, if the bricks i₁ < i₂ < … < i_k have the same color, then a_i1 < a_i2 < … < a_ik.

Johnie wants to use as few colors as he can (you know, he'll have to pay for the tubes with paint from his lunch money). Help him!

Input file

The first line of the input file contains N, the number of bricks Johnie has (1 ≤ N ≤ 239,017). N integer numbers follow, separated by spaces and/or line feeds.

Output file

On the first line of the output file print L – the least number of colors Johnie needs to fulfil his wish. On the second line output N integer numbers ranging from 1 to L – the colors to which Johnie should paint his bricks.

Examples:

color.in	color.out
5 1 2 4 3 5	2 1 1 1 2 2

Источник: Petrozavodsk Winter 2003. St. Petersburg Contest I

Обсудить       Отправить решение



Версия для печати