#include "triples.h"
#include <algorithm>
#include <set>
long long count_triples(std::vector<int> H) {
int N = (int) H.size();
if (N <= 100) {
long long ans = 0;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
for (int k = j + 1; k < N; k++) {
if (H[i] == j - i && H[j] == k - j && H[k] == k - i) ++ans;
else if (H[i] == j - i && H[k] == k - j && H[j] == k - i) ++ans;
else if (H[j] == j - i && H[i] == k - j && H[k] == k - i) ++ans;
else if (H[j] == j - i && H[k] == k - j && H[i] == k - i) ++ans;
else if (H[k] == j - i && H[i] == k - j && H[j] == k - i) ++ans;
else if (H[k] == j - i && H[j] == k - j && H[i] == k - i) ++ans;
}
}
}
return ans;
}
int mx = 0;
for (int i = 0; i < N; i++) mx = std::max(mx, H[i]);
if (mx <= 10) {
long long ans = 0;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < std::min(N, i + mx); j++) {
for (int k = j + 1; k < std::min(N, j + mx); k++) {
if (H[i] == j - i && H[j] == k - j && H[k] == k - i) ++ans;
else if (H[i] == j - i && H[k] == k - j && H[j] == k - i) ++ans;
else if (H[j] == j - i && H[i] == k - j && H[k] == k - i) ++ans;
else if (H[j] == j - i && H[k] == k - j && H[i] == k - i) ++ans;
else if (H[k] == j - i && H[i] == k - j && H[j] == k - i) ++ans;
else if (H[k] == j - i && H[j] == k - j && H[i] == k - i) ++ans;
}
}
}
return ans;
}
if (N <= 2000) {
long long ans = 0;
std::set<int> s;
for (int k = 0; k < N; k++) {
for (int i = 0; i < k; i++) {
s.clear();
int j;
// i < j < k
// H[i] = j - i
j = i + H[i];
if (i < j && j < k) {
if (H[i] == j - i && H[j] == k - j && H[k] == k - i) ++ans, s.insert(j);
else if (H[i] == j - i && H[k] == k - j && H[j] == k - i) ++ans, s.insert(j);
}
// H[i] = k - j
j = k - H[i];
if (i < j && j < k && s.find(j) == s.end()) {
if (H[j] == j - i && H[i] == k - j && H[k] == k - i) ++ans, s.insert(j);
else if (H[k] == j - i && H[i] == k - j && H[j] == k - i) ++ans, s.insert(j);
}
// H[i] = k - i
if (i + H[i] == k) {
// H[k] = k - j
j = k - H[k];
if ((i < j && j < k) && (H[j] == j - i) && (s.find(j) == s.end())) ++ans, s.insert(j);
// H[k] = j - i
j = i + H[k];
if ((i < j && j < k) && (H[j] == k - j) && (s.find(j) == s.end())) ++ans, s.insert(j);
}
}
}
return ans;
}
return 0LL;
}
std::vector<int> construct_range(int M, int K) {
return {1, 1, 1};
}
