#include "bits/stdc++.h"
// #include "grader.cpp"
#include "triples.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
#define mm make_pair
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
ll count_triples(vector<int> h){
int n=(int)h.size();
ll answer=0;
for(int i = 0; i < n-2; ++i){ // h[i] is the largest. Case #1
int k=i+h[i];
if(k>=n and h[i]<=h[k])
continue;
// h[k]==j-i or k-j
// let's take the first example, h[k]+i=j, it should be in range [i+1, k-1], h[k]+i>i => h[k]>0, problem statement already said that h[i]>0 for all i.
if(h[k]+i<k){
int j=h[k]+i;
if(i<j and j<k and h[j]==k-j)
answer++;
}
if(k-h[k]>i){
int j=k-h[k];
if(i<j and j<k and h[j]==j-i)
answer++;
}
}
for(int k = 2; k < n; ++k){ // h[k] is the largest. Case #2
int i=k-h[k];
if(i<0 or h[k]<=h[i])
continue;
if(h[i]+i<k){
int j=h[i]+i;
if(i<j and j<k and h[j]==k-j)
answer++;
}
if(k-h[i]>i){
int j=k-h[i];
if(i<j and j<k and h[j]==j-i)
answer++;
}
}
for(int i = 0; i < n-2; ++i){ // Case #3
int j=h[i]+i;
if(j>=n-1)
continue;
int k=h[j]+i;
if(k<=j)
continue;
if(i<j and j<k and h[j]==k-i and h[i]==j-i and h[k]==k-j)
answer++;
}
// only part to calculate
// number of triplets s.t. h[i]=k-j, h[j]=k-i, h[k]=j-i;
map<int, vector<int>> u, v;
for(int i = 0; i < n; ++i)
u[i+h[i]].pb(i), v[i-h[i]].pb(i);
for(int j = 1; j < n-1; ++j){
if((int)u[j+h[j]].size()<(int)v[j-h[j]].size()){
tr(it, u[j+h[j]]){
int k=*it;
if(k<=j)
continue;
int i=k-h[j];
if(i>=0 and i<j and h[i]==k-j and h[j]==k-i and h[k]==j-i and h[i]!=h[k]) // for not over couting
answer++;
// h[j]=k-i => i=k-h[j]
}
continue;
}
tr(it, v[j-h[j]]){
int i=*it;
if(i>=j)
break;
int k=i+h[j];
if(k>j and k<n and h[i]==k-j and h[j]==k-i and h[k]==j-i and h[i]!=h[k]) // for not over counting
answer++;
}
}
return answer;
}
vector<int> construct_range(int M, int K) {
return {1, 1, 1};
}
