#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> X, Y, C;
struct trigger {
int id;
int type;
trigger() {}
trigger(int typ) {
if (typ != 0) {
id = typ;
type = 1;
} else {
id = X.size();
X.push_back(0);
Y.push_back(0);
type = 0;
}
}
void connect_parent(int par) {
C[par] = -id;
}
void connect_X(trigger x) {
if (x.type == 0)
X[id - 1] = -x.id;
else
X[id - 1] = x.id;
}
void connect_Y(trigger y) {
if (y.type == 0)
Y[id - 1] = -y.id;
else
Y[id - 1] = y.id;
}
};
void set_idxs(int curr, int idx, int depth, int max_node, trigger node, vector<trigger> &targets) {
if (curr * 2 >= max_node) {
int xi = idx, yi = idx + (1 << depth);
node.connect_X(trigger(targets[xi]));
node.connect_Y(trigger(targets[yi]));
return;
}
trigger xnode(0);
trigger ynode(0);
set_idxs(curr*2, idx, depth + 1, max_node, xnode, targets);
set_idxs(curr*2+1, idx + (1 << depth), depth + 1, max_node, ynode, targets);
node.connect_X(xnode);
node.connect_Y(ynode);
}
void create_device(int node, vector<trigger> targets) {
int siz = 2, needed = 2;
while (siz < targets.size())
siz *= 2, needed += siz;
trigger root(0); root.connect_parent(node);
while (targets.size() < siz)
{
targets.push_back(root);
swap(targets[targets.size() - 1], targets[targets.size() - 2]);
}
set_idxs(1, 0, 0, siz, root, targets);
}
void create_circuit(int M, std::vector<int> A) {
int N = A.size();
C.resize(M+1);
C[0] = A[0];
vector<vector<trigger> > targets(M+1);
for (int i = 0; i < N; i++) {
int next = i == N - 1 ? 0 : A[i + 1];
targets[A[i]].push_back(trigger(next));
}
for (int i = 1; i <= M; i++)
{
if (!targets[i].empty())
create_device(i, targets[i]);
}
X.pop_back();
Y.pop_back();
answer(C, X, Y);
}
