#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);
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) {
cerr << i+1 << " " << j+1 << " " << k+1 << endl;
ret += 1;
}
};
int C = 500;
// k = hi + i
for (int i = 0; i < n; ++i) {
int k = H[i] + i;
if (k < n) check(i, i + H[k], k);
if (k < n && k - H[k] > i && H[k] != H[k - H[k]]) check(i, k - H[k], k);
}
// i = k - hk
for (int k = 0; k < n; ++k) {
int i = k - H[k];
if (0 <= i) check(i, H[i] + i, k);
if (0 <= i && k - H[i] > i && H[i] != H[k - H[i]]) check(i, k - H[i], k);
}
// j = hi + i
for (int i = 0; i < n; ++i) {
int j = H[i] + i;
if (j < n) {
check(i, j, i + H[j]);
}
}
vector<vector<int>> d(2 * n);
for (int i = 0; i < n; ++i) {
d[n + i - H[i]].push_back(i);
}
// k = i + hj, j = i + hk, k = j + hi
for (int _ = 0; _ < 2 * n; ++_) {
const vector<int>& 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]);
// assert(k % 2 == 0);
k /= 2;
if (k > n) continue;
if (H[i] == H[k]) continue;
if (k < n && k > j && k - i == H[j]) {
if (j - i == H[k] && k - j == H[i]) {
ret += 1;
}
}
}
}
} else {
for (int k = 0; k < n; ++k) {
int i = (_ + k - H[k] - n);
if (i < 0 || (i % 2 != 0)) continue;
i /= 2;
int j = _ + k - i - n;
if (i < j && j < k) {
// assert(k < n);
if (H[i] == H[k]) continue;
if (k - i == H[j] && j - i == H[k] && k - j == H[i]) {
cerr << i+1 << " " << j+1 << " " << k+1 << endl;
ret += 1;
}
}
}
}
}
return ret;
}
std::vector<int> construct_range(int M, int K) {
return {};
}
