#include "triples.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((ll)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto i:v)cout<<i<<" ";cout<<"\n";}
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vv;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
const ll MAXN=2e5;
long long count_triples(vector<int> __h) {
ll n=SZ(__h);
vv h;
fore(i,0,n)h.pb(__h[i]);
ll fg=1;
fore(i,0,n-1)fg&=h[i]<=h[i+1];
set<vv> all;
auto israre=[&](ll i, ll j, ll k){
return h[i]==abs(j-k)&&h[j]==abs(i-k)&&h[k]==abs(i-j);
};
auto good=[&](vv s){
assert(SZ(s)==3);
vector<ll> ds,hs;
fore(i,0,3)fore(j,i+1,3)ds.pb(abs(s[i]-s[j]));
fore(i,0,3)hs.pb(h[s[i]]);
sort(ALL(hs));
sort(ALL(ds));
return ds==hs;
};
auto eval=[&](ll i, ll j, ll k, bool allow=0){
vv s={i,j,k}; sort(ALL(s));
if(s[0]==s[1]||s[1]==s[2])return;
if(s[0]<0||s[2]>=n)return;
if(good(s)&&(allow||!israre(i,j,k)))all.insert(s);
};
auto doit=[&](ll i, ll j){
if(j<0||j>=n)return;
vv ind={i,j};
fore(wd,0,2)fore(wf,0,2)fore(ws,0,2){
ll d=h[ind[wd]];
ll f=ind[wf];
ll s=ws?1:-1;
ll k=f+s*d;
eval(i,j,k);
}
};
fore(i,0,n)doit(i,i+h[i]),doit(i,i-h[i]);
if(fg)return SZ(all);
// faltan las otras, las rare
ll res=0;
if(*max_element(ALL(h))<50){
fore(i,0,n){
ll b=h[i];
fore(j,max(0ll,i-b+1),i){
eval(j,i,j+b,1);
}
}
}
else {
map<ll,vv> h0,h1;
vv vis(n);
map<ll,bitset<MAXN>>mp1;
fore(i,0,n){
h0[h[i]-i].pb(i);
mp1[h[i]+i][n-h[i]]=1;
}
for(auto [asd,vec]:h0){
bitset<MAXN>b0;
for(auto i:vec)b0[h[i]]=1;
ll pr=0;
reverse(ALL(vec));
for(auto i:vec){
ll v=h[i];
ll d=n-v; d-=pr;
assert(d>0);
b0<<=d; pr+=d;
auto &b1=mp1[v+i];
ll c=(b0&b1).count();
res+=c;
}
}
}
// for(auto v:all){
// for(auto i:v)cout<<i<<" ";;cout<<": ";
// for(auto i:v)cout<<h[i]<<" ";;cout<<"\n";
// }
return SZ(all)+res;
}
vector<int> construct_range(int M, int K) {
ll n=M;
vector<int> a={1,2,1};
ll u=2;
while(SZ(a)<n){
ll v=SZ(a)+1;
fore(i,0,u+1)a.pb(v-i);
u=v;
}
while(SZ(a)>n||a.back()>=n)a.pop_back();
return a;
}
