#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;
// 1) số lớn nhất ở giữa
for (int p = 0; p < N; p++) {
auto &A = L[p];
auto &Bv = R[p];
if (A.empty() || Bv.empty()) continue;
// middle = p
++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++;
}
}
// middle = q = p + y - x
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++;
}
}
}
// 2) số lớn nhất ở trái
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++;
}
}
// 3) số lớn nhất ở phải
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;
}
// Thêm hàm này để grader link không bị lỗi.
// Nếu chỉ làm Part I thì cứ trả mảng rỗng hoặc mảng đơn giản.
vector<int> construct_range(int M, int K) {
return {1, 1, 1};
}
