#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int N;
bool checkTriple(int a, int b, int c, vector<signed>& H) {
if (a >= N) return false;
if (b >= N) return false;
if (c >= N) return false;
if (a < 0) return false;
if (b < 0) return false;
if (c < 0) return false;
if (a == b) return false;
if (a == c) return false;
if (b == c) return false;
vector<int> d {abs(b-a), abs(c-a), abs(c-b)};
vector<int> h = {H[a], H[b], H[c]};
sort(d.begin(), d.end());
sort(h.begin(), h.end());
for (int i = 0; i < 3; ++i) {
if (d[i] != h[i]) return false;
}
return true;
}
long long count_triples(std::vector<signed> H) {
ll ret = 0;
N = H.size();
set<int> nums;
for (int i = 0; i < N; ++i) {
int curr = H[i];
int left = i - curr, right = i + curr;
if (N > 2000) {
nums.clear();
int j = i - H[i];
if (j < 0) continue;
nums.insert(j + H[j]);
nums.insert(i - H[j]);
for (auto k = nums.begin(); k != nums.end(); ++k) {
if (*k < j) continue;
if (checkTriple(i, *k, j, H)) {
++ret;
// cout<<i<<' '<<*k<<' '<<j<<'\n';
}
};
} else {
for (int j = i; j < N; ++j) {
nums.clear();
nums.insert(i + H[i]);
nums.insert(i + H[j]);
nums.insert(j + H[i]);
nums.insert(j + H[j]);
for (auto k = nums.begin(); k != nums.end(); ++k) {
if (*k < j) continue;
if (checkTriple(i, *k, j, H)) {
++ret;
// cout<<i<<' '<<*k<<' '<<j<<'\n';
}
}
}
}
}
return ret;
}
std::vector<int> construct_range(int M, int K) {
return {1, 1, 1};
}
