Вдоль аллеи, по которой любит кататься Кеша, высаживают цветы в клумбы. Всего вдоль аллеи расположено 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
Эту работу поручили бригаде из 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