Шагающий робот
Известная компания по производству роботов сконструировала еще одну модель, теперь уже двуногого шагающего робота. Для его испытания выстраивают в ряд несколько столбиков, состоящих из одинаковых кубиков. Как выяснилось, робот может перешагнуть с одного столбика на другой, если высоты этих столбиков (то есть количество кубиков в них) отличаются не более, чем на 1.
Определите минимальное количество кубиков, которые необходимо снять для того, чтобы робот мог пройти весь ряд столбиков от начала до конца.
Входные данные
В первой строке входного файла записаны целое число N (1 ≤ N ≤ 10^6). Во второй строке задаются N неотрицательных целых чисел, не превышающих 2·10^6, определяющих высоты соответствующих столбиков.
Выходные данные
В первой строке выходного файла выведите минимальное количество кубиков, которые нужно снять. Во второй строке следует вывести N чисел, каждое из которых определяет количество кубиков, оставшихся в соответствующем столбике.