Задача №376. Раскраска кубиков
На день рождения Пете подарили коробку кубиков. На каждом кубике написано некоторое целое число. Петя выложил все n своих кубиков в ряд, так что числа на кубиках оказались расположены в некотором порядке a[1], a[2],...,a[n]. Теперь он хочет раскрасить кубики в разные цвета таким образом, чтобы для каждого цвета последовательность чисел на кубиках этого цвета была строго возрастающей. То есть, если кубики с номерами i[1], i[2],..., i[k] покрашены в один цвет, то a[i[1]] < a[i[2]] < ... < a[i[k]]. Петя хочет использовать как можно меньше цветов. Помогите ему!
Первая строка входного файла содержит число n - количество кубиков у Пети (1 <= n <= 250000). Затем следует n чисел, разделенных пробелами и/или переводами строки - a[1], a[2], ..., a[n].
На первой строке выходного файла выведите число L - наименьшее количество цветов, которое потребуется Пете. На следующей строке выведите n чисел из диапазона от 1 до L - цвета, в которые Петя должен покрасить кубики.
6 5 8 10 12 4 1
3 1 1 1 1 2 3