#include <bits/stdc++.h>
#include "triples.h"
using namespace std;
void manual(vector<int> &a) {
if (a[0] > a[1]) swap(a[0], a[1]);
if (a[1] > a[2]) swap(a[1], a[2]);
if (a[0] > a[1]) swap(a[0], a[1]);
}
long long count_triples(vector<int> h) {
int n = h.size();
auto f = [&](int i, int j, int k) {
vector<int> x = {abs(i - j), abs(i - k), abs(j - k)};
vector<int> y = {h[i], h[j], h[k]};
manual(x); manual(y);
return x == y;
};
long long res = 0;
for (int i = 0; i < n; i++) {
if (i - h[i] >= 0) {
int j = i - h[i];
int k = j + h[j];
int prv = -1;
if (k < i) {
if (f(i, j, k)) {
res++;
prv = k;
}
}
k = i - h[j];
if (k != prv && k > j) {
res += f(i, j, k);
}
}
if (i + h[i] < n) {
int j = i + h[i];
int k = j - h[j];
int prv = -1;
if (k > i) {
if (f(i, j, k)) {
res++;
prv = k;
}
}
k = i + h[j];
if (k != prv && k < j) {
res += f(i, j, k);
}
}
for (int j = max(0, i - h[i] + 1); j + h[i] <= min(n - 1, i + h[i] - 1); j++) {
int k = j + h[i];
if (j != i && k != i && h[j] + h[k] == h[i]) {
res += f(i, j, k);
}
}
}
return res;
}
vector<int> res = {1, 3, 2, 3, 4, 1, 2, 1, 3, 1, 2, 1, 4, 3, 2, 3, 1, 1, 2, 1};
vector<int> construct_range(int M, int K) {
vector<int> ret;
while (ret.size() < M) {
for (auto x : res) {
ret.push_back(x);
}
}
return ret;
}
