#include "triples.h"
#include <bits/stdc++.h>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
using namespace std;
vector<int> a;
bool ok(int i , int j , int k){
vector<int> X = {j - i , k - j , k - i};
vector<int> Y = {a[i] , a[j] , a[k]};
sort(all(X)); sort(all(Y));
bool check = true;
for (int id = 0 ; id < 3 ; id++){
if (X[id] != Y[id]) return false;
}
return true;
}
namespace sub5{
const int maxN = int(2e5)+7;
vector<int> pre[2 * maxN] , suf[2 * maxN];
long long solve(){
set<pair<int , pair<int , int>>> st;
int n = sz(a);
//i , j , k
for (int i = 0 ; i < n ; i++){
int j = i + a[i];
if (j >= n) continue;
int k = j + a[j];
if (k >= n) continue;
if (ok(i , j , k)) st.insert({i , {j , k}});
}
//i , k , j
for (int i = 0 ; i < n ; i++){
int j = i + a[i];
if (j >= n) continue;
int k = i + a[j];
if (k >= n) continue;
if (ok(i , j , k)) st.insert({i , {j , k}});
}
//j , i , k
for (int j = 0 ; j < n ; j++){
int i = j - a[j];
if (i < 0) continue;
int k = j + a[i];
if (k >= n) continue;
if (ok(i , j , k)) st.insert({i , {j , k}});
}
//j , k , i
for (int j = 0 ; j < n ; j++){
int i = j - a[j];
if (i < 0) continue;
int k = i + a[i];
if (k >= n) continue;
if (ok(i , j , k)) st.insert({i , {j , k}});
}
//k , j , i
for (int i = 0 ; i < n ; i++){
int k = i + a[i];
if (k >= n) continue;
int j = i + a[k];
if (j >= n) continue;
if (ok(i , j , k)) st.insert({i , {j , k}});
}
long long ans = sz(st);
//k , i , j
for (int k = n - 1 ; k >= 0 ; k--){
suf[a[k] + k].push_back(k);
}
for (int j = 0 ; j < n ; j++){
suf[a[j] + j].pop_back();
if (sz(pre[a[j] - j + maxN]) < sz(suf[a[j] + j])){
for (int i : pre[a[j] - j + maxN]){
int k = j + a[i];
if (k < n){
if (a[j] + j == a[k] + k) ans++;
}
}
}
else{
for (int k : suf[a[j] + j]){
int i = j - a[k];
if (i >= 0){
if (a[i] - i == a[j] - j) ans++;
}
}
}
pre[a[j] - j + maxN].push_back(j);
}
for (int j = 0 ; j < n ; j++){
if (a[j]&1) continue;
int i = j - a[j] / 2;
int k = j + a[j] / 2;
if (i < 0 || k >= n) continue;
if (ok(i , j , k)) ans--;
}
return ans;
}
}
long long count_triples(vector<int> h){
a = h;
return sub5::solve();
}
vector<int> construct_range(int m , int k) {
return {1 , 1 , 1};
}
// int main(){
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("templete.inp" , "r" , stdin);
// freopen("templete.ans" , "w" , stdout);
// int n; cin >> n;
// vector<int> h(n);
// for (int &x : h) cin >> x;
// cout << count_triples(h) << "\n";
// return 0;
// }
