#ifndef SorahISA
#define SorahISA
#include SorahISA __FILE__ SorahISA

int recur(const int N, const vector<int> &arr, int L, int R) {
    if (L == R) return 1;
    int M = (L + R) >> 1;
    int ans = 0;
    ans += recur(N, arr, L, M);
    ans += recur(N, arr, M+1, R);
    
    static vector<int> mn(N), mx(N);
    static vector<int> cnt1(4*N), cnt2(4*N); /// offset by 2*N
    mn[M] = mx[M] = arr[M];
    for (int i = M-1; i >= L; --i) mn[i] = min(mn[i+1], arr[i]), mx[i] = max(mx[i+1], arr[i]);
    mn[M+1] = mx[M+1] = arr[M+1];
    for (int i = M+2; i <= R; ++i) mn[i] = min(mn[i-1], arr[i]), mx[i] = max(mx[i-1], arr[i]);
    
    for (int l = M, r1 = M, r2 = M; l >= L; --l) {
        /// r1: last pos which mn[r1] and mx[r1] is between mn[l] and mx[l] ///
        /// r1: [max - min - r + l = 0] ==> [r = l + max - min] ///
        while (r1 < R and mn[r1+1] > mn[l] and mx[r1+1] < mx[l]) {
            ++r1;
            ++cnt1[2*N + r1];
            --cnt2[2*N + r1 + mn[r1]];
        }
        /// r2: last pos which mx[r2] is below mx[l] ///
        /// r2: [max - min - r + l = 0] ==> [r + min = l + max] ///
        while (r2 < R and mx[r2+1] < mx[l]) {
            ++r2;
            ++cnt2[2*N + r2 + mn[r2]];
        }
        ans += cnt1[2*N + l + mx[l] - mn[l]];
        ans += cnt2[2*N + l + mx[l]];
        
        if (l == L) {
            while (r2 != r1) --cnt2[2*N + r2 + mn[r2]], --r2;
            while (r1 != M)  --cnt1[2*N + r1],          --r1;
        }
    }
    
    for (int l1 = M+1, l2 = M+1, r = M+1; r <= R; ++r) {
        /// l1: first pos which mn[l1] and mx[l1] is between mn[r] and mx[r] ///
        /// l1: [max - min - r + l = 0] ==> [l = r + min - max] ///
        while (l1 > L and mn[l1-1] > mn[r] and mx[l1-1] < mx[r]) {
            --l1;
            ++cnt1[2*N + l1];
            --cnt2[2*N + l1 - mn[l1]];
        }
        /// l2: first pos which mx[l2] is below mx[r] ///
        /// l2: [max - min - r + l = 0] ==> [l - min = r - max] ///
        while (l2 > L and mx[l2-1] < mx[r]) {
            --l2;
            ++cnt2[2*N + l2 - mn[l2]];
        }
        ans += cnt1[2*N + r + mn[r] - mx[r]];
        ans += cnt2[2*N + r - mx[r]];
        
        if (r == R) {
            while (l2 != l1)  --cnt2[2*N + l2 - mn[l2]], ++l2;
            while (l1 != M+1) --cnt1[2*N + l1],          ++l1;
        }
    }
    
    return ans;
};

void solve() {
    int N, K; cin >> N >> K;
    
    if (K == 0) {
        cout << N * (N+1) / 2 << "\n";
        for (int i = 1; i <= N; ++i) cout << i << " \n"[i == N];
        return;
    }
    
    vector<int> A(N), B(N), used(N+1, 0);
    for (int i = 0; i < K; ++i) cin >> A[i], used[A[i]] = 1;
    B = A;
    
    for (int i = K, j = K-1, mn = A[j], mx = A[j]; i < N; ++i) {
        while (mn >= 1 and used[mn]) --mn;
        while (mx <= N and used[mx]) ++mx;
        while (j >= 0 and mn <= A[j] and A[j] <= mx) --j;
        if (j < 0) {
            B = A;
            int tmp_mn = mn, tmp_mx = mx;
            for (int k = i; k < N; ++k) A[k] = (mn >= 1 ? mn-- : mx++);
            mn = tmp_mn, mx = tmp_mx;
            for (int k = i; k < N; ++k) B[k] = (mx <= N ? mx++ : mn--);
            break;
        }
        if (A[j] < mn) used[A[i] = mn] = 1;
        else           used[A[i] = mx] = 1;
        // debug(mn, mx, i, j, A);
    }
    
    int ans_A = recur(N, A, 0, N-1), ans_B = recur(N, B, 0, N-1);
    // int tmp_A = 0, tmp_B = 0;
    // for (int L = 0; L < N; ++L) {
    //     int mn_A = A[L], mx_A = A[L], mn_B = B[L], mx_B = B[L];
    //     for (int R = L; R < N; ++R) {
    //         chmin(mn_A, A[R]), chmax(mx_A, A[R]);
    //         chmin(mn_B, B[R]), chmax(mx_B, B[R]);
    //         if (mx_A - mn_A == R - L) ++tmp_A;
    //         if (mx_B - mn_B == R - L) ++tmp_B;
    //     }
    // }
    // debug(ans_A, tmp_A, ans_B, tmp_B);
    
    if (ans_A > ans_B) {
        cout << ans_A << "\n";
        for (int i = 0; i < N; ++i) cout << A[i] << " \n"[i == N-1];
    }
    else {
        cout << ans_B << "\n";
        for (int i = 0; i < N; ++i) cout << B[i] << " \n"[i == N-1];
    }
}

int32_t main() {
    fastIO();
    
    int t = 1; // cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        // cout << "Case #" << _ << ": ";
        solve();
    }
    
    return 0;
}

#else

#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
// #define double __float80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;

// #define X first
// #define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

template <size_t D, typename T> struct Vec : vector<Vec<D-1, T>> {
    static_assert(D >= 1, "Vector dimension must be greater than zero!");
    template <typename... Args> Vec(int n = 0, Args... args) : vector<Vec<D-1, T>>(n, Vec<D-1, T>(args...)) {}
};

template <typename T> struct Vec<1, T> : vector<T> {
    Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {}
};

template <class F>
inline constexpr decltype(auto) lambda_fix(F&& f) {
    return [f = std::forward<F>(f)](auto&&... args) {
        return f(f, std::forward<decltype(args)>(args)...);
    };
}

#ifdef local
#define fastIO() void()
#define debug(...) \
    _color.emplace_back("\u001b[31m"), \
    fprintf(stderr, "%sAt [%s], line %d: (%s) = ", _color.back().c_str(), __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), _color.pop_back(), \
    fprintf(stderr, "%s", _color.back().c_str())
#define print(...) \
    fprintf(stdout, "%s", "\u001b[36m"), \
    _P(__VA_ARGS__), \
    fprintf(stdout, "%s", "\u001b[0m")

deque<string> _color{"\u001b[0m"};

template <typename T> concept is_string = is_same_v<T, string&> or is_same_v<T, const string&>;
template <typename T> concept is_iterable = requires (T _t) {begin(_t);};

template <typename T> inline void _print_err(T &&_t);
template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(const tuple<U...> &_t);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(tuple<U...> &_t);
template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu);

inline void _do() {cerr << "\n";};
template <typename T> inline void _do(T &&_t) {_print_err(_t), cerr << "\n";}
template <typename T, typename ...U> inline void _do(T &&_t, U &&..._u) {_print_err(_t), cerr << ", ", _do(_u...);}
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#define print(...) _P(__VA_ARGS__)
#endif

inline void _P() {cout << "\n";};
template <typename T> inline void _P(T &&_t) {cout << _t << "\n";}
template <typename T, typename ...U> inline void _P(T &&_t, U &&..._u) {cout << _t << " ", _P(_u...);}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

inline int getRand(int L, int R) {
    if (L > R) swap(L, R);
    return (int)(rng() % ((uint64_t)R - L + 1) + L);
}

template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

/// below are Fast I/O and _print_err templates ///

/*
/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///

#include <unistd.h>

const int S = 65536;

int OP = 0;
char OB[S];

inline char RC() {
    static char buf[S], *p = buf, *q = buf;
    return p == q and (q = (p = buf) + read(0, buf, S)) == buf ? -1 : *p++;
}

inline int RI() {
    static char c;
    int a;
    while (((c = RC()) < '0' or c > '9') and c != '-' and c != -1);
    if (c == '-') {
        a = 0;
        while ((c = RC()) >= '0' and c <= '9') a *= 10, a -= c ^ '0';
    }
    else {
        a = c ^ '0';
        while ((c = RC()) >= '0' and c <= '9') a *= 10, a += c ^ '0';
    }
    return a;
}

inline void WI(int n, char c = '\n') {
    static char buf[20], p;
    if (n == 0) OB[OP++] = '0';
    p = 0;
    if (n < 0) {
        OB[OP++] = '-';
        while (n) buf[p++] = '0' - (n % 10), n /= 10;
    }
    else {
        while (n) buf[p++] = '0' + (n % 10), n /= 10;
    }
    for (--p; p >= 0; --p) OB[OP++] = buf[p];
    OB[OP++] = c;
    if (OP > S-20) write(1, OB, OP), OP = 0;
}

/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
*/

#ifdef local

template <typename T> inline void _print_err(T &&_t) {cerr << _t;}

template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>) {
    string _tmp_color = _color.back();
    ++_tmp_color[3], _color.emplace_back(_tmp_color);
    cerr << _color.back() << "[";
    for (bool _first = true; auto &_x : _t) {
        if (!_first) cerr << ", ";
        _print_err(_x), _first = false;
    }
    cerr << "]" << (_color.pop_back(), _color.back());
}

template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu) {
    string _tmp_color = _color.back();
    ++_tmp_color[3], _color.emplace_back(_tmp_color);
    cerr << _color.back() << "(";
    _print_err(_tu.first), cerr << ", ", _print_err(_tu.second);
    cerr << ")" << (_color.pop_back(), _color.back());
    return os;
}

template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &) {
    cerr << ")" << (_color.pop_back(), _color.back());
}

template <size_t I = 0, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(const tuple<U...> &_t) {
    if (!I) {
        string _tmp_color = _color.back();
        ++_tmp_color[3], _color.emplace_back(_tmp_color);
        cerr << _color.back();
    }
    cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}

template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &) {
    cerr << ")" << (_color.pop_back(), _color.back());
}

template <size_t I = 0, typename ...U> inline typename enable_if<I <  sizeof...(U), void>::type _print_err(tuple<U...> &_t) {
    if (!I) {
        string _tmp_color = _color.back();
        ++_tmp_color[3], _color.emplace_back(_tmp_color);
        cerr << _color.back();
    }
    cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}

#endif

#endif