#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
long long count1(vector<int> &H)
{
int n = H.size();
long long ans = 0;
for(int i=0; i<n; i++)
{
if(i + H[i] < n)
{
int pa = i;
int pb = pa + H[pa];
//a - [c] - c - [b] - b
int pc = pb - H[pb];
if(pc - pa == H[pc])
ans++;
//a - [b] - c - [c] - b
pc = pa + H[pb];
if(pb - pc == H[pc])
ans++;
}
}
reverse(H.begin(), H.end());
for(int i=0; i<n; i++)
{
if(i + H[i] < n)
{
int pa = i;
int pb = pa + H[pa];
//a - [c] - c - [b] - b
int pc = pb - H[pb];
if(pc - pa == H[pc])
ans++;
//a - [b] - c - [c] - b
pc = pa + H[pb];
if(pb - pc == H[pc])
ans++;
}
}
return ans;
}
long long count2(vector<int> &H)
{
int n = H.size();
long long ans = 0;
for(int i=0; i<n; i++)
{
int pb = i;
int pa = pb - H[pb];
if(pa < 0)
continue;
int pc = pb - H[pa];
if(pc < 0)
continue;
if(H[pb] == H[pc])
continue;
if(pa - pc == H[pc])
ans++;
}
return ans;
}
long long count3(vector<int> &H)
{
int n = H.size();
long long ans = 0;
for(int pa=0; pa<n; pa++)
for(int pb=pa+1; pb<=min(n-1, pa+H[pa]); pb++)
for(int pc=pa-1; pc>=min(0, pa - H[pa]); pc--)
if( pb - pa == H[pc] &&
pa - pc == H[pb] &&
pb - pc == H[pa])
ans++;
return ans;
}
long long count_triples(std::vector<int> H)
{
long long ans = 0;
ans += count1(H);
ans += count2(H);
ans += count3(H);
return ans;
}
std::vector<int> construct_range(int M, int K) {
return {1, 1, 1};
}
