#include "triples.h"
#include <bits/stdc++.h>
#define el '\n'
typedef long long llo;
#define fn(i,a,b) for (int i = a; i <= b; i++)
#define rn(i,a,b) for (int i = a; i >= b; i--)
using namespace std;
long long count_triples(vector <signed> H)
{
int n = H.size();
long long ans = 0;
//Hj = j - i
for(int j = 0; j < n; j++)
{
for(int i = max(0, j - H[j] + 1); i < j && i + H[j] < n; i++)
{
int k = i + H[j];
int x = H[k], y = H[i];
int d1 = j - i, d2 = k - j;
if((H[k] == d1 && H[i] == d2) || (H[k] == d2 && H[i] == d1)) ans++;
}
int l = j - H[j];
if(l >= 0)
{
int x = H[l];
int y = H[j] - x;
if(y > 0)
{
if(H[l + x] == y) ans++;
if(y != x && H[l + y] == y) ans++;
}
}
int r = j + H[j];
if(r < n)
{
int x = H[r];
int y = H[j] - x;
if(y > 0)
{
if(H[j + x] == y) ans++;
if(y != x && H[j + y] == y) ans++;
}
}
}
return ans;
}
std::vector<int> construct_range(int M, int K){
int n = M;
vector<int> chosen = {0}, score(2*n, -1e9), X, Y, H(n);
vector<bool> used(2*n, 0);
for(int i = 2; i < 2*n; i += 2){
score[i] = 1;
}
while(true){
int best_score = -1e9, best_pos = -1;
fn(i,0,2*n-1){
if(score[i] > best_score){
best_score = score[i];
best_pos = i;
}
}
if (best_score <= 0) break;
for(int x : chosen){
int sum = x + best_pos;
if(sum >= 2*n || used[sum]) continue;
used[sum] = 1;
X.push_back(min(x, best_pos));
Y.push_back(max(x, best_pos));
for(int y : chosen){
int z = sum - y;
if(z >= 0 && z < 2*n) score[z]--;
}
}
for(int i = best_pos; best_pos + i < 2*n; i += 2){
if (!used[best_pos + i]) score[i]++;
}
chosen.push_back(best_pos);
score[best_pos] = -1e9;
}
int cnt_set = 0;
for (int i = 0; i < (int)X.size(); ++i) {
int mid = (X[i] + Y[i]) >> 1;
int diff = (Y[i] - X[i]) >> 1;
if (mid >= 0 && mid < n && H[mid] == 0) {
H[mid] = diff;
cnt_set++;
}
}
for (int i = 0; i < n; ++i) {
if (H[i] == 0) H[i] = 1;
}
llo cnt = count_triples(H);
while (cnt < K) {
bool changed = false;
for (int i = 0; i < n; ++i) {
int best_val = H[i];
for (int j = 1; j < n; ++j) {
H[i] = j;
llo new_cnt = count_triples(H);
if (new_cnt > cnt) {
cnt = new_cnt;
best_val = j;
changed = true;
}
}
H[i] = best_val;
}
if (!changed) break;
}
return H;
}
