Эта задача самая скучная из всех, которые Вы когда-либо видели.
Дана последовательность целых чисел a1, a2, ..., an и неотрицательное целое число h, наша задача — разбить последовательность на две подпоследовательности (не обязательно состоящие из подряд идущих элементов). Каждый элемент исходной последовательности должен содержаться ровно в одной из полученных подпоследовательностей. Заметьте, что одна из полученных подпоследовательностей может быть пустой.
Определим функцию f(ai, aj), аргументами которой являются два различных элемента (то есть, i ≠ j) исходной последовательности. Если ai и aj находятся в одной и той же подпоследовательности в текущем разбиении, f(ai, aj) = ai + aj в противном случае f(ai, aj) = ai + aj + h.
Рассмотрим все возможные значения функции f для некоторого разбиения. Назовем хорошестью данного разбиения разность между максимальным значением функции f и минимальным значением функции f.
Ваша задача — найти разбиение данной последовательности a, которое имеет минимально возможную хорошесть среди всех возможных разбиений.
Выходные данные
Первая строка выходных данных должна содержать искомую минимальную хорошесть.
Вторая строка описывает оптимальное разбиение. Выведите n разделенных пробелами целых чисел: i-ое целое число равняется 1, если ai находится в первой подпоследовательности, в противном случае оно должно равняться 2.
Если есть несколько возможных правильных ответов, Вам разрешается вывести любой.
Примечание
В первом примере значения f таковы: f(1, 2) = 1 + 2 + 2 = 5, f(1, 3) = 1 + 3 + 2 = 6 и f(2, 3) = 2 + 3 = 5. Таким образом, разность между максимальным и минимальным значением f равняется 1.
Во втором примере значение h велико, следовательно, лучше оставить одну из подпоследовательностей пустой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 2 3
|
1
1 2 2
|
|
2
|
5 10
0 1 0 2 1
|
3
2 2 2 2 2
|