돌을 밟고 호수 건너기

주디 홉스는 닉과의 매우 중요한 약속에 늦지 않으려고 달리고 있는데, 갑자기 커다란 호수가 길을 막았습니다. 돌아갈 시간이 없어서 다른 방법이 필요합니다. 다행히 호수 수면 위로 돌 몇 개가 보이고, 주디는 그 돌을 밟고 뛸 수 있습니다.

호수를 좌표축으로 생각합시다. 주디는 좌표 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$). $n$은 주디가 도달해야 하는 좌표이고, $k$는 호수에 있는 돌의 개수입니다. 둘째 줄에는 공백으로 구분된 $k$개의 정수 $x_i$가 주어집니다 ($1 \le x_i \le n$). $x_1 > 0$이며, $i > 1$인 모든 $i$에 대해 $x_i > x_{i-1}$입니다.

첫 줄에 좌표 0에서 좌표 $n$까지 가는 데 필요한 최소 점프 횟수를 출력합니다. 둘째 줄에는 최적 경로를 출력합니다. 경로는 공백 없이 이어 쓴 1과 2의 수열입니다. 경로의 길이는 최소여야 하며, 그중에서 사전순으로 가장 작아야 합니다. 호수를 돌아가지 않고는 좌표 $n$에 도달할 수 없다면 -1을 한 줄에 출력합니다.

수열 $A$가 수열 $B$보다 사전순으로 작다는 것은 $A \ne B$이고, $A_0 = B_0, A_1 = B_1, \ldots, A_k = B_k$이면서 $A_{k+1} < B_{k+1}$인 $0 \le k \le |A|$가 존재한다는 뜻입니다.