#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int S=350;
ll EasyPart(vector<int> H){
int n=H.size();
ll ans=0;
for(int mid=1;mid<n-1;mid++){
int L=mid-H[mid];
if(L>=0){
if(H[L]>H[mid]){
int R=L+H[L];
if(R<n && H[R]==R-mid){
ans++;
}
}
int R=mid+H[L];
if(R<n && H[R]==R-L){
ans++;
}
}
int R=mid+H[mid];
if(R<n){
if(H[R]>H[mid]){
int L=R-H[R];
if(L>=0 && H[L]==mid-L){
ans++;
}
}
int L=mid-H[R];
if(L>=0 && H[L]==R-L){
ans++;
}
}
L=mid-H[mid];
R=mid+H[mid];
if(L>=0 && R<n && max(H[L],H[R])==2*H[mid] && min(H[L],H[R])==H[mid]){
ans--;
}
}
return ans;
}
ll count_triples(vector<int> H) {
int n=H.size();
ll ans=EasyPart(H);
{
vector<vector<int>> Ls(n),Rs(n);
for(int i=0;i<n;i++){
if(i+H[i]<n)Ls[i+H[i]].pb(H[i]);
if(i-H[i]>=0)Rs[i-H[i]].pb(H[i]);
}
for(int mid=0;mid<n;mid++){
sort(Ls[mid].begin(),Ls[mid].end());
sort(Rs[mid].begin(),Rs[mid].end());
int j=(int)Rs[mid].size()-1;
for(int x:Ls[mid]){
while(j>=0 && x+Rs[mid][j]>H[mid]){
j--;
}
if(j>=0 && x+Rs[mid][j]==H[mid]){
ans++;
}
}
}
}
map<int,vector<int>> Ls;
for(int i=0;i<n;i++){
Ls[H[i]-i].pb(i);
}
vector<int> large;
for(auto& it:Ls){
if(it.second.size()>=S)large.pb(it.first);
else{
for(int a=0;a<it.second.size();a++){
for(int b=a+1;b<it.second.size();b++){
int i=it.second[a];
int j=it.second[b];
int k=i+H[j];
if(k<n && H[i]==k-j && H[k]==j-i && H[i]!=H[k]){
ans++;
}
}
}
}
}
for(int k=0;k<n;k++){
for(int x:large){
int j2=H[k]+k-x;
if(j2%2==0){
int j=j2/2;
int i=j-H[k];
if(j<k && i>=0 && H[j]==k-i && H[i]==k-j && H[i]!=H[k]){
ans++;
}
}
}
}
return ans;
}
mt19937 rng(time(0));
vector<int> construct_range(int M, int K) {
vector<int> S={0};
vector<bool> used(2*M,false);
vector<bool> done(2*M,false);
vector<int> cnt(2*M,1);
used[0]=true;
int was=0;
while(true){
vector<int> best={};
int mx=was;
for(int i=2;i<2*M;i+=2){
if(!used[i]){
int now=was+cnt[i];
if(mx<now){
mx=now;
best={i};
}else if(mx==now){
best.pb(i);
}
}
}
if(mx==was)break;
int idx=best[rng()%best.size()];
for(int x:S){
int z=x+idx;
if(z<2*M && !done[z]){
done[z]=true;
for(int y:S){
int z=x+idx-y;
if(0<z&&z<2*M)cnt[z]--;
}
}
}
for(int i=0;i<2*M;i+=2){
int z=i+idx;
if(0<z&&z<2*M && !done[z]){
cnt[i]++;
}
}
S.pb(idx);
used[idx]=true;
was=mx;
}
vector<int> H(M);
H[0]=1;
for(int i=(int)S.size()-1;i>=0;i--){
for(int j=0;j<i;j++){
int X=S[i];
int Y=S[j];
if(X>Y)swap(X,Y);
if(X+Y<2*M){
H[(X+Y)/2]=(Y-X)/2;
}
}
}
double start=(double)clock()/CLOCKS_PER_SEC;
double duration=-1;
ll now=count_triples(H);
while(true){
int i=rng()%M;
int best=H[i];
for(int j=max(1,best-3);j<=min(M,best+3);j++){
if(j!=best){
H[i]=j;
ll tmp=count_triples(H);
if(tmp>now || (tmp==now && rng()%2==0)){
now=tmp;
best=j;
}
}
}
H[i]=best;
if(now>=K)return H;
double now=(double)clock()/CLOCKS_PER_SEC;
if(duration<0)duration=now-start;
if(now-start+duration>1.8)break;
}
return H;
}
