#include <stdio.h>
#define N 2000000
#define M 100000
int min(int a, int b) { return a < b ? a : b; }
int iq[1 + M], pq[M], cnt, dp[M];
int lt(int i, int j) { return dp[i] < dp[j]; }
int p2(int p) {
return (p *= 2) > cnt ? 0 : p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p;
}
void pq_up(int i) {
int p, q, j;
for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_dn(int i) {
int p, q, j;
for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
int pq_first() {
return iq[1];
}
int main() {
static int hh[N], hh_[N];
static long long kk[N];
int n, n_, m, h, i, sum;
scanf("%d%d", &m, &n);
for (i = 0; i < n; i++)
scanf("%d", &hh[i]);
n_ = 0;
for (h = 0, i = 0; i < n; i++)
if (hh[i] != h)
hh[n_] = hh[i], kk[n_] = 1, n_++;
else {
if (hh[i + 1] == h)
hh[n_] = h, kk[n_] = hh[i + 2] + 1, n_++;
else if (hh[i + 2] == 0)
h = hh[i + 1];
else
hh[n_] = hh[i + 1], kk[n_] = hh[i + 2] + 3, n_++;
i += 2;
}
n = n_, n_ = 0;
for (i = 0; i < n; i++)
if (n_ == 0 || hh[n_ - 1] != hh[i])
hh[n_] = hh[i], kk[n_] = kk[i], n_++;
else
kk[n_ - 1] += kk[i];
n = n_;
for (h = 0; h < m; h++)
iq[pq[h] = ++cnt] = h;
sum = 0;
for (i = n - 1; i >= 0; i--) {
int k, k_, h, h_;
k = kk[i] / (m + 2) * 3 + min(kk[i] % (m + 2), 3), k_ = (kk[i] + m - 1) / m * 3;
sum += k;
h = hh[i];
dp[h] += k_ - k, pq_dn(h);
h_ = pq_first();
if (dp[h] > dp[h_] + 3) {
hh_[i] = h_;
dp[h] = dp[h_] + 3, pq_up(h);
} else
hh_[i] = -1;
}
printf("%d\n", sum + dp[0]);
for (h = 0, i = 0; i < n; i++) {
if (hh[i] == h && hh_[i] != -1)
printf("%d %d 0 ", h, hh_[i]), h = hh_[i];
if (hh[i] != h) {
while (kk[i] >= m + 2) {
printf("%d %d %d ", h, hh[i], m - 1);
kk[i] -= m + 2;
}
if (kk[i] <= 3)
while (kk[i]--)
printf("%d ", hh[i]);
else
printf("%d %d %lld ", h, hh[i], kk[i] - 3);
} else {
while (kk[i] >= m) {
printf("%d %d %d ", h, h, m - 1);
kk[i] -= m;
}
if (kk[i] > 0)
printf("%d %d %lld ", h, h, kk[i] - 1);
}
}
printf("\n");
return 0;
}
