//Challenge: Accepted
#include "triples.h"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
#define iter(v) v.begin(),v.end()
#define SZ(v) (int)v.size()
#define pb emplace_back
long long count_triples(std::vector<int> h) {
int n = h.size();
//first case: max at left or right
//
auto check_triple = [&] (int i, int j, int k) {
if (i < 0 || i >= n || j < 0 || j >= n || k < 0 || k >= n) return false;
int a[3] = {abs(j - i), abs(k - j), abs(k - i)};
int b[3] = {h[i], h[j], h[k]};
sort(a, a + 3);
sort(b, b + 3);
return (a[0] == b[0]) && (a[1] == b[1]) && (a[2] == b[2]);
};
ll count1 = 0;
for (int i = 0;i < n;i++) {
if (i + h[i] < n) {
int j = i+h[i];
if (h[j] < h[i]) {
count1 += check_triple(i, j, j - h[j]);
if (j - h[j] != i + h[j]) count1 += check_triple(i, j, i + h[j]);
}
}
if (i - h[i] >= 0) {
int j = i - h[i];
if (h[j] < h[i]) {
count1 += check_triple(i, j, j + h[j]);
if (j + h[j] != i - h[j]) count1 += check_triple(i, j, i - h[j]);
}
}
}
return count1;
}
std::vector<int> construct_range(int M, int K) {
return {1, 1, 1};
}
