/**
* JOI 2016/2017 Final Round - Task 5: Rope
* * Solution Logic:
* 1. The problem reduces to finding a pivot k such that the cost is minimized.
* 2. We solve for the "Left Alignment" case and then reverse the rope for the "Right Alignment" case.
* 3. We use a threshold to distinguish between "Heavy" and "Light" colors.
* - Heavy Colors: Compute exact cost for all k using prefix sums. O(N log N) per color.
* - Light Colors: Identify ranges of k where the count increases using the number theory
* property of the folding. Use a sweep-line with RMQ to find the min cost.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF = 1e9;
int N, M;
vector<int> C; // Colors
vector<int> final_ans;
// Sparse Table for O(1) Range Minimum Query
struct SparseTable {
vector<vector<int>> st;
vector<int> log_table;
int n;
void build(const vector<int>& arr) {
n = arr.size();
log_table.resize(n + 1);
log_table[1] = 0;
for (int i = 2; i <= n; i++)
log_table[i] = log_table[i / 2] + 1;
int K = log_table[n];
st.assign(n, vector<int>(K + 1));
for (int i = 0; i < n; i++)
st[i][0] = arr[i];
for (int j = 1; j <= K; j++)
for (int i = 0; i + (1 << j) <= n; i++)
st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
int query(int L, int R) {
if (L > R) return INF;
int j = log_table[R - L + 1];
return min(st[L][j], st[R - (1 << j) + 1][j]);
}
};
void solve_pass(const vector<int>& current_colors) {
// 1. Calculate Total Size of Left Pile for each k [1, N-1]
// The Left Pile for pivot k contains indices in [1, k], [2k+1, 3k], [4k+1, 5k], ...
vector<int> total_size(N, 0); // 0-based index k corresponds to pivot k
for (int k = 1; k < N; ++k) {
int count = 0;
for (int m = 0; ; m += 2) {
int l = m * k + 1;
int r = (m + 1) * k;
if (l > N) break;
r = min(r, N);
count += (r - l + 1);
}
total_size[k] = count;
}
// Build RMQ on total_size to quickly query min(Size) in ranges
SparseTable rmq;
rmq.build(total_size);
// Group positions by color
vector<vector<int>> positions(M + 1);
for (int i = 0; i < N; ++i) {
positions[current_colors[i]].push_back(i + 1); // Store 1-based indices
}
// Threshold tuning: B ~ sqrt(N) * log(N) is usually optimal or just sqrt(N).
// With N=1,000,000, sqrt(N)=1000.
// Heavy colors approach takes O(N log N). Light takes O(Freq * sqrt(N)).
// A threshold of ~3000 balances the two well.
const int THRESHOLD = 3000;
for (int c = 1; c <= M; ++c) {
if (positions[c].empty()) continue;
if (positions[c].size() > THRESHOLD) {
// --- HEAVY COLOR STRATEGY ---
// Iterate all k. Use prefix sums to count occurrences efficiently.
vector<int> pref(N + 1, 0);
for (int p : positions[c]) pref[p] = 1;
for (int i = 1; i <= N; ++i) pref[i] += pref[i - 1];
for (int k = 1; k < N; ++k) {
int cnt = 0;
// Sum segments [1, k], [2k+1, 3k], ...
for (int m = 0; ; m += 2) {
int l = m * k + 1;
int r = (m + 1) * k;
if (l > N) break;
r = min(r, N);
cnt += (pref[r] - pref[l - 1]);
}
final_ans[c] = min(final_ans[c], total_size[k] - cnt);
}
} else {
// --- LIGHT COLOR STRATEGY ---
// A position p contributes to pivot k if floor((p-1)/k) is Even.
// This creates ranges of k. We collect these ranges and sweep.
vector<pair<int, int>> events;
events.reserve(positions[c].size() * 100); // Heuristic reservation
for (int p : positions[c]) {
int X = p - 1;
// Case q=0: k > X. Range [X+1, N-1]
if (X + 1 < N) {
events.push_back({X + 1, 1});
events.push_back({N, -1});
}
// Iterate even q >= 2
// Valid k range for quotient q is roughly (X/(q+1), X/q]
for (int q = 2; ; q += 2) {
int R = X / q;
if (R == 0) break; // k must be >= 1
int L = X / (q + 1) + 1;
// Intersect with valid pivots [1, N-1]
int r_bound = min(N - 1, R);
int l_bound = max(1, L);
if (l_bound <= r_bound) {
events.push_back({l_bound, 1});
events.push_back({r_bound + 1, -1});
}
if (L > R) continue; // Should not happen with logic but safe check
}
}
if (events.empty()) {
final_ans[c] = min(final_ans[c], rmq.query(1, N - 1));
continue;
}
sort(events.begin(), events.end());
int current_gain = 0;
int prev_k = 1;
// Sweep line
for (size_t i = 0; i < events.size(); ) {
int curr_k = events[i].first;
// Query the minimum Size for the range where gain was constant
if (curr_k > prev_k) {
int min_s = rmq.query(prev_k, min(curr_k - 1, N - 1));
if (min_s != INF) {
final_ans[c] = min(final_ans[c], min_s - current_gain);
}
}
// Update gain
while (i < events.size() && events[i].first == curr_k) {
current_gain += events[i].second;
i++;
}
prev_k = curr_k;
}
// Handle tail [Last Event, N-1]
if (prev_k < N) {
int min_s = rmq.query(prev_k, N - 1);
if (min_s != INF) {
final_ans[c] = min(final_ans[c], min_s - current_gain);
}
}
}
}
}
int main() {
// Optimize I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
C.resize(N);
for (int i = 0; i < N; ++i) cin >> C[i];
final_ans.assign(M + 1, INF);
// Pass 1: Consider "Left Aligned" folding patterns
solve_pass(C);
// Pass 2: Consider "Right Aligned" folding patterns (equivalent to Left Aligned on reversed rope)
vector<int> C_rev = C;
reverse(C_rev.begin(), C_rev.end());
solve_pass(C_rev);
for (int c = 1; c <= M; ++c) {
cout << final_ans[c] << "\n";
}
return 0;
}
