#include<bits/stdc++.h>
using namespace std;
vector<int>construct_range(int M,int K){
vector<int>a(M);
for(int i=0;i<M;i++){
if(i%4==0||i%4==2)a[i]=1;
else if(i%4==1)a[i]=2;
else a[i]=3;
}return a;
}
bool check(int i1,int i2,int i3,vector<int>&H,set<tuple<int,int,int>>&s){
vector<int>H_i = {H[i1],H[i2],H[i3]};
sort(H_i.begin(),H_i.end());
vector<int>H_i_2 ={abs(i2-i1),abs(i3-i1),abs(i3-i2)};
sort(H_i_2.begin(),H_i_2.end());
if(H_i[0]==H_i_2[0]&&H_i[1]==H_i_2[1]&&H_i[2]==H_i_2[2]){
vector<int>ind = {i1,i2,i3};
sort(ind.begin(),ind.end());
if(s.find({ind[0],ind[1],ind[2]})!=s.end())return false;
s.insert({ind[0],ind[1],ind[2]});
//cout << i1 << " " << i2 << " " << i3 << endl;
return true;
}else return false;
}
void try_find(int i,int pos2,int &n,int &cant,vector<int>&H,set<tuple<int,int,int>>&s){
if(pos2-H[pos2]>=0&&check(i,pos2,pos2-H[pos2],H,s)){
cant++;
}if(pos2+H[pos2]<n&&check(i,pos2,pos2+H[pos2],H,s)){
cant++;
}if(i-H[pos2]>=0&&check(i,pos2,i-H[pos2],H,s)){
cant++;
}if(i+H[pos2]<n&&i+H[pos2]!=pos2-H[pos2]&&check(i,pos2,i+H[pos2],H,s)){
cant++;
}
return;
}
long long count_triples(vector<int>H){
// strat:
/*
- sweepline til one such that H[j]-act_dis = my_i --> non_direct
- sweepline til one such that H[j]-act_dis = 0 --> direct
- direct connection of H[i]
*/
int n = H.size();
map<int,vector<int>>swip_r;
for(int i=0;i<n;i++){
if(swip_r[H[i]-i].empty())swip_r[H[i]-i].push_back(1);
swip_r[H[i]-i].push_back(i);
}set<tuple<int,int,int>>s;
int cant = 0;
for(int i=0;i<n;i++){
int cant_eq = 0;
if(!swip_r[H[i]-i].empty()){
for(int j=swip_r[H[i]-i][0];j<swip_r[H[i]-i].size();j++){
int it = swip_r[H[i]-i][j];
if(it<=i){
swip_r[H[i]-i][0]++;
continue;
}
if(check(i,it,i+H[it],H,s))cant_eq++;
}
}
//int extra = 0;
if(i+H[i]<n)try_find(i,i+H[i],n,cant,H,s);
if(i-H[i]>=0)try_find(i-H[i],i,n,cant,H,s);
// cout << i << " ::" << extra << " " << cant_eq << endl;
cant+=cant_eq;
}//cout << cant << "--" << s.size() << endl;
return cant;
}
/*
si hay alguno q cuadra --> cuatro para un lado y simetrico y hecho, simulas
si ninguno cuadra-->
4--6----2
*//*
signed main(){
cout << count_triples({4,1,4,3,2,6,1}) << '\n';
vector<int>ans = construct_range(18,30);
for(auto it : ans)cout << it << " ";
cout << '\n';
cout << count_triples(construct_range(18,30)) << '\n';
}*/
