#include <bits/stdc++.h>
#include "triples.h"
using namespace std;
typedef long long ll;
bool check_triple(vector <int> a, vector <int> b){
sort(a.begin(), a.end());
sort(b.begin(), b.end());
if (a[0] != b[0] || a[1] != b[1] || a[2] != b[2])return 0;
return 1;
}
void find_triples(vector <tuple<int, int, int>> &triples, ll n, vector <int> &H, int i, int j){
for (int x : {i, j}){
for (int y : {-H[j], H[j]}){
int z = x+y;
if (z < 0 || z >= n || z == i || z == j)continue;
if (check_triple({abs(i-j), abs(i-z), abs(j-z)}, {H[i], H[j], H[z]})){
vector <int> v = {i, j, z};
sort(v.begin(), v.end());
triples.push_back({v[0], v[1], v[2]});
}
}
}
}
/*bool cmp_triple(tuple <int, int, int> a, tuple <int, int, int> b){
if (get<0>(a) == get<0>(b)){
if (get<1>(a) == get<1>(b))return (get<2>(a) < get<2>(b));
return (get<1>(a) < get<1>(b));
}
return (get<0>(a) < get<0>(b));
}*/
long long count_triples(std::vector<int> H) {
ll n = H.size();
vector <tuple <int, int, int>> triples;
for (int i = 0; i < n; i++){
if (i-H[i] >= 0)find_triples(triples, n, H, i, i-H[i]);
if (i+H[i] < n)find_triples(triples, n, H, i, i+H[i]);
}
sort(triples.begin(), triples.end());
ll count = 0;
if (!triples.empty()){
//cerr << get<0>(triples[0]) << " " << get<1>(triples[0]) << " " << get<2>(triples[0]) << "\n";
count++;
}
for (int i = 1; i < triples.size(); i++){
if (triples[i] != triples[i-1]){
count++;
//cerr << get<0>(triples[i]) << " " << get<1>(triples[i]) << " " << get<2>(triples[i]) << "\n";
}
}
vector <pair <ll, ll>> h(n);
for (int i = 0; i < n; i++)h[i] = {H[i], i};
sort(h.begin(), h.end());
reverse(h.begin(), h.end());
ll cur = -1;
for (int i = 0; i < n; i++){
while (cur < n-1 && h[cur+1].first > 2*h[i].first)cur++;
}
return count;
}
std::vector<int> construct_range(int M, int K) {
ll n = M;
vector <int> v(n);
for (int i = 0; i < n/2; i++)v[i] = i+1;
for (int i = n/2; i < n-1; i++)v[i] = n-i-1;
v[n-1] = 1;
return v;
}
