Задача №2859. Раскраска кубиков
На день рождения Пете подарили коробку кубиков. На каждом кубике написано некоторое целое число. Петя выложил все \(n\) своих кубиков в ряд, так что числа на кубиках оказались расположены в некотором порядке \(a_1\), \(a_2\), ..., \(a_n\). Теперь он хочет раскрасить кубики в разные цвета таким образом, чтобы для каждого цвета последовательность чисел на кубиках этого цвета была строго возрастающей. То есть, если кубики с номерами \(i_1\), \(i_2\), ...., \(i_k\) покрашены в один цвет, то \(a_{i_1} \lt a_{i_2}\lt ... \lt a_{i_k}\). Петя хочет использовать как можно меньше цветов. Помогите ему!
Первая строка входного файла содержит число \(n\) - количество кубиков у Пети (\(1\le n \le 250000\)). В следующей строке записано \(n\) чисел \(a_1\), \(a_2\), ..., \(a_k\), \(-2^{31}\le a_i \le 2^{31} - 1\).
На первой строке выходного файла выведите число \(m\) — наименьшее количество цветов, которое потребуется Пете. На следующей строке выведите \(n\) чисел из диапазона от 1 до \(m\) — цвета, в которые Петя должен покрасить кубики.
10 2 3 1 3 2 1 2 2 4 3
5 1 1 2 2 3 4 4 5 1 3