#ifndef TRIPLES_H
#define TRIPLES_H
#include <bits/stdc++.h>
#include <random>
#include <time.h>
#define fi first
#define se second
#define ii pair<int,int>
using namespace std;
//long long count_triples(std::vector<int> H){
// int n = H.size();
// vector <vector<int>> z[n];
// for (int i = 0; i < n; i++){
// for (int j = i + 1; j < n; j++){
// for (int k = j + 1; k < n; k++){
// int d1 = j - i, d2 = k - i, d3 = k - j;
// vector <int> tmp = {d1,d3,d2};
// z[i].push_back(tmp);
// // cout << d1 << " " << d2 << " " << d3 << "\n";
// }
// }
// }
// dist(i,j) + dist(j,k) = dist(i,k)
// -> d1 + d3 = d2
// for (d1) -> for (d3):
// a[i], a[i + d1], a[i + d1 + d3] = d1 , d3, d1 + d3
//
// xet a[i]
// j = i + a[i] -> co a[j]
// TH1: k = j + a[j] -> co a[k] | ok
// TH2: k = i + a[j] -> co a[k] | ok
//
// xet a[i]
// k = i + a[i]
// TH1: i + a[k]
// TH2: k - a[k]
//
//// xet a[i]
//// TH1:
//// k - j = a[i]
//// j - i = a[j]
//// k - i = a[k]
////
//// TH2:
//// k - j = a[i]
//// k = a[i] + j
//// j - i = a[k]
//// k - i = a[j]
// for (int i = 0; i < n; i++) sort(z[i].begin(), z[i].end());
// for (int i = 0; i < n; i++){
// for (auto x : z[i]){
// cout << i << " -> ";
// for (auto t : x) cout << t << " ";
// cout << "\n";
// }
// cout << "\n";
// }
// return 10;
//}
int n;
map <array<int,3>, bool> mps;
map <pair<int,int>, bool> rock;
void ct3(int i, int j, int k){
//cout << " -> " << i << " " << j << " " << k << "\n";
assert(i < j && j < k && i >=0 && k < n);
array<int,3> f = {i,j,k};
// if (mps[f] == true){
// for (auto x : gg) cout << x << " ";
// cout << "\n";
// }
// assert(mps[f] == false);
mps[f] = true;
}
long long count_triples(std::vector<int> H){
n = H.size();
mps.clear();
rock.clear();
int qut = 0;
vector <int> f[2 * n];
for (int i = 0; i < n; i++){
f[i + H[i]].push_back(i);
// rock[{i + H[i], i}] = 1;
}
for (int j = 1; j < n - 1; j++){
if (true){
int i = j - H[j];
if (i >= 0){
int k = j + H[i];
if (i >= 0 && k < n && H[k] == k - i) ct3(i,j,k);
}
}
if (true){
int i = j - H[j];
if (i >= 0){
int k = i + H[i];
if (i >= 0 && k < n && j < k && H[k] == k - j) ct3(i,j,k);
}
}
if (true){
int k = j + H[j];
if (k < n){
int i = j - H[k];
if (i >= 0 && k < n && H[i] == k - i) ct3(i,j,k);
}
}
if (true){
int k = j + H[j];
if (k < n){
int i = k - H[k];
if (i >= 0 && k < n && i < j && H[i] == j - i) ct3(i,j,k);
}
}
int pick = j + H[j];
int p = upper_bound(f[pick].begin(), f[pick].end(), j) - f[pick].begin();
for (int ik = p; ik < f[pick].size(); ik++){
int k = f[pick][ik];
assert(k > j); // H[k - H[j]] + H[k] == H[j]
if (k - H[j] >= 0 && k - H[j] < j && H[k - H[j]] == k - j){
ct3(k - H[j], j, k);
}
}
// for (int k = j + 1; k < n; k++){
// int i = k - H[j];
// if (i >= j) break;
// if (i >= 0 && i < j && ((H[i] == j - i && H[k] == k - j) || (H[i] == k - j && H[k] == j - i))) qut++;
// }
}
for (int i = 0; i < n; i++){
int j = i + H[i];
if (j < n){
int k = i + H[j];
if (k < n && j < k && H[k] == k - j) ct3(i,j,k);
}
}
return (int)mps.size() + qut;
}
vector<int> construct_range(int M, int K){
vector <int> res;
for (int i = 1; i < M; i++) res.push_back(M - i);
res.push_back(1);
return res;
};
#endif // TRIPLES_H
