#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();
// B dictates the size of our periodic dense block
int B = 250;
int V = 100;
// Scale down gently if we are in a tiny testing subtask
if (M < B) {
B = M;
V = std::max(1, B / 2);
}
std::vector<int> block(B);
for(int i = 0; i < B; ++i) {
block[i] = (rand() % V) + 1;
}
// Rapidly resolves the strict mythical missing link
auto get_missing = [&](int hx, int hy, int a, int b, int c) -> int {
if (hx == a) {
if (hy == b) return c;
if (hy == c) return b;
} else if (hx == b) {
if (hy == a) return c;
if (hy == c) return a;
} else if (hx == c) {
if (hy == a) return b;
if (hy == b) return a;
}
return -1;
};
int iterations = 0;
while (true) {
iterations++;
// Keep ILS running to convergence but violently pull it out just before the 1.0s limit
if ((iterations & 127) == 0) {
auto now = std::chrono::steady_clock::now();
double elapsed = std::chrono::duration<double>(now - start_time).count();
if (elapsed > 0.85) break;
}
int i = rand() % B;
std::vector<int> score(V + 1, 0);
// Target 1: Map cyclic pairs where 'i' is the first peak
for(int d1 = 1; d1 <= V; ++d1) {
for(int d2 = 1; d1 + d2 <= V; ++d2) {
int j = (i + d1) % B;
int k = (i + d1 + d2) % B;
int req = get_missing(block[j], block[k], d1, d2, d1 + d2);
if (req > 0 && req <= V) score[req]++;
}
}
// Target 2: Map cyclic pairs where 'i' is the middle peak
for(int d1 = 1; d1 <= V; ++d1) {
for(int d2 = 1; d1 + d2 <= V; ++d2) {
int first = (i - d1 + B) % B;
int k = (i + d2) % B;
int req = get_missing(block[first], block[k], d1, d2, d1 + d2);
if (req > 0 && req <= V) score[req]++;
}
}
// Target 3: Map cyclic pairs where 'i' is the final peak
for(int d1 = 1; d1 <= V; ++d1) {
for(int d2 = 1; d1 + d2 <= V; ++d2) {
int first = (i - d1 - d2 + 2 * B) % B;
int j = (i - d2 + B) % B;
int req = get_missing(block[first], block[j], d1, d2, d1 + d2);
if (req > 0 && req <= V) score[req]++;
}
}
int best_v = block[i];
int max_s = -1;
int tie_count = 0;
// Reservoir sampling noise insertion (Prevents Greedy Flatlining)
for(int v = 1; v <= V; ++v) {
if (score[v] > max_s) {
max_s = score[v];
best_v = v;
tie_count = 1;
} else if (score[v] == max_s) {
tie_count++;
if (rand() % tie_count == 0) {
best_v = v;
}
}
}
block[i] = best_v;
}
// Safely unroll and tile the optimized radioactive cyclic block across the entire limit
std::vector<int> H(M);
for(int i = 0; i < M; ++i) {
H[i] = block[i % B];
}
return H;
}
