#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
ll count_triples(vt<int> H) {
const int N = size(H);
ll ans = 0;
set<ari3> s;
const auto check = [&](const int i, const int j, const int k, bool bruh) {
if (!(i < j && j < k && i >= 0 && k < N))
return false;
ari3 a = {j - i, k - i, k - j};
ari3 b = {H[i], H[j], H[k]};
sort(all(a));
sort(all(b));
if (a == b && bruh)
s.insert({i, j, k});
return a == b;
};
FOR(i, 1, N-2) {
s.clear();
if (i-H[i] >= 0) {
check(i-H[i], i, i+H[i-H[i]], 1);
check(i-H[i], i, i-H[i]+H[i-H[i]], 1);
}
if (i+H[i] < N) {
check(i-H[i+H[i]], i, i+H[i], 1);
check(i+H[i]-H[i+H[i]], i, i+H[i], 1);
}
ans += size(s);
}
FOR(i, 0, N-3) {
const int j = i + H[i];
if (j < N-1 && H[j] > H[i]) {
const int k = i + H[j];
ans += check(i, j, k, 0) && H[i] != H[k];
}
}
// a < b < c
// max(H[a], H[c]) < H[b]
// b - a = H[c]
// c - b = H[a]
// c - a = H[b]
// c - a = H[c] + H[a]
// a + H[a] = c - H[c]
// b - a + H[b] = H[c] + c - a
// b + H[b] = c + H[c]
// b - c - H[b] = -H[a] - c + a
// b - H[b] = a - H[a]
vt<vt<int>> d1(N<<1), d2(N<<1);
FOR(i, 0, N-1) {
d1[i-H[i]+N].push_back(i);
d2[i+H[i]].push_back(i);
}
FOR(b, 1, N-2) {
if (size(d1[b-H[b]+N]) < size(d2[b+H[b]]))
for (const auto &a : d1[b-H[b]+N])
ans += check(a, b, b + H[a], 0);
else
for (const auto &c : d2[b+H[b]])
ans += check(b - H[c], b, c, 0);
}
return ans;
}
vt<int> construct_range(int M, int K) {
vt<int> ret(M);
FOR(i, 0, M-1)
ret[i] = i % 2 + 1;
return ret;
}
