#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;
void ssort(vector<int>& a) {
if (a[0] > a[2]) swap(a[0], a[2]);
if (a[0] > a[1]) swap(a[0], a[1]);
if (a[1] > a[2]) swap(a[1], a[2]);
}
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};
if (a[0] < a[1]) swap(a[0], a[1]);
vector<int> b = {H[i], H[j], H[k]};
ssort(a);
ssort(b);
ret += a == b;
};
int C = 450;
// k = hi + i
for (int i = 0; i < n; ++i) {
int k = H[i] + i;
if (k >= n) continue;
check(i, i + H[k], k);
if (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 (i < 0) continue;
check(i, H[i] + i, k);
if (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]);
k /= 2;
if (k > n) continue;
if (H[i] == H[k]) continue;
if (k < n && k > j && k - i == H[j] && 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) {
if (H[i] == H[k]) continue;
if (k - i == H[j] && j - i == H[k] && k - j == H[i]) {
ret += 1;
}
}
}
}
}
return ret;
}
std::vector<int> construct_range(int M, int K) {
return {};
}
