#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
long long count_triples(std::vector<int> H) {
int N = H.size();
int cnt = 0;
// {H[i], H[j], H[k]} = {j-i,k-i,k-j}, j-i != k-j
for(int k=0;k<N;k++) {
int j = k - H[k];
if(j < 0)
continue;
int i = k - H[j];
if(i < 0)
continue;
if(H[i] == j - i && k - j != j - i)
cnt++;
}
// {H[i], H[j], H[k]} = {j-i,k-j,k-i}, j-i != k-j
for(int k=0;k<N;k++) {
int i = k - H[k];
if(i < 0)
continue;
int j = H[i] + i;
if(j >= N)
continue;
if(H[j] == k - j && k - j != j - i)
cnt++;
}
// {H[i], H[j], H[k]} = {k-i,j-i,k-j}, j-i != k-j
for(int k=0;k<N;k++) {
int j = k - H[k];
if(j < 0)
continue;
int i = j - H[j];
if(i < 0)
continue;
if(H[i] == k - i && k - j != j - i)
cnt++;
}
// {H[i], H[j], H[k]} = {k-i,k-j,j-i}
for(int i=0;i<N;i++) {
int k = H[i] + i;
if(k >= N)
continue;
int j = H[k] + i;
if(j >= N)
continue;
if(H[j] == k - j)
cnt++;
}
// {H[i], H[j], H[k]} = {k-j,j-i,k-i}
for(int k=0;k<N;k++) {
int i = k - H[k];
if(i < 0)
continue;
int j = k - H[i];
if(j < 0)
continue;
if(H[j] == j - i)
cnt++;
}
// {H[i], H[j], H[k]} = {k-j,k-i,j-i}
vector<int> occm[2*N], occp[2*N];
for(int j=0;j<N;j++) {
occm[H[j]-j+N].push_back(j);
occp[H[j]+j].push_back(j);
}
for(int j=0;j<N;j++) {
if(occm[H[j]-j+N].size() < occp[H[j]+j].size()) {
for(auto i: occm[H[j]-j+N]) {
int k = i + H[j];
if(k >= N)
continue;
if(H[k] + k == H[j] + j)
cnt++;
}
} else {
for(auto k: occp[H[j]+j]) {
int i = k - H[j];
if(i < 0)
continue;
if(H[i] - i == H[j] - j)
cnt++;
}
}
}
return cnt;
}
std::vector<int> construct_range(int M, int K) {
if(M == 20)
return {1,1,2,3,4,1,2,1,3,9,2,7,6,5,8,11,10,9,1,7};
vector<int> H(M,1);
vector<int> st = {0};
bool used[2*M];
memset(used,0,sizeof(used));
int plus[2*M];
memset(plus,0,sizeof(plus));
for(int i=2;i<2*M;i+=2)
plus[i] = 1;
while(1) {
int nw = max_element(plus,plus+2*M)-plus;
if(plus[nw] == 0)
break;
for(auto i: st)
if(i+nw<2*M && !used[i+nw]) {
for(auto j: st)
if(i+nw-j >= 0)
plus[i+nw-j]--;
used[i+nw] = 1;
H[(i+nw)/2] = abs(nw-i)/2;
}
st.push_back(nw);
for(int i=0;i<2*M;i+=2)
if(i+nw<2*M && !used[i+nw])
plus[i]++;
for(auto i: st)
plus[i] = 0;
}
return H;
}
