#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
const int MAXN = 4e5+5;
vector<int> diag1[MAXN], diag2[MAXN];
int d1[MAXN], d2[MAXN];
ll count_triples(vector<int> H) {
int n = H.size();
set<array<int, 3>> trips;
//count standard pairs
for (int i = 0; i < n; i++) {
for (int j : {i - H[i], i + H[i]}) if (j >= 0 && j < n) {
for (int k : {i + H[i], i - H[i], i + H[j], i - H[j], j + H[i], j - H[i], j + H[j], j - H[j]}) if (k >= 0 && k < n) {
array<int, 3> diffs = {abs(i-j), abs(i-k), abs(k-j)};
array<int, 3> hs = {H[i], H[j], H[k]};
sort(diffs.begin(), diffs.end());
sort(hs.begin(), hs.end());
if (hs == diffs) {
array<int, 3> ind = {i, j, k};
sort(ind.begin(), ind.end());
trips.insert(ind);
}
}
}
}
ll ans = trips.size();
for (int i = 0; i < n; i++) {
ll d = H[i] - i + n;
d1[i] = diag1[d].size();
diag1[d].push_back(i);
}
for (int i = n-1; i >= 0; i--) {
ll d = H[i] + i;
d2[i] = diag2[d].size();
diag2[d].push_back(i);
}
for (int j = 0; j < n; j++) {
if (d1[j] < d2[j]) {
int d = H[j] - j + n;
for (int x = 0; x < d1[j]; x++) {
int i = diag1[d][x];
int k = i + H[j];
if (k < n && (H[k] + k == H[j] + j)) if (H[i] != H[j] && H[j] != H[k] && H[k] != H[i]) ans++;
}
} else {
int d = H[j] + j;
for (int x = 0; x < d2[j]; x++) {
int k = diag2[d][x];
int i = k - H[j];
if (i >= 0 && (H[i] - i == H[j] - j)) if (H[i] != H[j] && H[j] != H[k] && H[k] != H[i]) ans++;
}
}
}
return ans;
}
std::vector<int> construct_range(int M, int K) {
vector<int> ans = {1};
for (int i = 1; i < M; i++) ans.push_back(i);
return ans;
}
