#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static inline uint64_t pack_triple(int i, int j, int k) {
return (uint64_t(i) << 42) | (uint64_t(j) << 21) | uint64_t(k);
}
long long count_triples(std::vector<int> H) {
int n = (int)H.size();
vector<ll> a(H.begin(), H.end());
vector<array<int,3>> candidates;
candidates.reserve(n * 6);
for (int i = 0; i < n; ++i) {
{
ll j = (ll)i + a[i];
if (0 <= j && j < n) {
ll k = j + a[j];
if (0 <= k && k < n) candidates.push_back({i, int(j), int(k)});
}
}
{
ll j = (ll)i + a[i];
if (0 <= j && j < n) {
ll k = (ll)i + a[j];
if (0 <= k && k < n) candidates.push_back({i, int(j), int(k)});
}
}
{
ll k = (ll)i + a[i];
if (0 <= k && k < n) {
ll j = k - a[k];
if (0 <= j && j < n) candidates.push_back({i, int(j), int(k)});
}
}
}
for (int j = 0; j < n; ++j) {
{
ll i = (ll)j - a[j];
if (0 <= i && i < n) {
ll k = j + a[i];
if (0 <= k && k < n) candidates.push_back({int(i), j, int(k)});
}
}
{
ll k = (ll)j + a[j];
if (0 <= k && k < n) {
// i = j - H[k]
ll i = (ll)j - a[k];
if (0 <= i && i < n) candidates.push_back({int(i), j, int(k)});
}
}
}
for (int k = 0; k < n; ++k) {
// j = k - H[k]; i = k - H[j]
ll j = (ll)k - a[k];
if (0 <= j && j < n) {
ll i = (ll)k - a[j];
if (0 <= i && i < n) candidates.push_back({int(i), int(j), k});
}
}
unordered_set<uint64_t> seen;
seen.reserve(candidates.size() * 2 + 16);
ll ans = 0;
for (auto &t : candidates) {
int i = t[0], j = t[1], k = t[2];
if (!(0 <= i && i < j && j < k && k < n)) continue;
uint64_t key = pack_triple(i,j,k);
if (seen.find(key) != seen.end()) continue;
array<int,3> Hvals = { H[i], H[j], H[k] };
sort(Hvals.begin(), Hvals.end());
int d1 = j - i;
int d2 = k - j;
int d3 = k - i;
array<int,3> Dvals = { d1, d2, d3 };
sort(Dvals.begin(), Dvals.end());
if (Hvals == Dvals) {
seen.insert(key);
++ans;
}
}
return ans;
}
