#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;
set<array<int, 3>> st;
long long count_triples(std::vector<int> H) {
int n = sz(H);
ll ret = 0;
auto check = [&](int i, int j, int k) -> void {
if (!(0 <= i && i < j && j < k && k < n)) return;
vector<int> a = {k - i, k - j, j - i};
vector<int> b = {H[i], H[j], H[k]};
sort(all(a));
sort(all(b));
if (a == b) {
st.insert({i, j, k});
}
};
int C = sqrt(n);
// k = hi + i
for (int i = 0; i < n; ++i) {
int k = H[i] + i;
check(i, i + H[k], k);
check(i, k - H[k], k);
}
if (sz(st) > C * n) return -1;
// i = k - hk
for (int k = 0; k < n; ++k) {
int i = k - H[k];
check(i, H[i] + i, k);
check(i, k - H[i], k);
}
if (sz(st) > C * n) return -1;
// j = hi + i
for (int i = 0; i < n; ++i) {
int j = H[i] + i;
if (j < n) {
check(i, j, i + H[j]);
}
}
if (sz(st) > C * n) return -1;
ret = sz(st);
vector<vector<int>> d(2 * n + 5);
for (int i = 0; i < n; ++i) {
if (n + i - H[i] >= sz(d)) {
return -1;
}
d[n + i - H[i]].push_back(i);
}
// for (auto& v : st) {
// for (int j : v) {
// cerr << j + 1 << " ";
// }
// cerr << endl;
// }
// for (int i = 0; i < 2 * n; ++i) {
// cerr << i << "=";
// for (int j : d[i]) {
// cerr << j << " ";
// }
// cerr << endl;
// }
for (int _ = 0; _ < 2 * n; ++_) {
auto& v = d[_];
if (sz(v) < C) {
for (int it = 0; it < sz(v); ++it) {
for (int it1 = it + 1; it1 < sz(v); ++it1) {
int i = v[it];
int j = v[it1];
if (i > j) swap(i, j);
int k = (i + j + H[i] + H[j]);
// if (k % 2 != 0) continue;
assert(k % 2 == 0);
k /= 2;
if (k < n && k > j && k - i == H[j]) {
if (j - i == H[k] && k - j == H[i]) {
ret += !st.count({i, j, k});
// ret += 1;
}
}
}
}
} else {
for (int k = 0; k < n; ++k) {
int i = (_ + k - H[k] - n);
if (i < 0 || (i % 2 != 0)) continue;
// cerr << _ << " " << k << " " << H[k] << endl;
// assert(i % 2 == 0);
i /= 2;
int j = _ + k - i - n;
if (i < j && j < k) {
assert(k < n);
if (k - i == H[j] && j - i == H[k] && k - j == H[i]) {
// cerr << i+1 << " " << j+1 << " " << k+1 << endl;
ret += !st.count({i, j, k});
// ret += 1;
}
}
}
}
}
return ret;
}
std::vector<int> construct_range(int M, int K) {
return {};
}
