#include "triples.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<int> H;
ll n;
bool check(ll i,ll j,ll k){
if(i<0||j<0||k<0||i>=n||j>=n||k>=n)return 0;
ll s1[3],s2[3];
s1[0]=(abs(j-i));
s1[1]=(abs(k-i));
s1[2]=(abs(j-k));
sort(s1,s1+3);
if(s1[0]==0)return 0;
s2[0]=(H[i]);
s2[1]=(H[j]);
s2[2]=(H[k]);
sort(s2,s2+3);
return s1[0]==s2[0]&&s1[1]==s2[1]&&s1[2]==s2[2];
}
ll sub4(){
ll ans=0;
for(int i=n-1;i>1;i--){
ll x2=i-H[i];
if(x2<0)continue;
ll x3=x2+H[x2],x4=i-H[x2];
if(x3<i && i-x3==H[x3])ans++;
if(x3!=x4)
if(x4>x2 && x4-x2==H[x4])ans++;
}
return ans;
}
ll sub2(){
ll ans=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<=i+20;j++){
for(int k=j+1;k<n&&k<i+20;k++){
ans+=check(i,j,k);
}
}
}
return ans;
}
ll sub3(){
ll ans=0;
for(ll i=0;i<n;i++){
//Check M a b
while(1){
ll x2=i+H[i];
if(x2>=n)break;
ll x3=x2-H[x2],x4=i+H[x2];
if(x3>i && x3-i==H[x3])ans++;
if(x3!=x4)
if(x4<x2 && x2-x4==H[x4])ans++;
break;
}
//check a b M
while(1){
ll x2=i-H[i];
if(x2<0)break;
ll x3=x2+H[x2],x4=i-H[x2];
if(x3<i && i-x3==H[x3])ans++;
if(x3!=x4)
if(x4>x2 && x4-x2==H[x4])ans++;
break;
}
//check a M b
ll l=max(0LL,i-H[i]+1);
ll r=min(i,n-H[i]);
for(int j=l;j<r;j++){
ll x3=j+H[i];
if(H[j]==i-j&&H[x3]==x3-i)ans++;
else if(H[x3]==i-j&&H[j]==x3-i)ans++;
}
}
return ans;
}
ll full(){
ll ans=0;
ll typ=sqrt(n);
ll ntype=450;
vector<vector<int>> a(n+1,vector<int>(ntype,n));
vector<int> type(n);
for(int i=n-1;i>=0;i--){
if(i!=n-1){
for(int j=0;j<ntype;j++){
a[i][j]=a[i+1][j];
}
}
type[i]=H[i]/typ;
a[i][type[i]]=i;
}
for(ll i=0;i<n;i++){
//Check M a b
while(1){
ll x2=i+H[i];
if(x2>=n)break;
ll x3=x2-H[x2],x4=i+H[x2];
if(x3>i && x3-i==H[x3])ans++;
if(x3!=x4)
if(x4<x2 && x2-x4==H[x4])ans++;
break;
}
//check a b M
while(1){
ll x2=i-H[i];
if(x2<0)break;
ll x3=x2+H[x2],x4=i-H[x2];
if(x3<i && i-x3==H[x3])ans++;
if(x3!=x4)
if(x4>x2 && x4-x2==H[x4])ans++;
break;
}
//check a M b
ll l=max(0LL,i-H[i]+1);
ll r=min(i,n-H[i]);
/*for(int j=l;j<r;j++){
ll x3=j+H[i],dt=i-j,dt2=x3-i;
if(H[j]==dt&&H[x3]==dt2)ans++;
else if(H[x3]==dt&&H[j]==dt2)ans++;
}*/
/// check o M o
for(int j=0;j<ntype;j++){
ll mir=i-typ*(j+1),mar=i-typ*j;
mir=max(mir,l);
mar=min(mar,r);
mir=a[mir][j];
while(mir<mar){
ll x3=mir+H[i],dt=i-mir,dt2=x3-i;
if(H[mir]==dt&&H[x3]==dt2)ans++;
mir=a[mir+1][j];
}
}
///check x M x
for(int j=0;j<ntype;j++){
ll mir=i+typ*j-H[i],mar=i+typ*(j+1)-H[i];
mar=min(mar,r);
mir=min(mir,mar);
mir=max(mir,l);
mir=a[mir][j];
while(mir<mar){
ll x3=mir+H[i],dt=i-mir,dt2=x3-i;
if(dt!=dt2)
if(H[x3]==dt&&H[mir]==dt2)ans++;
mir=a[mir+1][j];
}
}
}
return ans;
}
ll count_triples(vector<int> h) {
n=h.size();
H=h;
return full();
}
vector<int> construct_range(int M, int K) {
return {1,1,1};
}
