#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
long long count_triples(std::vector<int> a) {
const int n = (int)a.size();
unordered_set<ll> seen;
auto check = [&](int i, int j) -> void {
if (j < 0 || j >= n) return;
vi cand = {i+a[i], i-a[i], i+a[j], i-a[j], j+a[i], j-a[i], j+a[j], j-a[j]};
for (int k : cand) if (k != i && k != j && k < n && k >= 0) {
array<int, 3> id{i, j, k}, v{a[i], a[j], a[k]}, d{abs(i-j), abs(i-k), abs(j-k)};
sort(id.begin(), id.end());
sort(v.begin(), v.end());
sort(d.begin(), d.end());
if (d == v) seen.insert(id[0]*(ll)1e12+id[1]*(ll)1e6+(ll)id[0]);
}
};
for (int i = 0; i < n; i++) check(i, i-a[i]), check(i, i+a[i]);
ll ans = seen.size();
vvi pk(3*n), nk(3*n);
for (int i = 0; i < n; i++) {
pk[i-a[i]+n].push_back(i);
nk[i+a[i]+n].push_back(i);
}
for (int i = 0; i < 3*n; i++) reverse(nk[i].begin(), nk[i].end());
for (int j = 0; j < n; j++) {
int szpk = (int)pk[j-a[j]+n].size();
int sznk = (int)nk[j+a[j]+n].size();
if (szpk < sznk) {
vi &sm = pk[j-a[j]+n];
for (int i : sm) {
if (i == j) break;
int l = j-i;
int k = j+a[i];
int r = k-j;
if (k < 0 || k >= n) continue;
if (r == a[i] && l == a[k]) ans++;
}
}
else {
vi &sm = nk[j+a[j]+n];
for (int k : sm) {
if (k == j) break;
int r = k-j;
int i = j-a[k];
int l = j-i;
if (i < 0 || i >= n) continue;
if (r == a[i] && l == a[k]) ans++;
}
}
}
return ans;
}
std::vector<int> construct_range(int M, int K) {
return {1, 1, 1};
}
