#include "triples.h"
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
long long count_triples(std::vector<int> H) {
int n = sz(H);
vector<int> cnt(n);
vector<vector<int>> occ(n);
for (int i = 0; i < n; ++i) {
cnt[H[i]] += 1;
occ[H[i]].push_back(i);
}
ll ret = 0;
// k = hi + i - 1
for (int i = 0; i < n; ++i) {
int k = H[i] + i;
if (k >= n) continue;
int hj = H[i] - H[k];
if (hj < 0) continue;
auto& v = occ[hj];
ret += lower_bound(all(v), k) - begin(v);
ret -= upper_bound(all(v), i) - begin(v);
// cerr << hj << " = " << i << " " << k << " = " << ((upper_bound(all(v), k) - begin(v)) - (lower_bound(all(v), i) - begin(v))) << endl;
}
// i = k - hk - 1
for (int k = 0; k < n; ++k) {
int i = k - H[k];
if (i < 0) continue;
int hj = H[k] - H[i];
if (hj < 0) continue;
auto& v = occ[hj];
ret += lower_bound(all(v), k) - begin(v);
ret -= upper_bound(all(v), i) - begin(v);
// cerr << hj << " = " << i << " " << k << " = " << ((upper_bound(all(v), k) - begin(v)) - (lower_bound(all(v), i) - begin(v))) << endl;
}
// k - hk = hi + i
for (int k = 0; k < n; ++k) {
for (int i = 0; i < k; ++i) {
if (k - H[k] != H[i] + i) continue;
int hj = H[k] + H[i];
auto& v = occ[hj];
ret += lower_bound(all(v), k) - begin(v);
ret -= upper_bound(all(v), i) - begin(v);
// cerr << i << " " << k << " = " << ((upper_bound(all(v), k) - begin(v)) - (lower_bound(all(v), i) - begin(v))) << endl;
}
}
return ret;
}
std::vector<int> construct_range(int M, int K) {
return {};
}
