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