Это сложная версия задачи. Задачи отличаются друг от друга, но простая версия почти является подзадачей сложной версии. Обратите внимание на то, что ограничения и формат вывода различаются.
Дана строка \(s\), состоящая из \(n\) строчных латинских букв.
Вам нужно раскрасить все её символы в минимальное количество цветов (каждый символ покрашен ровно в один цвет, одинаковые буквы могут быть покрашены как одним цветом, так и разными, т.е. вам нужно выбрать ровно один цвет для каждого индекса в \(s\)).
После покраски вы можете поменять местами два любых соседних символа строки, которые раскрашены в разные цвета. Вы можете применить эту операцию произвольное (возможно, нулевое) количество раз.
Цель — сделать строку отсортированной, т.е. все символы должны быть расположены в алфавитном порядке.
Ваша задача – найти минимальное количество цветов, которое нужно, чтобы раскрасить строку так, что после раскраски она может быть отсортирована с помощью какой-либо последовательности шагов. Обратите внимание: вам нужно восстановить только раскраску, но не последовательность шагов.
Выходные данные
В первой строке выведите одно целое число \(res\) (\(1 \le res \le n\)) — минимальное количество цветов, которое нужно, чтобы раскрасить строку так, что после раскраски она может быть отсортирована с помощью какой-либо последовательности шагов.
Во второй строке выведите любую возможную раскраску, которая может быть использована, чтобы отсортировать строку с помощью какой-либо последовательности шагов, описанных в условии задачи. Раскраской считается массив \(c\) длины \(n\), где \(1 \le c_i \le res\) и \(c_i\) содержит цвет \(i\)-го символа.