#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;
}
bool ok = true;
for (int i = 1; i < N; i++) if (H[i] < H[i - 1]) ok = false;
if (ok) {
long long ans = 0;
std::set<int> s;
for (int k = 0; k < N; k++) {
int i = k - H[k];
if (i < 0) continue;
s.clear();
// H[i] = k - j || H[i] = j - i
int j;
// H[i] = k - j
j = k - H[i];
if (i < j && j < k && H[j] == j - i && s.find(j) == s.end()) ++ans, s.insert(j);
// H[i] = j - i
j = i + H[i];
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) {
std::vector<int> H(M);
for (int i = 0; i < M; i++) {
H[i] = 1;
if (i % 4 == 2) H[i] = 3;
if (i % 4 == 3) H[i] = 2;
}
return H;
}
