#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define endl "\n"
#define dbg(x) cout << #x << " = " << (x) << endl;
const long long INF = 1e18;
const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;
bool match(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;
}
long long count_triples(vector<int> h) {
int n = h.size();
long long ans = 0;
// Preprocess: Map from height to list of indices
unordered_map<int, vector<int>> idx_map;
for (int i = 0; i < n; ++i)
idx_map[h[i]].push_back(i);
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
int di = j - i;
if(di != h[i] && di != h[j]){ // di must be h[k], k > j
if (idx_map.count(di)) {
const vector<int>& idxs = idx_map[di];
auto it = upper_bound(idxs.begin(), idxs.end(), j);
for (; it != idxs.end(); ++it) {
int k = *it;
vector<int> htriple = {h[i], h[j], h[k]};
vector<int> dtriple = {j - i, k - i, k - j};
if (match(htriple, dtriple)) ans++;
}
}
}
else if(di == h[i]){
int k1 = j + h[j];
if(k1 < n && match({h[i], h[j], h[k1]}, {di, k1 - i, k1 - j})) ans++;
int k2 = i + h[j];
if(k2 < n && k2 > j && match({h[i], h[j], h[k2]}, {di, k2 - i, k2 - j})) ans++;
}
else if(di == h[j]){
int k1 = i + h[i];
if(k1 < n && k1 > j && match({h[i], h[j], h[k1]}, {di, k1 - i, k1 - j})) ans++;
int k2 = j + h[i];
if(k2 < n && match({h[i], h[j], h[k2]}, {di, k2 - i, k2 - j})) ans++;
}
}
}
return ans;
}
vector<int> construct_range(int m, int k){
return {};
}
/*int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("input.in", "r", stdin);
//freopen("input.out", "w", stdout);
cout<<count_triples({4, 1, 4, 3, 2, 6, 1});
return 0;
}*/
