#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(){
return 0;
}
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++){
ans+=check(j,i,j+H[i]);
}
}
return ans;
}
ll count_triples(vector<int> h) {
n=h.size();
H=h;
if(n<2001)return sub3();
else return 0;
}
std::vector<int> construct_range(int M, int K) {
return {1, 1, 1};
}
