#include "triples.h"
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <iostream>
#define pb push_back
using namespace std;
int check(int i, int j, int k, vector<int>& h) {
vector <int> x, x2;
x.pb(h[i]);
x.pb(h[j]);
x.pb(h[k]);
sort(x.begin(), x.end());
x2.pb(abs(i - j));
x2.pb(abs(j - k));
x2.pb(abs(k - i));
sort(x2.begin(), x2.end());
if (x[0] == x2[0] && x[1] == x2[1] && x[2] == x2[2]) {
return 1;
}
return 0;
}
long long count_triples(std::vector<int> H) {
int n = H.size();
long long ans = 0;
vector <int> h(n);
for (int i = 0; i < n; i++) {
h[i] = H[i];
// cout<<h[i]<<" ";
}
// cout<<"\n";
for (int i = 0; i < n; i++) {
int k = h[i] + i;
if (k <= i + 1 || k >= n) continue;
int j = h[k] + i;
if (j > i && j < k) {
ans += check(i, j, k, h);
}
int j2 = k - h[k];
if (j2 > i && j2 < k && j2 != j) {
ans += check(i, j2, k, h);
}
}
for (int k = 0; k < n; k++) {
int i = k - h[k];
if (i < 0 || i >= k) continue;
int j = h[i] + i;
if (j > i && j < k) {
ans += check(i, j, k, h);
}
int j2 = k - h[i];
if (j2 > i && j2 < k && j2 != j) {
ans += check(i, j2, k, h);
}
}
// int res = 0;
// for (int i = 0; i < n; i++) {
// for (int j = i + 1; j < n; j++) {
// for (int k = j + 1; k < n; k++) {
// if (check(i, j, k, h) && (k - i == h[i] || k - i == h[k])) {
// res++;
// }
// }
// }
// }
// cout << "res: " << res << "\n";
// cout << "ans: " << ans << "\n";
for (int i = 0; i < n; i++) {
int j = h[i] + i;
int k = h[j] + i;
// cout << "i: " << i << ", j: " << j << ", k: " << k << " " << check(i, j, k, h) << "\n";
if (j < i + 1 || j > n) continue;
if (k > j && k < n) {
ans += check(i, j, k, h);
}
}
// for (int i = 0; i < n; i++) {
// for (int j = i + 1; j < n; j++) {
// for (int k = j + 1; k < n; k++) {
// if (check(i, j, k, h) && k - i == h[j] && h[i] == j - i && h[k] == k - j) {
// res++;
// cout << "i: " << i << ", j: " << j << ", k: " << k << "\n";
// }
// }
// }
// }
// cout << "res: " << res << "\n";
// cout << "ans: " << ans << "\n";
vector <vector<int>> vec(2 * n + 1);
for (int i = 0; i < n; i++) {
vec[h[i] - i + n].pb(i);
}
int b = 300;
for (int dif = 0; dif <= 2 * n; dif++) {
if (vec[dif].size() < b) {
for (int i : vec[dif]) {
for (int j : vec[dif]) {
if (j <= i) continue;
int k = h[j] + i;
// if (dif == n) {
// cout << i << " " << j << " " << k << " " << h[i] << " " << h[j] << "\n";
// }
if (k > j && k < n && h[j] == k - i && h[i] != h[k]) {
// if (dif == n) {
// cout << i << " -- " << j << " " << k << " " << h[i] << " " << h[j] << "\n";
// }
ans += check(i, j, k, h);
}
}
}
} else {
int act = dif - n;
// vector <int> fix(n, 0);
// for (int idx : vec[dif]) {
// fix[idx] = 1;
// }
for (int k = 2; k < n; k++) {
int i2 = k - h[k] - act;
if (i2 < 0 || i2 % 2) continue;
int i = i2 / 2;
if (i < 0 || i >= n) continue;
int j = h[k] + i;
if (j > i && j < k && h[j] == k - i && h[i] != h[k]) {
ans += check(i, j, k, h);
}
}
}
}
return ans;
}
std::vector<int> construct_range(int M, int K) {
return {1, 1, 1};
}
