#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
class CircuitBuilder {
public:
void build(int M, vector<int> A) {
N = A.size();
this->A = A;
C_ans.assign(M + 1, 0);
X_ans.clear();
Y_ans.clear();
switch_counter = 0;
if (N == 0) {
answer(C_ans, X_ans, Y_ans);
return;
}
create_main_path();
create_trigger_exits(M);
answer(C_ans, X_ans, Y_ans);
}
private:
int N;
vector<int> A;
vector<int> C_ans;
vector<int> X_ans;
vector<int> Y_ans;
int switch_counter;
vector<int> main_path_switches;
int new_switch() {
X_ans.push_back(0);
Y_ans.push_back(0);
return -(++switch_counter);
}
void create_main_path() {
main_path_switches.resize(N);
for (int i = 0; i < N; ++i) {
main_path_switches[i] = new_switch();
}
C_ans[0] = main_path_switches[0];
for (int i = 0; i < N; ++i) {
int idx = -main_path_switches[i] - 1;
assert(idx >= 0 && idx < (int)X_ans.size());
X_ans.at(idx) = A[i];
Y_ans.at(idx) = (i < N - 1) ? main_path_switches[i + 1] : 0;
}
}
void create_trigger_exits(int M) {
map<int, vector<int>> occs;
for (int i = 0; i < N; ++i) {
occs[A[i]].push_back(i);
}
for (int i = 1; i <= M; ++i) {
if (occs.find(i) == occs.end()) {
C_ans[i] = 0;
continue;
}
const auto& positions = occs.at(i);
vector<int> dests;
dests.reserve(positions.size());
for (int pos : positions) {
dests.push_back(main_path_switches[pos]);
}
vector<int> permuted_dests = get_permuted_destinations(dests);
C_ans[i] = build_selector_tree(permuted_dests);
}
}
vector<int> get_permuted_destinations(const vector<int>& dests) {
vector<int> indices(dests.size());
iota(indices.begin(), indices.end(), 0);
auto perm_indices = generate_permutation_map(indices);
vector<int> permuted_dests(dests.size());
for (size_t j = 0; j < dests.size(); ++j) {
permuted_dests[j] = dests[perm_indices[j]];
}
return permuted_dests;
}
vector<int> generate_permutation_map(const vector<int>& indices) {
if (indices.size() <= 1) {
return indices;
}
size_t k = indices.size();
size_t m = 1;
while (m * 2 < k) {
m *= 2;
}
vector<int> left(indices.begin(), indices.begin() + m);
vector<int> right(indices.begin() + m, indices.end());
auto perm_left = generate_permutation_map(left);
auto perm_right = generate_permutation_map(right);
vector<int> res;
res.reserve(k);
size_t l_ptr = 0, r_ptr = 0;
while (l_ptr < perm_left.size() || r_ptr < perm_right.size()) {
if (l_ptr < perm_left.size()) res.push_back(perm_left[l_ptr++]);
if (r_ptr < perm_right.size()) res.push_back(perm_right[r_ptr++]);
}
return res;
}
int build_selector_tree(const vector<int>& dests) {
if (dests.empty()) return 0;
if (dests.size() == 1) return dests[0];
size_t k = dests.size();
size_t m = 1;
while (m * 2 <= k) {
m *= 2;
}
vector<int> left_dests, right_dests;
for (size_t i = 0; i < dests.size(); ++i) {
if (i % 2 == 0) left_dests.push_back(dests[i]);
else right_dests.push_back(dests[i]);
}
int root = new_switch();
X_ans[-root - 1] = build_selector_tree(left_dests);
Y_ans[-root - 1] = build_selector_tree(right_dests);
return root;
}
};
void create_circuit(int M, vector<int> A) {
CircuitBuilder builder;
builder.build(M, A);
}
