#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long count_triples(std::vector<int> H) {
int n = H.size();
long long ans = 0;
// Cases 1-5 logically remain O(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++;
}
}
}
// Case 6 Heavy-Light O(N sqrt N)
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) {
std::vector<int> H(M);
// Maximized Window bounded dynamically to O(M * W) logic. Safely executes in < 0.2s
int W = 6000;
std::vector<int> score(W + 1, 0);
std::vector<int> modified;
modified.reserve(W + 1);
// Fast Sparse-Array incrementor limits overhead to strictly required hits
auto add_score = [&](int v) {
if (score[v] == 0) modified.push_back(v);
score[v]++;
};
for(int i = 0; i < M; ++i) {
modified.clear();
int start = std::max(0, i - W);
for(int k = start; k < i; ++k) {
int h2 = H[k];
int b = i - k;
// Because H[k] must be one of the three required distances to form a valid pair,
// we isolate the mathematical limits to bypass O(W^2) blind nested searching.
if (h2 == b) {
for(int j = start; j < k; ++j) {
int h1 = H[j];
if (h1 == k - j) add_score(i - j);
else if (h1 == i - j) add_score(k - j);
}
} else {
int j2 = k - h2;
if (j2 >= start) {
int h1 = H[j2];
if (h1 == b) add_score(i - j2);
else if (h1 == i - j2) add_score(b);
}
int j3 = i - h2;
if (j3 >= start && j3 < k) {
int h1 = H[j3];
if (h1 == k - j3) add_score(b);
else if (h1 == b) add_score(k - j3);
}
}
}
int best_v = 1;
int max_s = -1;
// Rapid resolution + cleanup in sparse bounds
for(int v : modified) {
if (score[v] > max_s || (score[v] == max_s && v < best_v)) {
max_s = score[v];
best_v = v;
}
score[v] = 0;
}
H[i] = best_v;
}
return H;
}
