#include "triples.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
long long calc(vector<int> h)
{
int n = size(h), isSorted = 1;
int maxH = *max_element(begin(h), end(h));
vector<int> l(n, -1), r(n, -1);
vector<vector<int>> hAt(maxH + 1);
for (int i = 0; i < n; i++)
{
if (h[i] <= i)
l[i] = i - h[i];
if (i + h[i] < n)
r[i] = i + h[i];
if (i && h[i - 1] > h[i])
isSorted = 0;
hAt[h[i]].push_back(i);
}
long long res = 0;
for (int i = 0; i < n; i++)
{
int j = r[i];
if (j < 0)
continue;
// 2.3..5
if (r[j] >= 0 && h[r[j]] == h[i] + h[j])
res++;
// 2.5..3
if (h[j] > h[i])
{
int k = j + h[j] - h[i];
if (k < n && l[k] == j)
res++;
}
// 5.3..2
if (h[j] < h[i])
{
int k = i + h[j];
if (r[k] == j && h[k] != h[j]) // exclude 211
res++;
}
// 2..5.3
if (maxH <= 10)
{
for (int hj = 1; hj <= maxH; hj++)
if (hj != h[i])
{
int j = i + hj + h[i];
if (j < n && h[j] == hj && h[i + hj] == h[i] + hj)
res++;
}
}
else if (!isSorted)
{
for (int k = i + 1; k < n; k++)
if (l[k] == j && h[k] != h[i] && h[i + h[k]] == h[i] + h[k])
res++;
}
}
for (int i = 0; i < n; i++)
{
int j = l[i];
if (j < 0)
continue;
// 5.2..3
if (l[j] >= 0 && h[l[j]] == h[i] + h[j])
res++;
// 3.2..5
int k = i + h[j];
if (r[j] != i && k < n && h[k] == h[i] + h[j]) // exclude 112
res++;
}
return res;
}
long long count_triples(vector<int> h) {
return calc(h);
}
vector<int> construct_range(int M, int K) {
return {1, 1, 1};
}
