Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Задача D. Клумбы

Задачу добавил: alef

Успешно сдано решений: 86

ограничение по времени на тест:2 секунды
ограничение по памяти на тест:256 мегабайт

Вдоль аллеи, по которой любит кататься Кеша, высаживают цветы в клумбы. Всего вдоль аллеи расположено n клумб. Для каждой клумбы известно, какое количество цветов на нее должно быть высажено — f1, f2, ..., fn.

Эту работу поручили бригаде из n человек. Известно, что каждый работник на высаживание одного цветка тратит ровно 2 единицы времени. Бригадир может назначить либо одного работника на одну клумбу, либо двух работников на 2 расположенные подряд клумбы.

Если работники трудятся в паре, они перейдут работать на вторую клумбу одновременно и только после того, как на первую клумбу будет высажен последний цветок.

Работа считается выполненной, когда все цветы будут высажены во все клумбы. Ваша задача — определить, за какое минимально возможное время работа может быть выполнена.

Входные данные

В первой строке содержится целое число n (1 ≤ n ≤ 105) — количество клумб (и работников).

Во второй строке содержится n целых чисел f1, f2, ..., fn (1 ≤ fi ≤ 105,  i = 1, 2, ..., n), где fi — количество цветов, которое должно быть высажено в клумбу #i. Клумбы занумерованы согласно их расположению вдоль аллеи.

Выходные данные

В первой строке выведите минимально возможное время, спустя которое цветы могут быть высажены во все клумбы.

Во второй строке выведите последовательность, состоящую из n единиц и двоек: на месте #i должна стоять 1, если на эту клумбу назначен один работник, и 2, если на эту клумбу назначено двое работников.

Если существует несколько вариантов ответа, выведите любой.

Примеры
Входные данные
7
6 10 3 7 5 10 4
Выходные данные
14
1 2 2 1 1 2 2
Входные данные
7
3 10 8 8 6 10 5
Выходные данные
16
2 2 1 1 2 2 1
Примечание

В первой группе тестов (3 - 52) баллы начисляются за каждый пройденный тест (до 50 баллов).

Во второй группе тестов (53 - 70) баллы (50) начисляются при условии прохождения всех тестов группы.

Сдать задачу

Задать вопрос жюри по этой задаче