#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
long long count_triples(std::vector<int> h) {
int n = h.size();
long long res = 0;
bool nonDec = true;
for (int i = 0; i < n-1; i++) nonDec &= h[i] <= h[i+1];
if (nonDec) {
for (int i = 0; i < n; i++) {
bool already = false;
if (h[i]+i < n && h[i]+i-h[h[i]+i] >= 0 && h[i]+i-h[h[i]+i] < i) {
vector<int> a = {h[i], h[h[i]+i], h[h[i]+i-h[h[i]+i]]};
vector<int> b = {h[i], h[h[i]+i]-h[i], h[h[i]+i]};
sort(a.begin(), a.end());
sort(b.begin(), b.end());
if (a == b) {
already = true;
res++;
}
}
if (i-h[i] >= 0 && i+h[i-h[i]] < n && i+h[i-h[i]] > i) {
vector<int> a = {h[i], h[i+h[i-h[i]]], h[i-h[i]]};
vector<int> b = {h[i], h[i-h[i]], h[i]+h[i-h[i]]};
sort(a.begin(), a.end());
sort(b.begin(), b.end());
if (a == b && (!already || h[i]+i-h[h[i]+i] != i-h[i] || i+h[i-h[i]] != h[i]+i)) res++;
}
}
} else if (n <= 2000) {
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (h[i]+j < n) {
vector<int> a = {h[i], h[j], h[h[i]+j]};
vector<int> b = {j-i, h[i], h[i]+j-i};
sort(a.begin(), a.end());
sort(b.begin(), b.end());
if (a == b) res++;
}
if (h[j]+j < n && h[i] != h[j]) {
vector<int> a = {h[i], h[j], h[h[j]+j]};
vector<int> b = {j-i, h[j], h[j]+j-i};
sort(a.begin(), a.end());
sort(b.begin(), b.end());
if (a == b) res++;
}
if (abs(h[i]-h[j])+j < n && h[i] != abs(h[i]-h[j]) && h[j] != abs(h[i]-h[j])) {
vector<int> a = {h[i], h[j], h[abs(h[i]-h[j])+j]};
vector<int> b = {j-i, abs(h[i]-h[j]), abs(h[i]-h[j])+j-i};
sort(a.begin(), a.end());
sort(b.begin(), b.end());
if (a == b) res++;
}
}
}
} else {
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n && j < i+20; j++) {
if (h[i]+j < n) {
vector<int> a = {h[i], h[j], h[h[i]+j]};
vector<int> b = {j-i, h[i], h[i]+j-i};
sort(a.begin(), a.end());
sort(b.begin(), b.end());
if (a == b) res++;
}
if (h[j]+j < n && h[i] != h[j]) {
vector<int> a = {h[i], h[j], h[h[j]+j]};
vector<int> b = {j-i, h[j], h[j]+j-i};
sort(a.begin(), a.end());
sort(b.begin(), b.end());
if (a == b) res++;
}
if (abs(h[i]-h[j])+j < n && h[i] != abs(h[i]-h[j]) && h[j] != abs(h[i]-h[j])) {
vector<int> a = {h[i], h[j], h[abs(h[i]-h[j])+j]};
vector<int> b = {j-i, abs(h[i]-h[j]), abs(h[i]-h[j])+j-i};
sort(a.begin(), a.end());
sort(b.begin(), b.end());
if (a == b) res++;
}
}
}
}
return res;
}
std::vector<int> construct_range(int M, int K) {
vector<int> ans(M);
for (int i = 0; i < M; i++) {
if (i % 3 <= 1) ans[i] = 1;
else ans[i] = 2;
}
return ans;
}
