#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct mst {
vector<vector<int>> st;
size_t sz;
mst(vector<int> a) {
sz = 1;
while (sz < a.size()) {
sz <<= 1;
}
st.resize(2 * sz);
for (int i = 0; i < a.size(); i++) {
st[sz + i].push_back(a[i]);
}
for (int i = sz - 1; i > 0; i--) {
st[i].resize(st[2 * i].size() + st[2 * i + 1].size());
ranges::merge(st[2 * i], st[2 * i + 1], st[i].begin());
}
}
int get_same(int l, int r, int v) {
l += sz; r += sz;
int res = 0;
while (l <= r) {
if (l & 1) {
res += ranges::upper_bound(st[l], v) - ranges::lower_bound(st[l], v);
l++;
}
if (~r & 1) {
res += ranges::upper_bound(st[r], v) - ranges::lower_bound(st[r], v);
r--;
}
l >>= 1;
r >>= 1;
}
return res;
}
};
ll count_triples(vector<int> h) {
int n = h.size();
vector<int> ff = h, ss = h;
vector<int> prev(n), next(n);
for (int i = 0; i < n; i++) {
ff[i] -= i;
ss[i] += i;
}
map<int, int> mp;
for (int i = 0; i < n; i++) {
if (mp.find(ff[i]) == mp.end()) {
prev[i] = -1;
} else {
prev[i] = mp[ff[i]];
}
mp[ff[i]] = i;
}
mp.clear();
for (int i = n - 1; i >= 0; i--) {
if (mp.find(ss[i]) == mp.end()) {
next[i] = n;
} else {
next[i] = mp[ss[i]];
}
mp[ss[i]] = i;
}
mst mst1(ff), mst2(ss);
ll ans = 0;
auto check1 = [&](int i, int j, int k) -> bool {
vector<int> x = {abs(i - j), abs(j - k), abs(k - i)}, y = {h[i], h[j], h[k]};
ranges::sort(x);
ranges::sort(y);
return x == y;
};
auto check2 = [&](int i, int j, int k) -> bool {
if (abs(k - i) == h[j] && abs(i - j) == h[k] && abs(j - k) == h[i]) return false;
return check1(i, j, k);
};
auto srt = [](tuple<int, int, int> t) -> tuple<int, int, int> {
vector<int> x = {get<0>(t), get<1>(t), get<2>(t)};
ranges::sort(x);
return {x[0], x[1], x[2]};
};
set<tuple<int, int, int>> simp;
for (int i = 0; i < n; i++) {
if (i - h[i] >= 0) {
int j = i - h[i];
if (j - h[j] >= 0) {
int l = j - h[j];
if (check2(i, j, l)) {
simp.insert(srt({i, j, l}));
}
}
if (j + h[j] < n) {
int l = j + h[j];
if (check2(i, j, l)) {
simp.insert(srt({i, j, l}));
}
}
if (i - h[j] >= 0) {
int l = i - h[j];
if (check2(i, j, l)) {
simp.insert(srt({i, j, l}));
}
}
if (i + h[j] < n) {
int l = i + h[j];
if (check2(i, j, l)) {
simp.insert(srt({i, j, l}));
}
}
}
if (i + h[i] < n) {
int j = i + h[i];
if (j - h[j] >= 0) {
int l = j - h[j];
if (check2(i, j, l)) {
simp.insert(srt({i, j, l}));
}
}
if (j + h[j] < n) {
int l = j + h[j];
if (check2(i, j, l)) {
simp.insert(srt({i, j, l}));
}
}
if (i - h[j] >= 0) {
int l = i - h[j];
if (check2(i, j, l)) {
simp.insert(srt({i, j, l}));
}
}
if (i + h[j] < n) {
int l = i + h[j];
if (check2(i, j, l)) {
simp.insert(srt({i, j, l}));
}
}
}
}
ans += simp.size();
simp.clear();
for (int i = 0; i < n; i++) {
if (mst1.get_same(0, i, ff[i]) < mst2.get_same(i, n - 1, ss[i])) {
int cur = prev[i];
while (cur != -1) {
if (i + h[cur] < n && check1(cur, i, i + h[cur])) {
ans++;
}
cur = prev[cur];
}
} else {
int cur = next[i];
while (cur != n) {
if (i - h[cur] > 0 && check1(i - h[cur], i, cur)) {
ans++;
}
cur = next[cur];
}
}
}
return ans;
}
std::vector<int> construct_range(int M, int K) {
return {1, 2, 1};
}
