#include "doll.h"
#include <algorithm>
#include <vector>
#include <cassert>
#include <iostream>
using namespace std;
vector<int> seqVoulue;
vector<vector<int>> sortiesVoulues;
vector<int> dirSort;
vector<int> sw1, sw2;
int lenSeq;
int nbTriggers;
int nbSwitchs = 0;
int newSwitch()
{
++nbSwitchs;
sw1.push_back(0);
sw2.push_back(0);
return nbSwitchs;
}
void repartir(int switchId, vector<int> sortiesOrd)
{
int sz = sortiesOrd.size();
int IND = switchId-1;
if (true) {
assert(sz % 2 == 0 && sz >= 2);
vector<vector<int>> subSor(2);
for (int i = 0; i < sz/2; ++i) {
subSor[0].push_back(sortiesOrd[i]);
subSor[1].push_back(sortiesOrd[i + sz/2]);
}
sw1[IND] = subSor[0].front();
for (int x : subSor[0]) if (x != sw1[IND]) {
sw1[IND] = -newSwitch();
break;
}
sw2[IND] = subSor[1].front();
for (int x : subSor[1]) if (x != sw2[IND]) {
sw2[IND] = -newSwitch();
break;
}
if (sw1[IND] < -1) repartir(-sw1[IND], subSor[0]);
if (sw2[IND] < -1) repartir(-sw2[IND], subSor[1]);
}
}
void create_circuit(int M, std::vector<int> A) {
nbTriggers = M;
seqVoulue = A;
lenSeq = seqVoulue.size();
sortiesVoulues.resize(nbTriggers + 1);
dirSort.resize(nbTriggers + 1);
sortiesVoulues[0].push_back(seqVoulue.front());
int mainSwitch = newSwitch();
for (int pos = 0; pos < lenSeq; ++pos) {
int cur = seqVoulue[pos];
int suiv = 0;
if (pos + 1 < lenSeq) {
suiv = seqVoulue[pos+1];
}
sortiesVoulues[cur].push_back(suiv);
}
vector<int> mainSorties;
for (int pos = 0; pos < lenSeq; ++pos) {
int cur = seqVoulue[pos];
int suiv = 0;
if (pos + 1 < lenSeq) {
suiv = seqVoulue[pos+1];
}
int szVoulu = sortiesVoulues[cur].size();
if (szVoulu > 1) {
mainSorties.push_back(suiv);
dirSort[cur] = -mainSwitch;
} else {
dirSort[cur] = suiv;
}
}
int sz = mainSorties.size();
int bb = 0;
int x = 1;
while (x < sz) { x *= 2; ++bb; }
int theSkips = x-sz;
sz = x;
vector<int> rl(sz, -1);
int curPris = 0;
for (int tpsVisite = 0; tpsVisite < sz; ++tpsVisite) {
vector<int> tb(bb, 0);
for (int iBit = 0; iBit < bb; ++iBit) {
if ((1 << iBit) & tpsVisite) tb[iBit] = 1;
}
int vraiePos = 0;
for (int w : tb) {
vraiePos *= 2;
vraiePos += w;
}
if (vraiePos >= theSkips) {
rl[vraiePos] = mainSorties[curPris++];
}
}
dirSort[0] = seqVoulue.front();
repartir(mainSwitch, rl);
answer(dirSort, sw1, sw2);
}
