#include "bits/stdc++.h"
using namespace std;

namespace st {
    static constexpr int size = 1 << 20;
    int tree[size * 2 - 1];

    void add(int i, int v) {
        int x = size + i - 1;
        tree[x] += v;
        while (x) {
            x = (x - 1) / 2;
            tree[x] = max(tree[x * 2 + 1], tree[x * 2 + 2]);
        }
    }
} // namespace st

signed main() {
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#else
    freopen("input.txt", "r", stdin);
#endif
    int n, m;
    cin >> n >> m;
    vector<int> c(n);
set<int> Q;
    for (int i = 0; i < n; i++) {
        cin >> c[i];
Q.insert(c[i]);
        c[i]--;
        st::add(c[i], 1);
    }

assert(Q.size() == m);

    vector<int> ans(m, n);

    {
        vector<vector<vector<int>>> B(m);
        for (int i = 0; i < n; i += 2) {
            if (i + 1 == n) {
                B[c[i]].push_back(vector<int>(1, c[i]));
            } else {
                B[c[i]].push_back(vector<int>{c[i], c[i + 1]});
                if (c[i + 1] != c[i]) {
                    B[c[i + 1]].push_back(vector<int>{c[i], c[i + 1]});
                }
            }
        }
        for (int i = 0; i < m; i++) {
            int cnt = 0;
            int cnt2 = 0;
            for (auto v : B[i]) {
                for (int x : v) {
                    cnt += 1;
                    cnt2 += x != i;
                    st::add(x, -1);
                }
            }
            ans[i] = min(ans[i], n - cnt - st::tree[0] + cnt2);
            for (auto v : B[i]) {
                for (int x : v) {
                    st::add(x, 1);
                }
            }
        }
    }

    {
        vector<vector<vector<int>>> B(m);
        for (int i = -1; i < n; i += 2) {
            if (i + 1 == n) {
                B[c[i]].push_back(vector<int>(1, c[i]));
            } else if (i == -1) {
                B[c[i + 1]].push_back(vector<int>{c[i + 1]});
            } else {
                B[c[i]].push_back(vector<int>{c[i], c[i + 1]});
                if (c[i + 1] != c[i]) {
                    B[c[i + 1]].push_back(vector<int>{c[i], c[i + 1]});
                }
            }
        }
        for (int i = 0; i < m; i++) {
            int cnt = 0;
            int cnt2 = 0;
            for (auto v : B[i]) {
                for (int x : v) {
                    cnt += 1;
                    cnt2 += x != i;
                    st::add(x, -1);
                }
            }
            ans[i] = min(ans[i], n - cnt - st::tree[0] + cnt2);
            for (auto v : B[i]) {
                for (int x : v) {
                    st::add(x, 1);
                }
            }
        }
    }

    for (int i = 0; i < m; i++) {
        cout << ans[i] << '\n';
    }
}