#include "triples.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<int> h;
bool same(vector<int> a,vector<int> b){
sort(a.begin(), a.end());
sort(b.begin(), b.end());
for (int i=0; i<3; i++)
if (a[i] != b[i]) return false;
return true;
}
bool check(int i,int j,int k){
bool flag = 0 <= i && i < j && j < k && k < n && same({k-i, k-j, j-i}, {h[i], h[j], h[k]});
// if (flag) cout << i << " " << j << " " << k << " <-\n";
// return 0 <= i && i < j && j < k && k < n && same({k-i, k-j, j-i}, {h[i], h[j], h[k]});
return flag;
}
const int N = 2e5+4;;
vector<int> vals[2*N];
ll count_triples(vector<int> H){
h = H;
n = h.size();
ll ans = 0;
for (int i=0; i<n; i++){
int l = i - h[i];
int r = i + h[i];
if (l >= 0){
ans += check(l, l+h[l], i);
if (l+h[l] != i-h[l])
ans += check(l, i-h[l], i);
if (h[l] != 2*h[i])
ans += check(i-h[l], l, i);
}
if (r < n){
ans += check(i, r-h[r], r);
if (r-h[r] != i+h[r])
ans += check(i, i+h[r], r);
}
vals[i + h[i]].push_back(i);
}
for (int val=1; val<2*n; val++){
int sz = vals[val].size();
if (sz == 0) continue;
if (1ll*sz*sz <= n){ // *O(k*k)
// cout << "caso 1 : val = " << val << " sz = " << sz << "\n";
for (int j=0; j<sz; j++)
for (int k=j+1; k<sz; k++){
int i = vals[val][j] + vals[val][k] - val;
ans += check(i, vals[val][j], vals[val][k]);
}
}
else{ // *O(n)
// cout << "caso 1 : val = " << val << " sz = " << sz << "\n";
for (int i=0; i<n; i++){
int j = i - h[i] + val;
int k = i + h[i] + val;
if (j%2 == 1 || k%2 == 1) continue;
j /= 2, k /= 2;
if (j < 0 || j >= n || k < 0 || k >= n) continue;
if (j + h[j] != val || k + h[k] != val) continue;
ans += check(i, j, k);
}
}
}
return ans;
}
vector<int> construct_range(int M, int K){
vector<int> vec;
int patron[] = {1, 1, 2}, p=0;
while (vec.size() < M){
vec.push_back(patron[p]);
p = (p+1)%3;
}
return vec;
}
