#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int N;
bool checkTriple(int a, int b, int c, vector<signed>& H) {
if (a >= N) return false;
if (b >= N) return false;
if (c >= N) return false;
if (a < 0) return false;
if (b < 0) return false;
if (c < 0) return false;
if (a == b) return false;
if (a == c) return false;
if (b == c) return false;
vector<int> d {abs(b-a), abs(c-a), abs(c-b)};
vector<int> h = {H[a], H[b], H[c]};
sort(d.begin(), d.end());
sort(h.begin(), h.end());
for (int i = 0; i < 3; ++i) {
if (d[i] != h[i]) return false;
}
return true;
}
long long count_triples(std::vector<signed> H) {
ll ret = 0;
N = H.size();
set<int> nums;
for (int i = 0; i < N; ++i) {
int curr = H[i];
int left = i - curr, right = i + curr;
if (N > 2000) {
nums.clear();
int j = i - H[i];
if (j >= 0) {
if (H[j] < H[i]) {
if (checkTriple(i, j+H[j], j, H)) {
++ret;
cout<<i<<' '<<j+H[j]<<' '<<j<<'\n';
}
if (checkTriple(i, i-H[j], j, H)) {
++ret;
cout<<i<<' '<<i-H[j]<<' '<<j<<'\n';
}
} else {
if (checkTriple(i, i-H[j], j, H)) {
++ret;
cout<<i<<' '<<i-H[j]<<' '<<j<<'\n';
}
}
}
j = i + H[i];
if (j < H.size()) {
if (H[j] < H[i]) {
if (checkTriple(i, j-H[j], j, H)) {
++ret;
cout<<i<<' '<<j-H[j]<<' '<<j<<'\n';
}
if (checkTriple(i, i+H[j], j, H)) {
++ret;
cout<<i<<' '<<i+H[j]<<' '<<j<<'\n';
}
} else {
if (checkTriple(i, i+H[j], j, H)) {
++ret;
cout<<i<<' '<<i+H[j]<<' '<<j<<'\n';
}
}
}
} else {
for (int j = i; j < N; ++j) {
nums.clear();
nums.insert(i + H[i]);
nums.insert(i + H[j]);
nums.insert(j + H[i]);
nums.insert(j + H[j]);
for (auto k = nums.begin(); k != nums.end(); ++k) {
if (*k < j) continue;
if (checkTriple(i, *k, j, H)) {
++ret;
// cout<<i<<' '<<*k<<' '<<j<<'\n';
}
}
}
}
}
return ret;
}
std::vector<int> construct_range(int M, int K) {
vector<int> ret;
int med = M/2;
for (int i = 0; i < M; ++i) {
if (i >= med) {
ret.push_back(max(1, i - med));
} else {
ret.push_back(max(1, i));
}
}
return ret;
}
