/* discussed with lunchbox */
#include "triples.h"
#include <cstdlib>
#include <iostream>
using namespace std;
typedef vector<int> vi;
const int N = 200000;
int *ej[N * 3], eo[N * 3];
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
char used[N * 3];
long long count_triangles(vi aa, int n) {
for (int i = 0; i < n * 3; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
for (int i = 0; i < n; i++) {
int l = n + i - aa[i], r = n + i + aa[i];
append(l, r), append(r, l);
}
long long ans = 0;
for (int i = 0; i < n * 3; i++) {
for (int oi = eo[i]; oi--; ) {
int j = ej[i][oi];
used[j] = 1;
}
for (int oi = eo[i]; oi--; ) {
int j = ej[i][oi];
if (eo[i] > eo[j] || eo[i] == eo[j] && i < j)
for (int oj = eo[j]; oj--; ) {
int k = ej[j][oj];
if (used[k])
ans++;
}
}
for (int oi = eo[i]; oi--; ) {
int j = ej[i][oi];
used[j] = 0;
}
}
for (int i = 0; i < n * 3; i++)
free(ej[i]);
return ans / 3;
}
long long count_triples(vi aa) {
int n = aa.size();
long long ans = 0;
for (int i = 0; i < n; i++) {
int j, k = i + aa[i];
if (k < n && aa[k] < aa[i]) {
j = k - aa[k];
if (j > i && aa[j] == j - i)
ans++;
if (aa[k] * 2 != aa[i]) {
j = i + aa[k];
if (j < k && aa[j] == k - j)
ans++;
}
}
}
for (int k = 0; k < n; k++) {
int i = k - aa[k], j;
if (i >= 0 && aa[i] < aa[k]) {
j = i + aa[i];
if (j < k && aa[j] == k - j)
ans++;
if (aa[i] * 2 != aa[k]) {
j = k - aa[i];
if (j > i && aa[j] == j - i)
ans++;
}
}
}
for (int i = 0; i < n; i++) {
int j = i + aa[i];
if (j < n && aa[j] > aa[i] && aa[j] != aa[i] * 2) {
int k = i + aa[j];
if (k < n && aa[k] == k - j)
ans++;
}
}
ans += count_triangles(aa, n);
return ans;
}
vi construct_range(int M, int K) {
return {1, 1, 1};
}
