#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {
return l + rd() % (r - l + 1);
}
long long count_triples(vector<int> a) {
int n = a.size();
unordered_set<ll> s;
auto add = [&](int i, int j) {
if (i < 0 || i >= n || j < 0 || j >= n) return;
vi c = {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 : c) if (k != i && k != j && k >= 0 && k < n) {
array<int,3> p{i,j,k}, v{a[i],a[j],a[k]}, d{abs(i-j),abs(i-k),abs(j-k)};
sort(p.begin(), p.end());
sort(v.begin(), v.end());
sort(d.begin(), d.end());
if (d == v) s.insert(p[0]*1000000000000LL + p[1]*1000000LL + p[2]);
}
};
for (int i = 0; i < n; i++) add(i, i-a[i]), add(i, i+a[i]);
ll ans = s.size();
vvi L(3*n), R(3*n);
for (int i = 0; i < n; i++) {
if (i-a[i]+n >= 0) L[i-a[i]+n].push_back(i);
if (i+a[i]+n < 3*n) R[i+a[i]+n].push_back(i);
}
for (int i = 0; i < 3*n; i++) reverse(R[i].begin(), R[i].end());
for (int j = 0; j < n; j++) if (a[j] <= n) {
int szL = L[j-a[j]+n].size(), szR = R[j+a[j]+n].size();
if (szL < szR) {
for (int i : L[j-a[j]+n]) {
if (i == j) break;
int k = j + a[i];
if (k < 0 || k >= n) continue;
if (k - j == a[i] && j - i == a[k] && a[i] != a[k]) ans++;
}
} else {
for (int k : R[j+a[j]+n]) {
if (k == j) break;
int i = j - a[k];
if (i < 0 || i >= n) continue;
if (k - j == a[i] && j - i == a[k] && a[i] != a[k]) ans++;
}
}
}
return ans;
}
vector<int> construct_range(int n, int k) {
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
auto rnd = [&]() {
return uniform_int_distribution<int>(1, 2)(rng);
};
vector<int> h(n, 1);
int len = min(n, 2);
for (int i = 0; i < len; i++) h[i] = rnd();
while (len < n) {
int half = len / 2;
int nxt = min(n, len + half);
for (int i = 0; i < half; i++) {
int j = i + half;
if (j >= len) break;
int d = j - i;
h[i] = h[j] = d;
int p = i + j;
if (p < nxt) {
if (2LL * d < (long long)1e9) h[p] = 2 * d;
else h[p] = rnd();
}
}
for (int i = len; i < nxt; i++) h[i] = rnd();
len = nxt;
}
return h;
}
