#include <bits/stdc++.h>
using namespace std;
long long count_triples(vector<int> H) {
const int N = (int)H.size();
long long ans = 0;
// -------- Case 1: Max at the LEFT end (i). H[i] = k - i.
// For fixed i, k is forced: k = i + H[i].
// Then j is forced by H[k] in at most two ways:
// (A) H[k] = k - j -> j = k - H[k], require H[j] = j - i
// (B) H[k] = j - i -> j = i + H[k], require H[j] = k - j
for (int i = 0; i < N; ++i) {
int k = i + H[i];
if (k >= 0 && k < N) {
int cnt = 0;
int j1 = k - H[k];
if (i < j1 && j1 < k && H[j1] == j1 - i) ++cnt;
int j2 = i + H[k];
if (j2 != j1 && i < j2 && j2 < k && H[j2] == k - j2) ++cnt;
ans += cnt;
}
}
// -------- Case 2: Max at the RIGHT end (k). H[k] = k - i.
// Symmetric to case 1.
for (int k = 0; k < N; ++k) {
int i = k - H[k];
if (i >= 0 && i < k) {
int cnt = 0;
int j1 = i + H[i];
if (i < j1 && j1 < k && H[j1] == k - j1) ++cnt;
int j2 = k - H[i];
if (j2 != j1 && i < j2 && j2 < k && H[j2] == j2 - i) ++cnt;
ans += cnt;
}
}
// -------- Case 3: Max at the MIDDLE (j). H[j] = (j - i) + (k - j).
//
// Let D = H[j]. For any split s in {1..D-1}:
// left gap = s
// right gap = D - s
// i = j - s, k = j + (D - s)
// We need {H[i], H[k]} = {s, D - s}.
//
// Iterating all s is too slow, so we use the standard small/large trick:
// only iterate s up to B ~ sqrt(N). This checks any triple where the
// smaller of the two gaps is <= B. For the remaining (both gaps > B),
// they are handled implicitly via the “max at ends” cases above (fast),
// plus a small extra loop below that covers the swapped orientation when
// one of the endpoint heights is small.
int B = max(1, (int) sqrt((double)N) + 1);
auto check_pair = [&](int j, int s) -> int {
int D = H[j];
if (s <= 0 || s >= D) return 0;
int i = j - s;
int k = j + (D - s);
if (i < 0 || k >= N) return 0;
int a = s, b = D - s;
// {H[i], H[k]} must be {a, b}
if ((H[i] == a && H[k] == b) || (H[i] == b && H[k] == a)) return 1;
return 0;
};
for (int j = 0; j < N; ++j) {
int D = H[j];
if (D <= 1) continue;
int up = min(B, D - 1);
// iterate only the smaller gap s (so s <= D - s) to avoid double counting
up = min(up, D / 2);
for (int s = 1; s <= up; ++s) {
ans += check_pair(j, s);
}
// Also cover the case where the RIGHT gap is the smaller (<= B) but
// right gap < left gap; that is equivalent to iterating s' = (D - s)
// where s' <= B and s' < D - s'. To avoid overlap, we handle the
// “right-small” side with strict inequality.
int right_up = min(B, D - 1);
for (int r = 1; r <= right_up; ++r) {
if (r < D - r) { // strict to avoid double counting when gaps equal
// right gap = r -> s = D - r
ans += check_pair(j, D - r);
}
}
}
// -------- Extra safety: swapped-orientation when one endpoint height is small.
//
// Swapped middle-max means H[i] = (k - j) and H[k] = (j - i), i.e., endpoints' heights
// equal the *opposite* gaps. Such triples are often already covered by the loops above,
// but to be robust we add an O(B*N) sweep:
//
// For each small a = H[i] (1..B) and each k:
// i = k - (a + H[k])
// j = k - a
// Check bounds and H[j] == a + H[k].
//
// This is linear in N for each small a, so O(B*N).
for (int a = 1; a <= B; ++a) {
for (int k = 0; k < N; ++k) {
int i = k - (a + H[k]);
if (i < 0 || i >= k) continue;
int j = k - a;
if (j <= i || j >= k) continue;
if (H[i] != a) continue;
if (H[j] == a + H[k]) {
++ans;
}
}
}
// The symmetric small-end on the right (small H[k]) — also O(B*N).
for (int b = 1; b <= B; ++b) {
for (int i = 0; i < N; ++i) {
int k = i + H[i] + b;
if (k <= i || k >= N) continue;
int j = i + H[i];
if (j <= i || j >= k) continue;
if (H[k] != b) continue;
if (H[j] == H[i] + b) {
++ans;
}
}
}
// Finally, middle-max *perfectly symmetric* (equal gaps) were touched multiple times.
// Count each symmetric middle-max once and subtract duplicates.
// Symmetric means: H[j] even, a = H[j]/2, i = j - a, k = j + a, and H[i] = H[k] = a.
long long symmetric_mid = 0;
for (int j = 0; j < N; ++j) {
int D = H[j];
if ((D & 1) == 0) {
int a = D / 2;
int i = j - a, k = j + a;
if (i >= 0 && k < N && H[i] == a && H[k] == a) {
++symmetric_mid;
}
}
}
// We added symmetric triples more than once in our “middle” loops; keep exactly one copy.
// The two small-gap passes can both hit the same symmetric triple, so subtract one of them.
ans -= symmetric_mid;
return ans;
}
