#include "triples.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define lol ios::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef long double ld;
using namespace std;
const ll M = 998244353;
long long count_triples(std::vector<int> H) {
int N = H.size();
ll ans = 0;
for(int i=0; i<N; i++) {
int j = H[i] + i;
if(i < j && j < N) {
int k1 = H[j] + i, k2 = H[j] + j, k3 = j - H[j];
if(i < k1 && k1 < N && H[k1] == abs(k1 - j)) ans++;
if(j < k2 && k2 < N && H[k2] == k2 - i) ans++;
if(i < k3 && k3 < j && H[k3] == k3 - i) ans++;
}
}
for(int j=0; j<N; j++) {
int i = j - H[j];
if(0 <= i && i < j) {
int k = H[i] + j;
if(j < k && k < N && H[k] == k - i) ans++;
}
}
map<int,vector<int>> mp;
for(int i=0; i<N; i++) mp[H[i]-i].push_back(i);
int d = sqrt(N);
for(auto & p : mp) {
if(p.S.size() <= d) {
for(int x=0; x<p.S.size(); x++) for(int y=x+1; y<p.S.size(); y++) {
int i=p.S[x], j = p.S[y], k = H[i] + j;
if(j < k && k < N && H[k] == j-i) ans++;
}
} else {
for(int k=0; k<N; k++) {
int sm = k - p.F, df = H[k];
if((sm - df) % 2 == 0) {
int i = (sm-df)/2, j = (sm+df)/2;
if(0 <= i && i < j && j < k && H[i]-i == p.F && H[j]-j == p.F) ans++;
}
}
}
}
for(int i=0; i<N; i++) {
int d1 = H[i], d2 = H[i]/2;
if(i + 2*d1 < N && ((H[i+d1] == d1 && H[i+2*d1] == 2*d1) || (H[i+d1] == 2*d1 && H[i+2*d1] == d1))) ans--;
if(H[i] % 2 == 0 && i + 2*d2 < N && H[i+d2] == d2 && H[i+2*d2] == d2) ans--;
}
return ans;
}
std::vector<int> construct_range(int M, int K) {
return {1, 1, 1};
}
