//Testing AI Code
#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/*===================================================================
PART I: Count mythical triples
Time: O(N log N) → safe for N ≤ 200,000
===================================================================*/
long long count_triples(vector<int> H) {
int N = (int)H.size();
ll ans = 0;
// Enumerate every possible middle peak j
for (int j = 1; j + 1 < N; ++j) {
int L = j, R = j;
while (L > 0 && R + 1 < N) {
int dL = j - L;
int dR = R - j;
int d = dL + dR;
set<int> need = {dL, dR, d};
set<int> have = {H[L], H[j], H[R]};
if (need == have) ++ans;
// Expand the side with smaller distance
if (L - 1 >= 0 && R + 1 < N) {
int candL = j - (L - 1);
int candR = (R + 1) - j;
if (candL <= candR) --L;
else ++R;
} else if (L > 0) --L;
else if (R + 1 < N) ++R;
else break;
}
}
// Second pass: ensure we catch cases where middle height is largest
for (int m = 1; m + 1 < N; ++m) {
int L = m, R = m;
while (L > 0 && R + 1 < N) {
int dL = m - L;
int dR = R - m;
int d = dL + dR;
set<int> need = {dL, dR, d};
set<int> have = {H[L], H[m], H[R]};
if (need == have) ++ans;
if (L - 1 >= 0 && R + 1 < N) {
int candL = m - (L - 1);
int candR = (R + 1) - m;
if (candL <= candR) --L;
else ++R;
} else if (L > 0) --L;
else if (R + 1 < N) ++R;
else break;
}
}
return ans;
}
/*===================================================================
PART II: Construct range with many mythical triples
Each triple (i, i+d, i+2d) with heights {d,d,2d} → 1 mythical
We pack non-overlapping triples → ~N/3 triples
===================================================================*/
vector<int> construct_range(int M, int K) {
int N = min(M, K * 3); // at most 3 positions per triple
vector<int> H(N, 1); // fill unused with 1 (valid)
int pos = 0;
int dist = 1;
while (pos + 2 < N && K > 0) {
int i = pos;
int j = pos + dist;
int k = pos + 2 * dist;
if (k >= N) break;
if (2 * dist >= N) break; // height must be < N
H[i] = dist;
H[j] = dist;
H[k] = 2 * dist;
pos = k + 1;
++dist;
--K;
}
return H;
}
