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