/**
* JOI 2016/2017 Final Round - Task 5: Rope
* Solution based on Pair Parity Observation.
* * Logic:
* The folding process partitions the rope into adjacent pairs that are merged.
* We analyze adjacent pairs in different alignments (starting at index 0 or 1).
* We aim to maximize matches for a Target Color C and an optimal Partner Color Y.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
const int INF = 1e9;
// Global variables to store frequencies and answers
int N, M;
vector<int> ar;
vector<int> ans;
vector<int> app; // Total appearance count of each color
vector<int> d; // Colors sorted by frequency
// Updates the answer for color 'a' with a new minimum cost 'b'
void chmin(int& a, int b) {
if (b < a) a = b;
}
// Solver function for a specific sub-segment of the rope
// n: length of the segment to consider
// offset: starting index in the global array 'ar'
// L, R: Boundary colors (leftover cords) that are NOT part of pairs
// (passed as -1 if they don't exist in the current cut)
void solve(int n, int offset, int L, int R) {
// If n is odd, one element is left unpaired inside the range.
// The passed L and R account for boundary "singletons".
// 1. Identify pairs (u, v) in this alignment
vector<pair<int, int>> ps;
ps.reserve(n / 2);
for (int i = 0; i < n - 1; i += 2) {
int u = ar[offset + i];
int v = ar[offset + i + 1];
if (u > v) swap(u, v);
ps.push_back({u, v});
}
// Sort pairs to count unique overlaps efficiently
sort(ps.begin(), ps.end());
// Unique the pairs to iterate distinct combinations
vector<pair<int, int>> unique_ps = ps;
unique_ps.erase(unique(unique_ps.begin(), unique_ps.end()), unique_ps.end());
// Count occurrences of each specific pair
vector<int> pscnt(unique_ps.size(), 0);
// Use lower_bound to find index in unique_ps
for (size_t i = 0; i < ps.size(); ++i) {
int idx = lower_bound(unique_ps.begin(), unique_ps.end(), ps[i]) - unique_ps.begin();
pscnt[idx]++;
}
// 2. Optimization 1: Calculate cost based on adjacent pairs found
for (size_t i = 0; i < unique_ps.size(); ++i) {
int u = unique_ps[i].first;
int v = unique_ps[i].second;
// Cost formula explanation:
// We want to keep all 'u' and all 'v'.
// Total instances = app[u] + app[v].
// However, pscnt[i] is the number of times u and v appear as a specific merged pair.
// In those merged pairs, we gain +1 match total (either u or v matches),
// whereas app[u]+app[v] counts +2. So we subtract pscnt[i] to correct the gain.
// Total Gain = app[u] + app[v] - pscnt[i].
// Cost = Total_Rope_Length - Total_Gain.
// Note: The rope length for cost calculation is the original N.
int val = N - (app[u] + app[v] - pscnt[i]);
chmin(ans[u], val);
chmin(ans[v], val);
}
// 3. Optimization 2: Fallback for high-frequency colors that might NOT be adjacent
// We try to pair color 'i' with the most frequent color 'j' such that
// the pair (i, j) was NOT handled in the loop above (i.e., not strictly adjacent).
// We iterate through colors sorted by frequency (descending)
for (int i = 0; i < M; ++i) {
int color_u = d[i];
// Find the best partner color_v (d[j])
int j = 0;
while (j < M) {
int color_v = d[j];
if (color_u == color_v) {
j++;
continue;
}
// Check if this pair (u, v) exists in the current adjacent pairing.
// If it does, we already processed the optimal case for it in step 2.
// If it does NOT, the overlap is 0, so Gain = app[u] + app[v].
// We check existence using binary search on unique_ps.
int mn = min(color_u, color_v);
int mx = max(color_u, color_v);
if (binary_search(unique_ps.begin(), unique_ps.end(), make_pair(mn, mx))) {
j++; // This pair was adjacent, so handled above. Skip.
} else {
// Found best non-adjacent partner.
int val = N - (app[color_u] + app[color_v]);
chmin(ans[color_u], val);
chmin(ans[color_v], val);
break; // Since d is sorted by frequency, the first valid j is the best.
}
}
}
}
int main() {
// Fast I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (!(cin >> N >> M)) return 0;
if (M == 1) {
cout << "0\n";
return 0;
}
ar.resize(N);
app.assign(M, 0);
ans.assign(M, INF);
for (int i = 0; i < N; ++i) {
cin >> ar[i];
ar[i]--; // Convert to 0-based index
app[ar[i]]++;
}
// Prepare 'd' array: colors sorted by frequency descending
d.resize(M);
for (int i = 0; i < M; ++i) d[i] = i;
sort(d.begin(), d.end(), [&](int a, int b) {
return app[a] > app[b];
});
// We try 4 configurations to cover all alignment parities and boundary conditions
// 1. Full array, starting at 0
solve(N, 0, -1, -1);
// 2. Skip first element, starting at 1 (Shifted alignment)
solve(N - 1, 1, ar[0], -1);
// 3. Skip last element (Alignment starting at 0, but N-1 length)
solve(N - 1, 0, -1, ar[N - 1]);
// 4. Skip first and last (Shifted alignment, N-2 length)
solve(N - 2, 1, ar[0], ar[N - 1]);
for (int i = 0; i < M; ++i) {
cout << ans[i] << "\n";
}
return 0;
}
