#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;
// Case 1: H[i]=k-i, H[j]=j-i, H[k]=k-j
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++;
}
}
// Case 2: H[i]=k-i, H[j]=k-j, H[k]=j-i
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++;
}
}
}
// Case 3: H[i]=j-i, H[j]=k-j, H[k]=k-i
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++;
}
}
// Case 4: H[i]=k-j, H[j]=j-i, H[k]=k-i
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++;
}
}
}
// Case 5: H[i]=j-i, H[j]=k-i, H[k]=k-j
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: H[i]=k-j, H[j]=k-i, H[k]=j-i
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);
// W = 80 operates safely under the 1s time limit and ensures a massive score density.
int W = 80;
std::vector<int> score(W + 1, 0);
for(int i = 0; i < M; ++i) {
std::fill(score.begin(), score.end(), 0);
int start_j = std::max(0, i - W);
// Greedily count up overlapping triples for all permutations in the window
for(int j = start_j; j < i - 1; ++j) {
int h1 = H[j];
int c = i - j;
for(int k = j + 1; k < i; ++k) {
int h2 = H[k];
int a = k - j;
int b = i - k;
if (h1 == a) {
if (h2 == b) score[c]++;
else if (h2 == c) score[b]++;
} else if (h1 == b) {
if (h2 == a) score[c]++;
else if (h2 == c) score[a]++;
} else if (h1 == c) {
if (h2 == a) score[b]++;
else if (h2 == b) score[a]++;
}
}
}
// Pick the height that completes the maximum mythical triples terminating strictly at 'i'
int best_v = 1;
int max_s = -1;
for(int v = 1; v <= W; ++v) {
if (score[v] > max_s) {
max_s = score[v];
best_v = v;
}
}
H[i] = best_v;
}
return H;
}
