#include "triples.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+9;
const int sqr = 410;
ll code_tri(ll a, ll b, ll c)
{
return a + b*200001LL + c*200001LL*200001LL;
}
vi decode_tri(ll x)
{
int a = x % 200001LL;
x /= 200001LL;
int b = x % 200001LL;
x /= 200001LL;
return {a,b,(int)x};
}
vi L_pot[400001];
vi R_pot[400001];
ll cntL[400001];
ll cntR[400001];
int H[200001];
int n;
ll ans = 0;
void solve(vi& l, vi& r)
{
forall(it,l)
{
cntL[H[it]-it+200000]++;
}
forall(it,r)
{
cntR[H[it]+it]++;
}
rep(it,n)
{
ans += cntL[H[it]-it+200000]*cntR[H[it]+it];
}
forall(it,l)
{
cntL[H[it]-it+200000]--;
}
forall(it,r)
{
cntR[H[it]+it]--;
}
}
ll count_triples(vi H2)
{
unordered_set<ll> tri;
n = siz(H2);
rep(i,n) H[i] = H2[i];
rep(i,n)
{
// l-s s-r l-r
if(i+H[i] < n && i+H[i]+H[i+H[i]] < n && H[i+H[i]+H[i+H[i]]] == i+H[i]+H[i+H[i]] - i) tri.insert(code_tri(i,i+H[i],i+H[i]+H[i+H[i]]));
// l-s l-r s-r
if(i+H[i] < n && i+H[i+H[i]] < n && H[i+H[i+H[i]]] == i+H[i+H[i]] - (i+H[i])) tri.insert(code_tri(i,i+H[i],i+H[i+H[i]]));
// l-r l-s s-r
if(i+H[i] < n && i+H[i]-H[i+H[i]] >= 0 && H[i+H[i]-H[i+H[i]]] == i+H[i]-H[i+H[i]] - i) tri.insert(code_tri(i,i+H[i]-H[i+H[i]],i+H[i]));
// l-r s-r l-s
if(i+H[i] < n && i+H[i+H[i]] < n && H[i+H[i+H[i]]] == i+H[i] - (i+H[i+H[i]])) tri.insert(code_tri(i,i+H[i+H[i]],i+H[i]));
// s-r s-l r-l i = S
if(i-H[i] >= 0 && i+H[i-H[i]] < n && H[i+H[i-H[i]]] == i+H[i-H[i]] - (i-H[i])) tri.insert(code_tri(i-H[i],i,i+H[i-H[i]]));
}
forall(it,tri)
{
vi v = decode_tri(it);
int a = v[0];
int b = v[1];
int c = v[2];
if(!(H[a] == c-b && H[b] == c-a && H[c] == b-a))
{
ans++;
}
}
rep(i,n)
{
L_pot[H[i]+i].pb(i);
if(i - H[i] >= 0) R_pot[i-H[i]].pb(i);
}
// s-r r-l s-l
rep(o,n*2)
{
if(siz(L_pot[o]) < sqr)
{
forall(itL,L_pot[o])
{
forall(itR,R_pot[o])
{
int itS = itL + H[itR];
if(itS < n && H[itL] == itR-itS && H[itS] == itR-itL && H[itR] == itS-itL) ans++;
}
}
}
else
{
solve(L_pot[o],R_pot[o]);
}
}
return ans;
}
vi construct_range(int M, int K)
{
}
