29084번 - Прыжки по камням 스페셜 저지다국어

Джуди Хоппс бежит на очень важную встречу с Ником, и тут как назло перед ней оказалось огромное озеро. Обходить его времени нет, требуется какой-то другой план. К счастью для Джуди, на поверхности озера виднеются несколько камней, по которым она сможет прыгать.

Для простоты представим озеро в виде координатной прямой, на которой Джуди стоит в точке 0, а конец озера находится в точке с координатой $n$. Несмотря на то, что Джуди --- зайчиха и хороша в прыжках, прыгать она может только на 1 и 2 метра вперед соответственно (то есть из точки с координатой $x$ она может попасть в точки с координатами $x+1$ и $x+2$). Зная координаты камней, Джуди хочет найти минимальное количество прыжков, которое ей нужно совершить, чтобы добраться из точки с координатой 0 в точку с координатой $n$. Однако ее также с детства учили делать все максимально оптимально, поэтому она также хочет из всех путей с минимальным количеством прыжком выбрать лексикографически минимальный. Каждый прыжок описывается последовательностью чисел 1 и 2 ($i$-е число соответствует длине $i$-го прыжка).

Помогите Джуди как можно быстрее решить эту задачу --- хоть она и дама, очень сильно опаздывать на встречу все-таки некрасиво.

В первой строке входного файла находятся два числа $n$, $k$ ($1 \le n \le 10^5; 0 \le k < n$) --- координата, в которую Джуди надо попасть, и количество камней на озере соответственно.

В следующей строке через пробел находятся $k$ чисел $x_i$ ($1 \le x_i \le n$) --- координаты камней. Гарантируется, что для всех $x_1 > 0$, а также для всех $i > 1$ верно, что $x_i > x_{i-1}$.

В первой строке выходного файла выведите целое число --- минимальное количество прыжков, которое требуется, чтобы добраться из координаты 0 в координату $n$. Во второй строке выведите оптимальный путь --- последовательность 1 и 2 без пробелов.

Путь должен быть минимальным по длине, а из всех таких, лексикографически минимальным.

Если Джуди не удастся никак допрыгнуть до точки с координатой $n$, то есть придется обходить озеро, в этом случае в единственной строке выходного файла выведите <<-1>> (без кавычек).

Последовательность чисел $A$ является лексикографически меньше последовательности $B$, если $A \ne B$ и существует такое $0 \le k \le |A|$, что $A_0 = B_0, A_1 = B_1, \ldots, A_k = B_k$ и $A_{k+1} < B_{k+1}$.