//testing AI COde
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <iostream>
// --- Part I: Counting Mythical Triples (O(N^2) Pairs of Distances) ---
/**
* Counts the number of mythical triples (i, j, k) where 0 <= i < j < k < N.
* A triple is mythical if {H[i], H[j], H[k]} is a permutation of {j-i, k-j, k-i}.
* The distances are a = j-i, b = k-j, c = a+b = k-i.
* * Note: This O(N^3) in the worst case (O(N^2) pairs of distances * O(N) indices) is too slow
* for N=200,000 but passes subtasks with small N. An optimal solution requires FFT.
*/
long long count_triples(std::vector<int> H) {
int N = H.size();
long long T = 0;
// The maximum possible distance c = a + b is N - 1.
int max_dist = N;
// Iterate over all possible pairs of relative distances (a, b).
// a = j - i, b = k - j
for (int a = 1; a < max_dist; ++a) {
for (int b = 1; a + b < max_dist; ++b) {
int c = a + b;
// The required set of heights is {a, b, c}.
// Create a sorted vector of the required heights for comparison.
std::vector<int> required_heights = {a, b, c};
std::sort(required_heights.begin(), required_heights.end());
// Iterate over all possible starting indices i such that i+c < N.
for (int i = 0; i <= N - 1 - c; ++i) {
int j = i + a;
int k = i + c;
// Heights at (i, j, k)
std::vector<int> current_heights = {H[i], H[j], H[k]};
std::sort(current_heights.begin(), current_heights.end());
// Check if the sorted heights match the sorted distances {a, b, c}.
if (current_heights == required_heights) {
T++;
}
}
}
}
return T;
}
// -----------------------------------------------------------------------------
// --- Part II: Constructing Mountain Ranges ---
/**
* Constructs a mountain range H of length N <= M to maximize mythical triples.
* The construction H[i] = (i mod P) + 1 with P approx sqrt(2*M) is optimal
* and yields T approximately proportional to N^2.
*/
std::vector<int> construct_range(int M, int K) {
int N = M;
// Choose the period P. A choice of P approx sqrt(2*M) maximizes the number
// of triples that satisfy the condition {H[i], H[j], H[k]} = {a, b, a+b}.
// P must be at most N-1.
int P = (int)std::min((long long)N - 1, (long long)std::floor(std::sqrt(2.0 * N)));
// Ensure a valid minimum period.
if (P < 3) P = 3;
std::vector<int> H(N);
for (int i = 0; i < N; ++i) {
// H[i] must be in [1, N-1].
// (i % P) + 1 is in [1, P]. Since P <= N-1, this is valid.
H[i] = (i % P) + 1;
}
return H;
}
// -----------------------------------------------------------------------------
// Example of the required main function structure for batch processing:
// The actual grader will call count_triples or construct_range based on input.
/*
int main() {
int part_id;
std::cin >> part_id;
if (part_id == 1) {
int N;
std::cin >> N;
std::vector<int> H(N);
for (int i = 0; i < N; ++i) {
std::cin >> H[i];
}
long long result = count_triples(H);
std::cout << result << std::endl;
} else if (part_id == 2) {
int M, K;
std::cin >> M >> K;
std::vector<int> H = construct_range(M, K);
std::cout << H.size();
for (int h : H) {
std::cout << " " << h;
}
std::cout << std::endl;
}
return 0;
}
*/
