#include "triples.h"
# include <bits/stdc++.h>
# pragma GCC optimize("unroll-loops")
# pragma GCC optimize("Ofast")
# define ll long long
# define fi first
# define se second
# define pii pair<int, int>
using namespace std;
vector<int> num[600001];
vector< pair<int, pii> > ct;
int ss[200001];
pair<int, pii> sr(int a, int b, int c) {
if(a > b) swap(a, b);
if(b > c) swap(b, c);
if(a > b) swap(a, b);
return {a, {b, c}};
}
int fn() {
sort(ct.begin(), ct.end());
int cnt = 0;
for(int i=0;i<ct.size();i++) {
if(i == 0 || ct[i] != ct[i - 1]) cnt++;
}
return cnt;
}
int arr[200001];
int N;
bool cek(int a, int b, int c) {
if(a == b || a == c || b == c) return 0;
if(a < 1 || b < 1 || c < 1) return 0;
if(a > N || b > N || c > N) return 0;
// cout<<"cek ? "<<a<<" "<<b<<" "<<c<<endl;
if(sr(abs(a - b), abs(a - c), abs(b - c)) == sr(arr[a], arr[b], arr[c])) return 1;
return 0;
}
ll count_triples(vector<int> H) {
ct.clear();
N = H.size();
for(int i=0;i<N;i++) {
arr[i + 1] = H[i];
}
for(int i=1;i<=N;i++) {
// cout<<"cc : "<<i<<" "<<i + arr[i]<<endl;
if(i > arr[i]) {
int x = i - arr[i];
if(x > arr[x]) {
int y = x - arr[x];
if(cek(i, x, y)) ct.push_back(sr(i, x, y));
}
if(x + arr[x] <= N) {
if(cek(i, x, x + arr[x])) ct.push_back(sr(i, x, x + arr[x]));
}
if(i - arr[x] > 0) {
if(cek(i, x, i - arr[x])) ct.push_back(sr(i, x, i - arr[x]));
}
if(i + arr[x] <= N) {
if(cek(i, x, i + arr[x])) ct.push_back(sr(i, x, i + arr[x]));
}
}
if(i + arr[i] <= N) {
int x = i + arr[i];
if(x > arr[x]) {
int y = x - arr[x];
if(cek(i, x, y)) ct.push_back(sr(i, x, y));
}
if(x + arr[x] <= N) {
if(cek(i, x, x + arr[x])) ct.push_back(sr(i, x, x + arr[x]));
}
if(i - arr[x] > 0) {
if(cek(i, x, i - arr[x])) ct.push_back(sr(i, x, i - arr[x]));
}
if(i + arr[x] <= N) {
if(cek(i, x, i + arr[x])) ct.push_back(sr(i, x, i + arr[x]));
}
}
}
// cout<<"fn : "<<fn()<<endl;
int sq = ceil(sqrt(N));
for(int i=0;i<=3*N;i++) num[i].clear();
for(int i=N;i>=1;i--) {
for(auto x : num[i + arr[i] + N]) {
if(cek(i, x, i + arr[x])) ct.push_back(sr(i, x, i + arr[x]));
}
if(num[i - arr[i] + N].size() < sq) num[i - arr[i] + N].push_back(i);
else ss[i]++;
}
for(int i=0;i<=3*N;i++) num[i].clear();
for(int i=N;i>=1;i--) {
for(auto x : num[i + arr[i] + N]) {
if(cek(i, x, x - arr[i])) ct.push_back(sr(i, x, x - arr[i]));
}
if(num[i + arr[i] + N].size() < sq) num[i + arr[i] + N].push_back(i);
else ss[i]++;
}
int calc = 0;
for(int i=1;i<=N;i++) calc++;
for(int i=1;i<=N;i++) {
if(ss[i] == 2) {
for(int c = max(1, i - arr[i]);c <= i + arr[i] && c <= N;c++) {
if(cek(c, i, c + arr[i])) ct.push_back(sr(c, i, arr[i]));
}
}
}
return fn();
}
std::vector<int> construct_range(int M, int K) {
vector<int> arr = {3, 1, 2, 1, 4, 3, 2, 7};
vector<int> ans(M);
for(int i=0;i<M;i++) {
ans[i] = arr[i % 8];
}
return ans;
}
