#include "triples.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
typedef pair<int,int> pii;
const int MAXN = 5e5+10;
const int SQRT = 500;
void chmx(auto &a, auto b){ a = max(a,b); }
void chmn(auto &a, auto b){ a = min(a,b); }
int n, h[MAXN];
ll ans;
void cek(int i, int j, int k){
if(1<=i && i<j && j<k && k<=n){
// if(ty==1 && h[i] <= max(h[j], h[k])) return;
int mxa = -1, mxb = -1, mna = MAXN, mnb = MAXN, tota=0, totb=0;
chmx(mxa, h[i]); chmn(mna, h[i]); tota += h[i];
chmx(mxa, h[j]); chmn(mna, h[j]); tota += h[j];
chmx(mxa, h[k]); chmn(mna, h[k]); tota += h[k];
chmx(mxb, j-i); chmn(mnb, j-i); totb += j-i;
chmx(mxb, k-j); chmn(mnb, k-j); totb += k-j;
chmx(mxb, k-i); chmn(mnb, k-i); totb += k-i;
if(mxa==mxb && mna==mnb && tota==totb) ans++;
}
}
vector<int> vec[MAXN], tag[MAXN];
long long count_triples(std::vector<int> H) {
n = H.size(); ans = 0;
for(int i=0; i<=2*n; i++){
vec[i].clear(); tag[i].clear();
}
for(int i=1; i<=n; i++) h[i] = H[i-1];
for(int i=1; i<=n; i++){ // i max
int k = h[i]+i;
cek(i, i+h[k], k);
if(i+h[k] != k-h[k]) cek(i, k-h[k], k);
}
for(int k=1; k<=n; k++){ // k max
int i = k-h[k];
cek(i, i+h[i], k);
if(i+h[i] != k-h[i]) cek(i, k-h[i], k);
}
for(int i=1; i<=n; i++){ // j max
int j = i+h[i];
if(h[i] != i+h[j]-j) cek(i, j, i+h[j]);
}
for(int i=1; i<=n; i++)
vec[h[i]-i + n].pb(i);
for(int idx=0; idx<=2*n; idx++){ // j max
if(vec[idx].size() < SQRT){
for(int a=0; a<vec[idx].size(); a++){
for(int b=a+1; b<vec[idx].size(); b++){
int i = vec[idx][a], j = vec[idx][b];
cek(i, j, h[j]+i);
}
}
} else {
for(auto i : vec[idx])
tag[h[i]+i].pb(i);
for(int k=1; k<=n; k++){
for(auto j : tag[h[k]+k]){
cek(k-h[j], j, k);
}
}
for(auto i : vec[idx])
tag[h[i]+i].clear();
}
}
return ans;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
std::vector<int> construct_range(int M, int K) {
vector<int> ans;
while(ans.size() < M){
vector<int> te =
{1, 3, 2, 3, 4, 1, 2, 1, 3, 1, 2, 1, 4, 3, 2, 3, 1, 2, 1, 4};
for(auto in : te) ans.pb(in);
}
return ans;
/*
for(int i=0; i<M; i++){
for(int j=i+1; j<M; j++){
for(int p=1; p<=4; p++){
for(int q=1; q<=4; q++){
vector <int> cob = te;
cob[i] = p; cob[j] = q;
if(count_triples(cob) == K){
cout << " ket\n";
for(auto in : cob) cout << in << ' ';
cout << '\n';
}
}
}
}
}
cout << "nein\n";
ll mx = -1; vector<int> ans;
while(mx < K){
vector<int> te;
for(int i=0; i<M; i++) te.pb(rng()%4+1);
ll has = count_triples(te);
for(int i=0; i<M; i++){
int aw = te[i];
te[i] = rng()%4+1;
ll baru = count_triples(te);
if(baru < has)
te[i] = aw;
}
for(int i=0; i<M; i++){
int aw = te[i];
te[i] = rng()%4+1;
ll baru = count_triples(te);
if(baru < has)
te[i] = aw;
}
has = count_triples(te);
if(has > mx){
mx = has;
ans = te;
cout << has << " ket\n";
for(auto in : ans) cout << in << ' ';
cout << '\n';
}
}
return ans;
*/
}
