#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <cstdlib>
using namespace std;
long long count_triples(std::vector<int> H) {
int n = H.size();
long long ans = 0;
// Part I logically remains completely O(N sqrt N)
for(int i=0; i<n; ++i) {
int k = i + H[i];
if(k < n) {
int j = k - H[k];
if(i < j && j < k && H[j] == j - i) ans++;
}
}
for(int i=0; i<n; ++i) {
int k = i + H[i];
if(k < n) {
int j = i + H[k];
if(i < j && j < k && H[j] == k - j) {
if (j - i != k - j) ans++;
}
}
}
for(int k=0; k<n; ++k) {
int i = k - H[k];
if(i >= 0) {
int j = i + H[i];
if(i < j && j < k && H[j] == k - j) ans++;
}
}
for(int k=0; k<n; ++k) {
int i = k - H[k];
if(i >= 0) {
int j = k - H[i];
if(i < j && j < k && H[j] == j - i) {
if (j - i != k - j) ans++;
}
}
}
for(int i=0; i<n; ++i) {
int j = i + H[i];
if(j < n) {
int req = H[j] - H[i];
if(req > 0) {
int k = j + req;
if(k < n && H[k] == req) ans++;
}
}
}
const int OFFSET = 200005;
vector<vector<int>> groupD(400010);
vector<vector<int>> groupS(400010);
for(int x=0; x<n; ++x) {
groupD[H[x] - x + OFFSET].push_back(x);
groupS[H[x] + x].push_back(x);
}
for(int j=1; j<n-1; ++j) {
int D_j = H[j] - j + OFFSET;
int S_j = H[j] + j;
int min_i = j - H[j] + 1;
auto it_start_D = lower_bound(groupD[D_j].begin(), groupD[D_j].end(), min_i);
auto it_end_D = lower_bound(groupD[D_j].begin(), groupD[D_j].end(), j);
int count_D = distance(it_start_D, it_end_D);
int max_k = j + H[j] - 1;
auto it_start_S = upper_bound(groupS[S_j].begin(), groupS[S_j].end(), j);
auto it_end_S = upper_bound(groupS[S_j].begin(), groupS[S_j].end(), max_k);
int count_S = distance(it_start_S, it_end_S);
if (count_D <= count_S) {
for(auto it = it_start_D; it != it_end_D; ++it) {
int i = *it;
int u = H[i];
int k = j + u;
if(k < n && H[k] == H[j] - u) {
if(u != H[j] - u) ans++;
}
}
} else {
for(auto it = it_start_S; it != it_end_S; ++it) {
int k = *it;
int v = H[k];
int i = j - v;
if(i >= 0 && H[i] == H[j] - v) {
if(H[i] != v) ans++;
}
}
}
}
return ans;
}
std::vector<int> construct_range(int M, int K) {
auto start_time = std::chrono::steady_clock::now();
// Massive block parameters, enabled safely by O(W) evaluation
int B = 2000;
int W = 900;
if (M < B) {
B = M;
W = std::max(1, B / 2 - 1);
}
std::vector<int> block(B);
for(int i = 0; i < B; ++i) {
block[i] = (rand() % W) + 1;
}
std::vector<int> score(W + 1, 0);
std::vector<int> modified;
modified.reserve(W + 1);
auto add_score = [&](int v) {
if (v > 0 && v <= W) {
if (score[v] == 0) modified.push_back(v);
score[v]++;
}
};
int passes = 0;
while (true) {
passes++;
// Keep optimizing until 0.65s (Comfortably safe against 1.0s limit)
if (passes % 2 == 0) {
auto now = std::chrono::steady_clock::now();
if (std::chrono::duration<double>(now - start_time).count() > 0.65) break;
}
for(int x = 0; x < B; ++x) {
modified.clear();
// Subcase 1: 'x' is the third element (k)
for(int d2 = 1; d2 <= W; ++d2) {
int j = (x - d2 + B) % B;
int h2 = block[j];
if (h2 == d2) {
for(int d1 = 1; d1 <= W - d2; ++d1) {
int i = (j - d1 + B) % B;
int h1 = block[i];
if (h1 == d1) add_score(d1 + d2);
else if (h1 == d1 + d2) add_score(d1);
}
}
int d1_a = h2;
if (d1_a > 0 && d1_a + d2 <= W) {
int i = (j - d1_a + B) % B;
int h1 = block[i];
if (h1 == d2) add_score(d1_a + d2);
else if (h1 == d1_a + d2) add_score(d2);
}
int d1_b = h2 - d2;
if (d1_b > 0 && d1_b + d2 <= W) {
int i = (j - d1_b + B) % B;
int h1 = block[i];
if (h1 == d1_b) add_score(d2);
else if (h1 == d2) add_score(d1_b);
}
}
// Subcase 2: 'x' is the middle element (j)
for(int d2 = 1; d2 <= W; ++d2) {
int k = (x + d2) % B;
int h3 = block[k];
if (h3 == d2) {
for(int d1 = 1; d1 <= W - d2; ++d1) {
int i = (x - d1 + B) % B;
int h1 = block[i];
if (h1 == d1) add_score(d1 + d2);
else if (h1 == d1 + d2) add_score(d1);
}
}
int d1_a = h3;
if (d1_a > 0 && d1_a + d2 <= W) {
int i = (x - d1_a + B) % B;
int h1 = block[i];
if (h1 == d2) add_score(d1_a + d2);
else if (h1 == d1_a + d2) add_score(d2);
}
int d1_b = h3 - d2;
if (d1_b > 0 && d1_b + d2 <= W) {
int i = (x - d1_b + B) % B;
int h1 = block[i];
if (h1 == d1_b) add_score(d2);
else if (h1 == d2) add_score(d1_b);
}
}
// Subcase 3: 'x' is the first element (i)
for(int d1 = 1; d1 <= W; ++d1) {
int j = (x + d1) % B;
int h2 = block[j];
if (h2 == d1) {
for(int d2 = 1; d2 <= W - d1; ++d2) {
int k = (j + d2) % B;
int h3 = block[k];
if (h3 == d2) add_score(d1 + d2);
else if (h3 == d1 + d2) add_score(d2);
}
}
int d2_a = h2;
if (d2_a > 0 && d1 + d2_a <= W) {
int k = (j + d2_a) % B;
int h3 = block[k];
if (h3 == d1) add_score(d1 + d2_a);
else if (h3 == d1 + d2_a) add_score(d1);
}
int d2_b = h2 - d1;
if (d2_b > 0 && d1 + d2_b <= W) {
int k = (j + d2_b) % B;
int h3 = block[k];
if (h3 == d1) add_score(d2_b);
else if (h3 == d2_b) add_score(d1);
}
}
int best_v = block[x];
int max_s = -1;
int ties = 0;
for(int v : modified) {
if (score[v] > max_s) {
max_s = score[v];
best_v = v;
ties = 1;
} else if (score[v] == max_s) {
ties++;
if (rand() % ties == 0) best_v = v;
}
score[v] = 0;
}
if (max_s <= 0) {
best_v = (rand() % W) + 1;
}
block[x] = best_v;
}
}
// Safely unroll our densely packed O(W) block
// W < B/2 ensures boundary tiling yields zero artifact overlap.
std::vector<int> H(M);
for(int i = 0; i < M; ++i) {
H[i] = block[i % B];
}
return H;
}
