#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <iomanip>
#include <queue>
#include <stack>
#include <numeric>
#include <cassert>
#include <cmath>
#include <random>
#include <ctime>
#include <chrono>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)x.size())
#define rep(i, a, b) for(int i = a; i < b; ++i)
template<typename C> struct rge{C l, r;};
template<typename C> rge<C> range(C i, C j) { return rge<C>{i, j}; }
template<typename C> ostream& operator<<(ostream &os, rge<C> r) { os << '{'; for(auto it = r.l; it != r.r; it++) os << "," + (it == r.l) << *it; os << '}'; return os; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '{' << p.first << "," << p.second << '}'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ","; return os << '}'; }
void dbg_out() { cerr << ']' << endl; }
template<typename A> void dbg_out(A H) { cerr << H; dbg_out(); }
template<typename A, typename B, typename... C> void dbg_out(A H, B G, C... T) { cerr << H << ","; dbg_out(G, T...); }
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = [", dbg_out(__VA_ARGS__)
#else
#define debug(...)
#endif
template <typename T>
void remove_duplicates(vector<T> &v){
sort(all(v));
v.resize(unique(all(v)) - v.begin());
}
template <typename T> void chmin(T &a, T b){ a = (b < a) ? b : a; }
template <typename T> void chmax(T &a, T b){ a = (b > a) ? b : a; }
ll n;
vi h;
ll count_easy() {
set<array<int, 3>> triples;
auto test3 = [&](int a, int b, int c) {
if (c < 0 || c >= n) {
return;
}
int arr[3]{a, b, c};
sort(arr, arr + 3);
a = arr[0];
b = arr[1];
c = arr[2];
int diffs[3]{b - a, c - b, c - a};
int vals[3]{h[a], h[b], h[c]};
sort(diffs, diffs + 3);
sort(vals, vals + 3);
for (int i = 0; i < 3; ++i) {
if (diffs[i] != vals[i]) {
return;
}
}
triples.insert({a, b, c});
};
auto test2 = [&](int a, int b) {
if (b < 0 || b >= n) {
return;
}
test3(a, b, a + h[b]);
test3(a, b, a - h[b]);
test3(a, b, b + h[b]);
test3(a, b, b - h[b]);
};
for (int i = 0; i < n; ++i) {
test2(i, i - h[i]);
test2(i, i + h[i]);
}
return triples.size();
}
ll count_triples(vector<int> H) {
swap(H, h);
n = h.size();
ll ans = count_easy();
for (int i = 0; i < n; ++i) {
int j = i + h[i];
int k = j + h[i];
if (k >= n) {
continue;
}
ans -= h[k] == h[i] && h[j] == 2 * h[i];
}
for (int i = 0; i < n; ++i) {
int j = i + 1;
int k = j + h[i];
for (; k < n; ++j, ++k) {
ans += (h[j] == (k - i)) && (h[k] == (j - i));
}
}
return ans;
}
std::vector<int> construct_range(int M, int K) { return {};}
#ifdef LOCAL_TEST
int main() {
vector<int> H = {4,1,4,3,2,6,1};
cout << count_triples(H) << "\n"; // 3
}
#endif
