#include <bits/stdc++.h>
#include "doll.h"
#define ll long long
#define pb push_back
#define ff first
#define ss second
using namespace std;
int n;
int currentSwitch = 1;
vector<int>goes[100002];
vector<int>c, x, y;
vector<ll>potencias2;
bool isPot(ll k){
while(k > 1){
if(k % 2 == 1)return false;
k/=2;
}
return true;
}
int principio, puntero;
int generar(ll vec, ll desde, ll cada, ll cuantosHay, bool up){
//cout << "generando " << vec << " desde " << desde << " " << cada << "hay " << cuantosHay << endl;
ll tam = goes[vec].size()-desde;
ll cuantosReal = (tam + cada-1)/cada;
if(cuantosReal == 1 and cuantosHay == 1){
return goes[vec][desde];
}
if(cuantosReal <= 0 and cuantosHay == 1){
if(!up){
return principio;
}else{
return INT_MAX;
}
}
x.pb(0);
y.pb(0);
int estoy = currentSwitch ++ ; // 1
x[estoy-1] = generar(vec, desde, cada * 2, cuantosHay/2, false);
y[estoy-1] = generar(vec, desde + cada, cada*2, cuantosHay/2, up);
if(y[estoy-1] == INT_MAX)puntero = estoy-1;
return (-estoy);
}
void create_circuit(int M, std::vector<int> A) {
n = A.size();
for(int i = 1 ; i < n ; i ++){
goes[A[i-1]].pb(A[i]);
}
int temp = 1;
while(temp < 2000000){
potencias2.pb(temp);
temp*= 2;
}
int ultimo = A.back();
//goes[A.back()].pb(0);
bool vis[M+1];
memset(vis,false, sizeof vis);
c.pb(A[0]);
vector<pair<int, int> > toRepair; // switch inicio, indice Y final
for(int i = 1 ; i <= M ; i ++)c.pb(0);
for(int i = 0 ; i < n ; i ++){
if(A[i] == ultimo)continue;
if(!vis[A[i]]){
vis[A[i]] = true;
principio = -currentSwitch;
ll nextPot = 1;
while(nextPot < goes[A[i]].size())nextPot*=2;
c[A[i]] = generar(A[i], 0, 1, nextPot, true);
if(!isPot(goes[A[i]].size())){
toRepair.pb({c[A[i]], puntero});
//cout << "ins " << c[A[i]] << " " << puntero << endl;
}
}
}
if(goes[ultimo].size() == 0){
if(toRepair.size() == 0){
c[ultimo] = 0;
answer(c, x, y);
return ;
}else{
c[ultimo] = toRepair.back().ff;
}
}else{
principio = -currentSwitch;
int nextPot = 1;
while(nextPot < goes[ultimo].size())nextPot*=2;
if(nextPot == goes[ultimo].size()){
c[ultimo] = generar(ultimo, 0, 1, nextPot*2, true);
toRepair.pb({c[ultimo], puntero});
}else {
c[ultimo] = generar(ultimo, 0, 1, nextPot, true);
toRepair.pb({c[ultimo], puntero});
}
}
for(int i = toRepair.size() -1 ; i > 0 ; i --){
//cout << "end " << toRepair[i].ss << " to " << toRepair[i-1].ff << endl;
y[toRepair[i].ss] = toRepair[i-1].ff;
}
y[toRepair[0].ss] = 0;
answer(c, x, y);
}
