#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
struct Triplet {
int i, j, k;
};
int n;
map<pair<pair<int, int>, int>, int> mapper;
vector<int> h;
bool check(int i, int j, int k) {
if (i < 0 || j < 0 || k < 0 || i >= n || j >= n || k >= n) return 0;
if (!(i < j && j < k)) return 0;
if (mapper.count({{i, j}, k})) return 0;
vector<int> a = {h[i], h[j], h[k]};
vector<int> b = {j-i, k-j, k-i};
sort(a.begin(), a.end());
sort(b.begin(), b.end());
if (a == b) {
mapper[{{i, j}, k}] = true;
return 1;
}
return 0;
}
long long count_triples(std::vector<int> H) {
h = H;
n = h.size();
mapper = map<pair<pair<int, int>, int>, int>();
long long res = 0;
for (int i = 0; i < n; i++) {
if (i+h[i] < n) res += check(i+h[i]-h[i+h[i]], i, i+h[i]);
if (i+h[i] < n) res += check(i-h[i+h[i]], i, i+h[i]);
if (i-h[i] >= 0) res += check(i-h[i], i, i-h[i]+h[i-h[i]]);
if (i-h[i] >= 0) res += check(i-h[i], i, i+h[i-h[i]]);
}
for (int i = 0; i < n; i++) {
int j = i+h[i];
if (j >= n) continue;
int k = i + h[j];
if (k >= n) continue;
if (k <= j) continue;
if (h[i] == h[k]) continue;
vector<int> a = {h[i], h[j], h[k]};
vector<int> b = {j-i, k-j, k-i};
sort(a.begin(), a.end());
sort(b.begin(), b.end());
if (a == b) {
res++;
}
}
// for (int i = 0; i < n; i++) {
// for (int j = i+1; j < n; j++) {
// for (int k = j+1; k < n; k++) {
// res += h[k] == j-i && h[i] == k-j && h[j] == k-i;
// }
// }
// }
vector<vector<int>> groups(n);
for (int i = 0; i < n; i++) {
if (i-h[i] >= 0) groups[i-h[i]].push_back(i);
}
for (int i = 0; i < n; i++) {
if (i+h[i] >= n) continue;
for (auto k : groups[i+h[i]]) {
res += h[h[k]+i] == k-i;
}
}
// bool nonDec = true;
// for (int i = 0; i < n-1; i++) nonDec &= h[i] <= h[i+1];
// if (nonDec) {
// for (int i = 0; i < n; i++) {
// bool already = false;
// if (h[i]+i < n && h[i]+i-h[h[i]+i] >= 0 && h[i]+i-h[h[i]+i] < i) {
// vector<int> a = {h[i], h[h[i]+i], h[h[i]+i-h[h[i]+i]]};
// vector<int> b = {h[i], h[h[i]+i]-h[i], h[h[i]+i]};
// sort(a.begin(), a.end());
// sort(b.begin(), b.end());
// if (a == b) {
// already = true;
// res++;
// }
// }
// if (i-h[i] >= 0 && i+h[i-h[i]] < n && i+h[i-h[i]] > i) {
// vector<int> a = {h[i], h[i+h[i-h[i]]], h[i-h[i]]};
// vector<int> b = {h[i], h[i-h[i]], h[i]+h[i-h[i]]};
// sort(a.begin(), a.end());
// sort(b.begin(), b.end());
// if (a == b && (!already || h[i]+i-h[h[i]+i] != i-h[i] || i+h[i-h[i]] != h[i]+i)) res++;
// }
// }
// } else if (n <= 2000) {
// for (int i = 0; i < n; i++) {
// for (int j = i+1; j < n; j++) {
// if (h[i]+j < n) {
// vector<int> a = {h[i], h[j], h[h[i]+j]};
// vector<int> b = {j-i, h[i], h[i]+j-i};
// sort(a.begin(), a.end());
// sort(b.begin(), b.end());
// if (a == b) res++;
// }
// if (h[j]+j < n && h[i] != h[j]) {
// vector<int> a = {h[i], h[j], h[h[j]+j]};
// vector<int> b = {j-i, h[j], h[j]+j-i};
// sort(a.begin(), a.end());
// sort(b.begin(), b.end());
// if (a == b) res++;
// }
// if (abs(h[i]-h[j])+j < n && h[i] != abs(h[i]-h[j]) && h[j] != abs(h[i]-h[j])) {
// vector<int> a = {h[i], h[j], h[abs(h[i]-h[j])+j]};
// vector<int> b = {j-i, abs(h[i]-h[j]), abs(h[i]-h[j])+j-i};
// sort(a.begin(), a.end());
// sort(b.begin(), b.end());
// if (a == b) res++;
// }
// }
// }
// } else {
// for (int i = 0; i < n; i++) {
// for (int j = i+1; j < n && j < i+20; j++) {
// if (h[i]+j < n) {
// vector<int> a = {h[i], h[j], h[h[i]+j]};
// vector<int> b = {j-i, h[i], h[i]+j-i};
// sort(a.begin(), a.end());
// sort(b.begin(), b.end());
// if (a == b) res++;
// }
// if (h[j]+j < n && h[i] != h[j]) {
// vector<int> a = {h[i], h[j], h[h[j]+j]};
// vector<int> b = {j-i, h[j], h[j]+j-i};
// sort(a.begin(), a.end());
// sort(b.begin(), b.end());
// if (a == b) res++;
// }
// if (abs(h[i]-h[j])+j < n && h[i] != abs(h[i]-h[j]) && h[j] != abs(h[i]-h[j])) {
// vector<int> a = {h[i], h[j], h[abs(h[i]-h[j])+j]};
// vector<int> b = {j-i, abs(h[i]-h[j]), abs(h[i]-h[j])+j-i};
// sort(a.begin(), a.end());
// sort(b.begin(), b.end());
// if (a == b) res++;
// }
// }
// }
// }
return res;
}
std::vector<int> construct_range(int M, int K) {
vector<int> tmp = {8, 3, 1, 2, 1, 4, 3, 2};
vector<int> ans(M);
for (int i = 0; i < M; i++) {
ans[i] = tmp[i%8];
}
return ans;
}
