#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)
#define cout if (0) cout
ll fast_checker(v<int> &H) {
int N = H.size();
ll cnt = 0;
rep(i, 0, N) {
rep(j, i+1, N) {
rep(k, j+1, N) {
v<int> dis = {k-i, k-j, j-i};
v<int> h = {H[i], H[j], H[k]};
sort(dis.begin(), dis.end());
sort(h.begin(), h.end());
if (dis == h) cnt++;
}
}
}
return cnt;
}
ll count_triangles(v<v<int>> &edges, map<int, v<int>> &adj) {
ll cnt = 0;
for (auto x : edges) {
int u = x[0];
int v = x[1];
if (adj[u].size() > adj[v].size()) {
swap(u, v);
}
int i, j;
i=j=0;
while (i < (int)adj[u].size() && j<(int)adj[v].size()) {
if (adj[u][i] == adj[v][j]) {
cnt++;
i++; j++;
}
else if (adj[u][i] > adj[v][j]) j++;
else i++;
}
}
return cnt/3;
}
long long count_triples(std::vector<int> H) {
ll ans=0;
int N = H.size();
rep(i, 0, N) {
if (H[i]+i < N) {
int k = H[i]+i;
if (k-H[k] > 0) {
int j = k-H[k];
if (H[i] == k-i && H[k] == k-j && H[j] == j-i && (i != j && j != k && k != i)) {
ans++;
cout << "1" << endl;
cout << i << " " << j << " " << k << endl;
}
}
if (H[k]+i < N) {
int j = H[k]+i;
if (H[i] == k-i && H[k] == j-i && H[j] == k-j && (i != j && j != k && k != i)) {
ans++;
cout << "2" << endl;
cout << i << " " << j << " " << k << endl;
}
}
}
}
rep(k, 0, N) {
if (k-H[k] > 0) {
int i = k-H[k];
if (H[i]+i < N) {
int j = H[i]+i;
if (H[k] == k-i && H[i] == j-i && H[j] == k-j && (i != j && j != k && k != i)) {
ans++;
cout << i << " " << j << " " << k << endl;
}
}
if (k-H[i] > 0) {
int j = k-H[i];
if (H[k] == k-i && H[i] == k-j && H[j] == j-i && (i != j && j != k && k != i)) {
ans++;
cout << i << " " << j << " " << k << endl;
}
}
}
}
rep(i, 0, N) {
if (H[i]+i < N) {
int j = H[i]+i;
if (H[j]+i < N) {
int k = H[j]+i;
if (H[i] == j-i && H[k] == k-j && H[j] == k-i && (i != j && j != k && k != i)) {
ans++;
cout << i << " " << j << " " << k << endl;
}
}
}
}
v<v<int>> edges;
rep(i, 0, N) {
if (i-H[i] > 0 && i+H[i] < N) edges.push_back({i-H[i], i+H[i]});
}
map<int, v<int>> adj;
for (auto x : edges) {
int u = x[0];
int v = x[1];
adj[u].push_back(v);
adj[v].push_back(u);
}
for (auto &x : adj) {
sort(x.second.begin(), x.second.end());
}
ans += count_triangles(edges, adj);
//cerr << fast_checker(H) << " ";
return ans;
}
std::vector<int> construct_range(int M, int K) {
return {1, 1, 1};
}
