#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O5")
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
inline void bubble(vector<int> &a) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2-i; j++) {
if (a[j] > a[j+1]) swap(a[j], a[j+1]);
}
}
}
vector<tuple<int, int, int>> stuff;
inline void add(int i, int j, int k, map<tuple<int, int, int>, bool> &mp, vector<int> &H, bool ok = true) {
if (i == j or j == k or i == k) return;
vector<int> a = {i, j, k};
sort(a.begin(), a.end());
// bubble(a);
if (!ok) {
vector<int> b = {a[2]-a[0], a[2]-a[1], a[1]-a[0]};
sort(b.begin(), b.end());
// bubble(b);
vector<int> c = {H[i], H[j], H[k]};
sort(c.begin(), c.end());
// bubble(c);
if (b != c) return;
}
// mp[{a[0], a[1], a[2]}] = true;
stuff.emplace_back(a[0], a[1], a[2]);
return;
}
long long count_triples(vector<int> H) {
const int SHIFT = 2e5+21;
int n = H.size();
map<tuple<int, int, int>, bool> mp;
vector<vector<int>> diff(SHIFT * 2);
for (int i = 0; i < n; i++) {
diff[H[i]-i+SHIFT].push_back(i);
int j = H[i]+i;
if (j >= n) continue;
int d = j-i;
int t = (d == H[i] ? H[j] : H[i]);
int w, x, y, z;
w = i-t, x = i+t;
y = j-t, z = j+t;
if (w >= 0 and H[w] == abs(j-w)) add(i, j, w, mp, H);
if (x < n and H[x] == abs(j-x)) add(i, j, x, mp, H);
if (y >= 0 and H[y] == abs(i-y)) add(i, j, y, mp, H);
if (z < n and H[z] == abs(i-z)) add(i, j, z, mp, H);
}
int CB = cbrt(n);
int SQ = 700;
for (int k = 0; k < 2 * SHIFT; k++) {
auto &v = diff[k];
if (v.size() <= 1) continue;
int di = k - SHIFT;
if (v.size() <= SQ) {
for (auto &i : v) {
for (auto &j : v) {
if (j <= i) continue;
int d = j-i;
int t = min(H[i], H[j]);
int x, y;
x = i-t, y = j+t;
if (x >= 0 and H[x] == d) add(i, j, x, mp, H);
if (y < n and H[y] == d) add(i, j, y, mp, H);
}
}
} else {
for (int i = 0; i < n; i++) {
int j = (i-H[i]-di)/2;
if (j < 0 or j >= n) continue;
int t = min(H[i], H[j]);
int x, y;
x = i-t, y = j+t;
if (x >= 0) add(i, j, x, mp, H, false);
if (y < n) add(i, j, y, mp, H, false);
}
}
}
sort(stuff.begin(), stuff.end());
stuff.erase(unique(stuff.begin(), stuff.end()), stuff.end());
return stuff.size();
}
vector<int> construct_range(int M, int K) {
vector<int> o(M);
iota(o.begin(), o.end(), 0);
o[0] = 1;
return o;
}
