#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
using vi = vector<int>;
using ll = long long;
#define fst first
#define snd second
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
ll count_triples(vi h) {
const int n = sz(h);
const int sq = sqrt(n);
int ret = 0;
forn(i, n) {
int j = i + h[i];
if (j >= n) continue;
{
int k = j + h[j];
if (k < n && 2 * j != i + k && h[k] == k - i) ret++;
}
{
int k = j + h[j] - h[i];
if (j < k && k < n && 2 * j != i + k && h[k] == k - j) ret++;
}
}
forn(j, n) {
int i = j - h[j];
if (i < 0) continue;
{
int k = j + h[i];
if (k < n && h[k] == k - i) ret++;
}
{
int k = j + h[i] - h[j];
if (j < k && k < n && 2 * j != i + k && h[k] == k - j) ret++;
}
}
forn(j, n) {
int k = j + h[j];
if (k >= n) continue;
int i = j - h[k];
if (i >= 0 && h[i] == k - i) ret++;
}
vector<vi> diag1(2 * n), diag2(2 * n);
forn(i, n) {
diag1[h[i] - i + n].pb(i);
diag2[h[i] + i].pb(i);
}
for (auto d : diag1) {
if (sz(d) < sq) {
forn(idx1, sz(d)) forsn(idx2, idx1 + 1, sz(d)) {
int i = d[idx1], j = d[idx2];
int k = j + h[i];
if (k < n && h[j] == k - i && h[k] == j - i) ret++;
}
} else {
for (int j : d) for (int k : diag2[h[j] + j]) {
if (j >= k) continue;
int i = j - h[k];
if (i >= 0 && h[i] == k - j && h[j] == k - i) ret++;
}
}
}
return ret;
}
const int INF = 1e9;
vi construct_range(int M, int K) {
vi ret = {};
int best = 0;
int seed = -1247761304;
while (best < K) {
mt19937 rng(seed++);
int S = sqrt(6 * M);
S = uniform_int_distribution<int>(S * 2 / 3, S * 4 / 3 + 1)(rng);
set<int> s;
vi diag(S);
forn(i, S) {
diag[i] = uniform_int_distribution<int>(-M / 2, M * 3 / 2 + 1)(rng);
diag[i] /= 2, diag[i] *= 2;
if (s.count(diag[i])) i--;
else s.insert(diag[i]);
}
vi ans(M, INF);
forn(i, S) forsn(j, i + 1, S) {
int idx = (diag[i] + diag[j]) / 2;
int val = abs(diag[i] - diag[j]) / 2;
if (0 <= idx && idx < M && 1 <= val && val < M) ans[idx] = min(ans[idx], val);
}
forn(i, M) if (ans[i] == INF) {
ans[i] = uniform_int_distribution<int>(1, 2)(rng);
}
int triples = count_triples(ans);
if (triples > best) best = triples, ret = ans;
}
return ret;
}
