#include <bits/stdc++.h>
using namespace std;
long long count_triples(vector<int> H) {
int N = (int)H.size();
vector<vector<int>> L(N), R(N);
for (int i = 0; i < N; i++) {
int x = H[i];
if (i + x < N) L[i + x].push_back(x);
if (i - x >= 0) R[i - x].push_back(x);
}
long long ans = 0;
int B = (int)sqrt(N) + 1;
vector<int> markL(N + 1, 0), markR(N + 1, 0);
int timer = 0;
for (int p = 0; p < N; p++) {
auto &A = L[p];
auto &Bv = R[p];
if (A.empty() || Bv.empty()) continue;
++timer;
if ((int)A.size() < (int)Bv.size()) {
for (int y : Bv) markR[y] = timer;
for (int x : A) {
int need = H[p] - x;
if (need > 0 && need <= N && markR[need] == timer) ans++;
}
} else {
for (int x : A) markL[x] = timer;
for (int y : Bv) {
int need = H[p] - y;
if (need > 0 && need <= N && markL[need] == timer) ans++;
}
}
long long prod = 1LL * A.size() * Bv.size();
if (prod <= 1LL * B * B) {
for (int x : A) {
for (int y : Bv) {
if (x == y) continue;
int q = p + y - x;
if (0 <= q && q < N && H[q] == x + y) ans++;
}
}
} else {
++timer;
for (int x : A) markL[x] = timer;
for (int y : Bv) markR[y] = timer;
for (int q = 0; q < N; q++) {
if (q == p) continue;
int s = H[q];
int d = q - p;
int numX = s - d;
int numY = s + d;
if (numX & 1) continue;
if (numY & 1) continue;
int x = numX / 2;
int y = numY / 2;
if (x <= 0 || y <= 0) continue;
if (x > N || y > N) continue;
if (markL[x] == timer && markR[y] == timer) ans++;
}
}
}
for (int i = 0; i < N; i++) {
int s = H[i];
int k = i + s;
if (k >= N) continue;
int t = H[k];
if (0 < t && t < s) {
int j1 = i + t;
if (j1 > i && j1 < k && H[j1] == s - t) ans++;
int j2 = i + (s - t);
if (t != s - t && j2 > i && j2 < k && H[j2] == s - t) ans++;
}
}
for (int k = 0; k < N; k++) {
int s = H[k];
int i = k - s;
if (i < 0) continue;
int t = H[i];
if (0 < t && t < s) {
int j1 = i + t;
if (j1 > i && j1 < k && H[j1] == s - t) ans++;
int j2 = i + (s - t);
if (t != s - t && j2 > i && j2 < k && H[j2] == s - t) ans++;
}
}
return ans;
}
vector<int> construct_range(int M, int K) {
vector<int> H = {3,1,2,1,4,3,2,3,1,2,1,4,3,2,3,1,2,1,4,3};
if ((int)H.size() > M) H.resize(M);
if (H.empty()) H.push_back(1);
int N = (int)H.size();
for (int i = 0; i < N; i++) {
H[i] = max(1, min(H[i], N - 1));
}
return H;
}
