Television#1166
There is such a job—pressing buttons
A girl named Nastya owns a TV with different channels, numbered from to . She uses a remote control with buttons numbered from to to change channels. The remote can operate in two modes: and . In mode , the channel number is set by pressing a single digit button. In mode , the channel number is set by pressing two digit buttons (for example, pressing and then switches to channel ). Pressing the "" button decreases the channel number by one (if the current channel is , Nastya will switch to channel ). The "" button increases the channel number by one. Pressing the "" button switches the remote's mode: if the current mode is , it goes to , and vice versa. Initially, the TV is on channel , and the remote is in mode .
After studying the TV guide for a year, Nastya has made a list of channels she wants to watch, in a specific order. The list is very long, and the remote is not very new, so Nastya wants to minimize the number of button presses. Help her do this. Note that Nastya must watch the channels in the given order.
The first line contains a positive integer (1 \leq n \leq 100000) — the number of channels in the list. The second line contains non-negative integers — the sequence of channels Nastya wants to watch. Adjacent numbers are separated by a space. The channel numbers do not exceed .
Output an integer — the minimum number of button presses required to watch the specified list of channels. On the second line, output characters describing the optimal button presses. If there are multiple optimal solutions, output any one of them.
Example 1