Круглая карусель состоит из \(n\) фигур различных животных. Фигуры пронумерованы от \(1\) до \(n\) по ходу движения карусели. Таким образом, после \(n\)-й фигуры идёт фигура с номером \(1\). Каждая фигура имеет вид — это животного этой фигуры (лошадка, тигр и др.). Вид животного \(i\)-й фигуры равен \(t_i\).
Пример изображения карусели для \(n=9\) и \(t=[5, 5, 1, 15, 1, 5, 5, 1, 1]\). Вы хотите покрасить каждую фигуру в один из цветов. Вам кажется скучным, если в каруселе разные фигуры (с разными видами животных) идут подряд и покрашены в одинаковые цвета.
Ваша задача — покрасить фигуры так, чтобы количество различных использованных цветов было минимальным и не существовало двух фигур разного вида, которые идут подряд и покрашены в один цвет одновременно. Если Вы используете ровно \(k\) различных цветов, то цвета фигур должны быть пронумерованы целыми числами от \(1\) до \(k\).
Выходные данные
Выведите \(q\) ответов — на для каждого набора входных данных выведите две строки.
В первую строку выведите одно целое число \(k\) — минимально возможное количество различных цветов фигур.
Во вторую строку выведите \(n\) целых чисел \(c_1, c_2, \dots, c_n\) (\(1 \le c_i \le k\)), где \(c_i\) обозначает номер цвета \(i\)-й фигуры. Если существует несколько возможных ответов, вы можете вывести любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5
1 2 1 2 2
6
1 2 2 1 2 2
5
1 2 1 2 3
3
10 10 10
|
2
1 2 1 2 2
2
2 1 2 1 2 1
3
2 3 2 3 1
1
1 1 1
|