e-olymp
Competitions

Summer School 2011 in Sevastopol, Day 7

Шагающий робот

Известная компания по производству роботов сконструировала еще одну модель, теперь уже двуногого шагающего робота. Для его испытания выстраивают в ряд несколько столбиков, состоящих из одинаковых кубиков. Как выяснилось, робот может перешагнуть с одного столбика на другой, если высоты этих столбиков (то есть количество кубиков в них) отличаются не более, чем на 1.

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

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

В первой строке входного файла записаны целое число N (1N106). Во второй строке задаются N неотрицательных целых чисел, не превышающих 2·106, определяющих высоты соответствующих столбиков.

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

В первой строке выходного файла выведите минимальное количество кубиков, которые нужно снять. Во второй строке следует вывести N чисел, каждое из которых определяет количество кубиков, оставшихся в соответствующем столбике.

Time limit 1 second
Memory limit 64 MiB
Input example #1
4
1 3 1 2
Output example #1
1
1 2 1 2
Author Виталий Неспирный