#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
unordered_set<int> sum_ct[400001];
unordered_set<int> dif_ct[400001];
long long count_triples(vector<int> v) {
int n = v.size();
auto is_in_range = [&](int x) {
return (0 <= x && x < n);
};
auto try_bound = [&](int l, int r) {
int x = min(v[l], v[r]);
assert(x < r-l);
int g = max(v[l], v[r]) - min(v[l], v[r]);
int ans = 0;
if(v[l+x] == g) ans++;
if(v[r-x] == g) ans++;
if(l+x == r-x && ans == 2) ans--;
return ans;
};
ll tot = 0;
// peak on the left or right
for(int i = 0; i < n; i++) {
if(is_in_range(i + v[i]) && v[i+v[i]] < v[i]) {
tot += try_bound(i, i+v[i]);
}
if(is_in_range(i - v[i]) && v[i-v[i]] < v[i]) {
tot += try_bound(i-v[i], i);
}
}
// peak on the middle, 2-5--3
for(int i = 0; i < n; i++) {
if(is_in_range(i + v[i]) && is_in_range(i + v[i + v[i]])) {
// probably remove overcounts
if(v[i] + v[i + v[i + v[i]]] == v[i + v[i]] && v[i] != v[i + v[i + v[i]]]) tot++;
}
}
// cout << "So far tot is " << tot << endl;
// peak on the middle, 3-5--2
for(int i = 0; i < 2 * n; i++) {
sum_ct[i].clear();
dif_ct[i].clear();
}
for(int i = 0; i < n; i++) {
sum_ct[i + v[i]].insert(v[i]);
dif_ct[i - v[i] + n].insert(v[i]);
}
for(int i = 0; i < n; i++) {
if(sum_ct[i + v[i]].size() < dif_ct[i - v[i] + n].size()) {
for(int g : sum_ct[i + v[i]]) {
if(dif_ct[i - v[i] + n].count(v[i] - g)) tot++;
}
}
else {
for(int g : dif_ct[i - v[i] + n]) {
if(sum_ct[i + v[i]].count(v[i] - g)) tot++;
}
}
}
/*
for(int i = 0; i < n; i++) {
for(int j = i-1; j >= 0; j--) {
if(v[j] < v[i] && is_in_range(j + v[i]) && v[j] + v[j + v[i]] == v[i] && v[j + v[i]] == i - j) tot++;
}
}
*/
return tot;
}
vector<int> construct_range(int n, int k) {
vector<int> v(n);
for(int i = 0; i < n; i++) {
v[i] = (i % 3 ? 1 : 0) + 1;
}
return v;
}
