#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=100005;
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;
map<int,vector<int>> Rs;
for(int i=0;i<n;i++){
Ls[H[i]-i].pb(H[i]);
}
for(int i=n-1;i>=0;i--){
int j=(int)Rs[H[i]+i].size()-1;
for(int x:Ls[H[i]-i]){
if(x>=H[i])break;
while(j>=0 && x+Rs[H[i]+i][j]>=H[i])j--;
if(j>=0 && x!=Rs[H[i]+i][j] && x+Rs[H[i]+i][j]==H[i])ans++;
}
Rs[H[i]+i].pb(H[i]);
}
/*map<int,bitset<N>> Ls;
map<int,bitset<N>> all;
for(int i=0;i<n;i++){
if(H[i]<N)Ls[H[i]-i].set(H[i]);
}
for(int i=n-1;i>=0;i--){
bitset<N> Rs=all[H[i]+i]>>(N-H[i]);
ans+=(Ls[H[i]-i]&Rs).count();
if(H[i]%2==0 && Ls[H[i]-i].test(H[i]/2) && Rs.test(H[i]/2))ans--;
if(N-H[i]>=0)all[H[i]+i].set(N-H[i]);
}*/
return ans;
}
mt19937 rng(time(0));
vector<int> Gen(int M){
vector<int> ans;
for(int i=0;i<M;i++){
ans.pb(rng()%(M-1)+1);
}
return ans;
}
vector<int> construct_range(int M, int K) {
vector<int> ans=Gen(M);
vector<int> best;
ll mx=0;
printf("Solving %i %i\n",M,K);
double start=(double)clock()/CLOCKS_PER_SEC;
while(true){
ll now=count_triples(ans);
if(now>mx){
mx=now;
best=ans;
printf("%lld\n",mx);
}
if(mx>=K)break;
ans=Gen(M);
double tme=(double)clock()/CLOCKS_PER_SEC-start;
/*if(tme>60){
printf("Failed %i %i\n",M,K);
return best;
}*/
}
printf("Solved %i %i\n",M,K);
return ans;
}
