Телевізор#1166

Телевізор

1 секунда
64 мегабайти
Легка

Є така робота — натискати кнопки

У дівчини на ім'я Настя є телевізор зі різними каналами, пронумерованими від до . Вона користується пультом з кнопками, пронумерованими від до , щоб перемикати канали. Пульт може працювати у двох режимах: та . У режимі номер каналу встановлюється натисканням однієї кнопки-цифри. У режимі номер каналу встановлюється натисканням двох кнопок-цифр (наприклад, натиснувши "", а потім "", перемикаємося на канал ). Натискання кнопки "" зменшує номер каналу на один (якщо поточний канал — нуль, Настя перемкнеться на канал ). Кнопка "" збільшує номер каналу на один. Натискання кнопки "" змінює режим пульта: якщо поточний режим , він перемикається на , і навпаки. Спочатку телевізор увімкнено на каналі , а пульт перебуває у режимі .

Після року вивчення телевізійної програми Настя склала список каналів, які хоче переглянути, у певному порядку. Список дуже довгий, а пульт не дуже новий, тому Настя хоче мінімізувати кількість натискань на кнопки. Допоможіть їй у цьому. Зверніть увагу, що Настя повинна переглядати канали у зазначеному порядку.

Вхідні дані

У першому рядку задане ціле додатне число (1 \leq n \leq 100000) — кількість каналів у списку. У другому рядку міститься невід'ємних чисел — послідовність каналів, які Настя хоче переглянути. Сусідні числа розділені пробілом. Номери каналів не перевищують .

Вихідні дані

Виведіть одне ціле число — мінімальну кількість натискань на кнопки, необхідну для перегляду заданого списку каналів. У другому рядку виведіть символів, які описують оптимальну послідовність натискань кнопок. Якщо існує кілька оптимальних рішень, виведіть будь-яке з них.

Приклади

Приклад 1

Loading
Loading