За круглым столом сидят n людей из разных компаний. Люди пронумерованы от 1 до n по часовой стрелке. Человек с номером i относится к компании ai.
Скоро начнется совещание и Вам необходимо выдать каждому из n людей микрофон. В Вашем распоряжении есть бесконечное количество микрофонов любых возможных цветов. По эстетическим соображениям, человеку с номером i не понравится, если хотя бы один из его соседей слева или справа будет относиться к другой компании и при этом будет иметь микрофон того же цвета, что и человек с номером i.
Люди сидят по кругу и пронумерованы так, что:
для всех людей, кроме человека с номером 1, соседом слева является человек, имеющий номер на единицу меньше, а для человека с номером 1 соседом слева является человек с номером n;
для всех людей, кроме человека с номером n, соседом справа является человек, имеющий номер на единицу больше, а для человека с номером n соседом справа является человек с номером 1.
Ваша задача — раздать микрофоны таким образом, чтобы минимизировать количество различных использованных цветов. Если Вы используете ровно k различных цветов, то цвета микрофонов должны быть пронумерованы от 1 до k.
Входные данные
Первая строка входных данных содержит одно целое число n (3 ≤ n ≤ 2·105) — количество людей на совещании.
Вторая строка входных данных содержит n целых чисел a1, a2, …, an (1 ≤ ai ≤ 2·105), где ai равно компании, к которой принадлежит человек с номером i.
Выходные данные
В первой строке выведите одно целое число k — минимально возможное количество различных цветов микрофонов.
Во второй строке входных данных выведите n целых чисел c1, c2, …, cn (1 ≤ ci ≤ k), разделенных пробелами и/или переводами строк, где ci обозначает номер цвета микрофона, который необходимо отдать i-му человеку. Если существует несколько возможных ответов, вы можете вывести любой из них. Стоит заметить, что минимально возможное количество цветов микрофонов различным быть не может.
Вот мой код. В чем может быть ошибка?
n = int(input()) a = list(map(int, input().split())) dct = {} color = 1 for i in range(n): if a[i] not in dct: dct[a[i]] = color color += 1 result = [] for i in range(n): result.append(str(dct[a[i]])) print(len(dct)) print(' '.join(result))