#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
static inline bool is_mythical(const vector<int>& H, int i, int j, int k){
int a = j - i;
int b = k - j;
int c = k - i;
array<int,3> d = {a,b,c};
array<int,3> h = {H[i], H[j], H[k]};
sort(d.begin(), d.end());
sort(h.begin(), h.end());
return d == h;
}
long long count_triples(vector<int> H){
int N = (int)H.size();
unordered_set<unsigned long long> seen;
seen.reserve((size_t)N * 8);
auto key = [&](int i,int j,int k)->unsigned long long{
return ( (unsigned long long)i << 42 ) ^ ( (unsigned long long)j << 21 ) ^ (unsigned long long)k;
};
auto try_add = [&](int i,int j,int k){
if(i < 0 || j < 0 || k < 0) return;
if(i >= N || j >= N || k >= N) return;
if(!(i < j && j < k)) return;
if(!is_mythical(H, i, j, k)) return;
seen.insert(key(i,j,k));
};
unordered_set<unsigned long long> usedPairs;
usedPairs.reserve((size_t)N * 4);
auto pairkey = [&](int i,int j)->unsigned long long{
return ( (unsigned long long)i << 21 ) ^ (unsigned long long)j;
};
auto process_pair = [&](int i, int j, int a){
if(!(0 <= i && i < j && j < N)) return;
unsigned long long pk = pairkey(i,j);
if(usedPairs.find(pk) != usedPairs.end()) return;
usedPairs.insert(pk);
int hi = H[i], hj = H[j];
if(hi > a){
int b = hi - a;
try_add(i, j, j + b);
}
if(hj > a){
int b = hj - a;
try_add(i, j, j + b);
}
{
int b = hi;
try_add(i, j, j + b);
}
{
int b = hj;
try_add(i, j, j + b);
}
};
for(int u=0;u<N;u++){
int d = H[u];
int v = u + d;
if(v < N) process_pair(u, v, d);
}
for(int u=0;u<N;u++){
int d = H[u];
int i = u - d;
if(i >= 0) process_pair(i, u, d);
}
return (long long)seen.size();
}
vector<int> construct_range(int M, int K){
int N = max(3, min(M, 200000));
vector<int> H(N, 1);
for(int i=0;i<N;i++){
H[i] = min(N-1, max(1, (i%2 ? 1 : 2)));
}
return H;
}
