#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef vector<int> Vi;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;
#define forR(i, n) for (int i = 0; i < (n); i++)
void answer(Vi C, Vi X, Vi Y);
Vi C, X, Y;
Vi swState;
int getLevelSW(int sz) {
int level = 1, maxSz = 2;
while (sz > maxSz) {
level++, maxSz *= 2;
}
return level;
}
int getSW(int root = 0) {
int swNo = -1 - X.size();
X.push_back(root); Y.push_back(root); swState.push_back(0);
return swNo;
}
void setSWX(int sw, int t) {
X[-1 - sw] = t;
}
void setSWY(int sw, int t) {
Y[-1 - sw] = t;
}
int getStateSW(int sw) {
int state = swState[sw];
swState[sw] = 1 - state;
return state;
}
int& goAlong(int node, int step) {
int* nodePtr = NULL;
for (int i = 0; i < step; i++) {
assert(node < 0);
int sw = -1 - node;
if (getStateSW(sw) == 0) {
nodePtr = &X[sw];
} else {
nodePtr = &Y[sw];
}
node = *nodePtr;
}
return *nodePtr;
}
int buildLevelSW(int lvl, const Vi& nexts) {
int root = getSW();
Vi sws(1, root);
for (int i = 1; i < lvl; i++) {
Vi sw_lvl;
for (int sw : sws) {
int sw0 = getSW(root), sw1 = getSW(root);
sw_lvl.push_back(sw0);
sw_lvl.push_back(sw1);
setSWX(sw, sw0);
setSWY(sw, sw1);
}
sws = sw_lvl;
}
forR(i, ((1 << lvl) - nexts.size())) {
goAlong(root, lvl) = root;
}
for (int next : nexts) {
goAlong(root, lvl) = next;
}
return root;
}
void build_answer(int node, const Vi& nexts) {
if (nexts.size() == 0) {
C[node] = 0;
return;
} else if (nexts.size() == 1) {
C[node] = nexts[0];
return;
}
int lvlSW = getLevelSW(nexts.size());
int numSW = (1 << lvlSW) - 1;
int root = buildLevelSW(lvlSW, nexts);
C[node] = root;
}
void create_circuit(int M, Vi A) {
int n = A.size();
X = Y = swState = Vi();
C = Vi(n + 1);
C[0] = A[0];
Vii nexts(M + 1);
A.push_back(0);
forR(i, n) {
nexts[A[i]].push_back(A[i + 1]);
}
forR(i, M) {
build_answer(i + 1, nexts[i + 1]);
}
answer(C, X, Y);
}
#ifdef TEST_LOCAL
void answer(Vi C, Vi X, Vi Y) {
}
int main() {
create_circuit(4, Vi{ 1, 2, 1, 2,2,0 });
return 0;
}
#endif
