#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int N;
vector<int> H;
vector<vector<int>> F(0);
bool _L (vector<int> a, vector<int> b){
for (int i = 0; i < 3; i++){
if (a[i] != b[i]) return a[i] < b[i];
}
return false;
};
bool _E (vector<int> a, vector<int> b){
for (int i = 0; i < 3; i++) if (a[i] != b[i]) return false;
return true;
}
vector<int> _MK (int a, int b, int c){
vector<int> o = {a, b, c};
sort(o.begin(), o.end());
return o;
}
void _CH (vector<int> a){
auto p = _MK (abs(a[0] - a[1]), abs(a[1] - a[2]), abs(a[0] - a[2]));
for (int i = 0; i < 3; i++) if (a[i] < 0 || a[i] >= N) return;
auto q = _MK (H[a[0]], H[a[1]], H[a[2]]);
if (_E(p, q)) F.push_back(a);
}
long long count_triples(std::vector<int> h) {
N = h.size();
H = h;
bool st = true;
for (int i = 0; i < N-1; i++) {
if (H[i+1] < H[i]) st = false;
}
for (int i = 0; i < N; i++) {
// forward
int p = i + H[i];
if (p < N) {
_CH(_MK(i, p, p+H[p]));
_CH(_MK(i, p, p-H[p]));
_CH(_MK(i, p, i+H[p]));
_CH(_MK(i, p, i-H[p]));
}
// backward
p = i - H[i];
if (p >= 0) {
_CH(_MK(i, p, p+H[p]));
_CH(_MK(i, p, p-H[p]));
_CH(_MK(i, p, i+H[p]));
_CH(_MK(i, p, i-H[p]));
}
if (st) continue;
for (int j = i - H[i] + 1; j < i; j++){
_CH({j, i, j + H[i]});
}
}
// make return
sort(F.begin(), F.end(), _L);
int out= F.size();
for (int i = 1; i < F.size(); i++) {
if (_E(F[i], F[i-1])) out--;
}
return out;
}
std::vector<int> construct_range(int M, int K) {
vector<int> out;
vector<int> cur = {1,2,1,3};
for (int i =0 ; i < M; i++){
out.push_back(cur[i%4]);
}
return out;
}
