#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/extc++.h>
#include "triples.h"
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
mt19937_64 rd(time(0));
ll Hash1[200005];
ll Hash2[200005];
vector<int> construct_range(int M, int K) {
M /= 6;
M *= 6;
vector<int> ans;
for (int i = 0; i < M; i += 6) {
for (int j:{3, 4, 2, 1, 1, 3}) ans.push_back(j);
}
return ans;
}
gp_hash_table<ll, bool> all;
vector<int> H;
void check(int a, int b, int c) {
if (c < 0 or c >= H.size()) return;
if (a == b or a == c or b == c) return;
array<int, 3> h = {H[a], H[b], H[c]};
array<int, 3> diff = {abs(a-b), abs(a-c), abs(b-c)};
sort(h.begin(), h.end());
sort(diff.begin(), diff.end());
if (h == diff) {
all[Hash1[a]^Hash1[b]^Hash1[c]] = 1;
}
}
vector<int> adj[400005];
gp_hash_table<int, __gnu_pbds::null_type> big[400005];
int from[400005];
gp_hash_table<int, int> bruh[400005];
vector<int> cc;
ll triangles() {
int N = cc.size();
vector<int> order;
for (int i = 0; i < N; i ++) order.push_back(i);
sort(order.begin(), order.end(), [](const int a, const int b) {
return adj[a].size() < adj[b].size();
});
for (int i = 0; i < N; i ++) for (int j:adj[i]) if (make_pair(i, adj[i].size()) < make_pair(j, adj[j].size())) {
big[i].insert(j);
}
ll num = 0;
for (int ii = 0; ii < N; ii ++) {
int i = order[ii];
for (int j:big[i]) {
for (int k:big[j]) if (big[i].find(k) != big[i].end()) {
// cout << i << " " << j << " " << k << "\n";
// cout << bruh[i][j] << " " << bruh[i][k] << " " << bruh[j][k] << "\n";
check(bruh[i][j], bruh[i][k], bruh[j][k]);
num ++;
}
}
}
return num;
}
ll count_triples(vector<int> h) {
::H = h;
int N = H.size();
for (int i = 0; i < N; i ++) Hash1[i] = rd(), Hash2[i] = rd();
for (int i = 0; i < N; i ++) {
// Normal case:
// Edge with length H[i] connects from i
int p1 = i, p2 = i - H[i];
if (p2 >= 0) {
check(p1, p2, p1 - H[p2]);
check(p1, p2, p1 + H[p2]);
check(p1, p2, p2 - H[p2]);
check(p1, p2, p2 + H[p2]);
}
p1 = i, p2 = i + H[i];
if (p2 < N) {
check(p1, p2, p1 - H[p2]);
check(p1, p2, p1 + H[p2]);
check(p1, p2, p2 - H[p2]);
check(p1, p2, p2 + H[p2]);
}
}
// count triangles in a graph
for (int i = 0; i < N; i ++) {
cc.push_back(i - H[i]);
cc.push_back(i + H[i]);
}
sort(cc.begin(), cc.end());
cc.resize(unique(cc.begin(), cc.end()) - cc.begin());
for (int i = 0; i < N; i ++) {
int a = lower_bound(cc.begin(), cc.end(), i - H[i]) - cc.begin();
int b = lower_bound(cc.begin(), cc.end(), i + H[i]) - cc.begin();
bruh[a][b] = bruh[b][a] = i;
adj[a].push_back(b);
adj[b].push_back(a);
}
triangles();
return (ll)all.size();
}
