#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
vector<ll> h;
unordered_set<ll> ans;
ll mul = 1e6;
ll SQ = 0;
void comp(ll i, ll j, ll k)
{
if (i == j || i == k || j == k)
return;
vector<ll> v = {abs(i - j), abs(i - k), abs(j - k)}, v2 = {h[i], h[j], h[k]};
ll has = 0;
sort(all(v));
sort(all(v2));
if (v == v2)
{
vector<ll> ret = {i, j, k};
sort(all(ret));
if (ret[1] - ret[0] == ret[2] - ret[1] && h[ret[1]] == ret[2] - ret[0])
return;
has = ret[0] * mul * mul + ret[1] * mul + ret[2];
ans.insert(has);
}
}
long long count_triples(std::vector<int> H)
{
for (auto k : H)
h.pb(k);
ll i, j, k, a, b, a2, b2, c, c2;
auto calc = [&]()
{
b = a - h[a];
if (b >= 0)
comp(k, a, b);
b2 = a + h[a];
if (b2 < sz(h))
comp(k, a, b2);
c = k - h[a];
if (c >= 0)
comp(k, a, c);
c = k + h[a];
if (c < sz(h))
comp(k, a, c);
};
for (k = 0; k < sz(h); k++)
{
a = k - h[k];
if (a >= 0)
calc();
a2 = k + h[k];
if (a2 < sz(h))
{
a = a2;
calc();
}
}
ll ag = 0, tot, ca, act = 0;
vector<vector<ll>> ordR(sz(h) * 2), ordL(sz(h) * 2);
vector<ll> vis(sz(h) * 2, -1), R(sz(h)), L(sz(h));
for (i = 0; i < sz(h); i++)
{
ordR[i + h[i]].pb(i);
ordL[i - h[i] + sz(h)].pb(i);
R[i]=i+h[i];
L[i]=i-h[i]+sz(h);
}
for (i = 0; i < sz(h) * 2; i++)
{
act++;
for (auto &x : ordL[i])
vis[h[x]] = act;
for (auto &x : ordL[i])
{
if (sz(ordL[i]) >= sz(ordR[R[x]]))
{
for (auto &y : ordR[R[x]])
{
if (h[x] > h[y] && vis[h[x] - h[y]]==act)
ag++;
}
}
}
act++;
for (auto &x : ordR[i])
vis[h[x]] = act;
for (auto &x : ordR[i])
{
if (sz(ordR[i]) > sz(ordL[L[x]]))
{
for (auto &y : ordL[L[x]])
{
if (h[x] > h[y] && vis[h[x] - h[y]]==act)
ag++;
}
}
}
}
return ag + sz(ans);
}
std::vector<int> construct_range(int M, int K)
{
return {1, 1, 1};
}
