Məsələlər
Шагающий робот
Шагающий робот
Известная компания по производству роботов сконструировала еще одну модель, теперь уже двуногого шагающего робота. Для его испытания выстраивают в ряд несколько столбиков, состоящих из одинаковых кубиков. Как выяснилось, робот может перешагнуть с одного столбика на другой, если высоты этих столбиков (то есть количество кубиков в них) отличаются не более, чем на \textbf{1}.
Определите минимальное количество кубиков, которые необходимо снять для того, чтобы робот мог пройти весь ряд столбиков от начала до конца.
\InputFile
В первой строке входного файла записаны целое число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10^6}). Во второй строке задаются \textbf{N} неотрицательных целых чисел, не превышающих \textbf{2·10^6}, определяющих высоты соответствующих столбиков.
\OutputFile
В первой строке выходного файла выведите минимальное количество кубиков, которые нужно снять. Во второй строке следует вывести \textbf{N} чисел, каждое из которых определяет количество кубиков, оставшихся в соответствующем столбике.
Giriş verilənləri #1
4 1 3 1 2
Çıxış verilənləri #1
1 1 2 1 2