#include<bits/stdc++.h>
#include "doll.h"
using namespace std;
const int M = 200010;
vector <int> cnt[M];
int at = -1;
vector <int> c, x, y;
vector <int> order(vector <int> v){
int cnt = 1;
while(cnt < v.size()){
cnt *= 2;
}
if(cnt == 1) return v;
int add = cnt-v.size();
int aaad = add;
reverse(v.begin(), v.end());
while(add > 0){
v.push_back(M);
add--;
}
reverse(v.begin(), v.end());
vector <int> aux;
for(int i = 0;i < v.size();i++){
aux.push_back(i);
}
vector <int> answer;
stack <vector <int>> q;
q.push(aux);
while(!q.empty()){
auto vv = q.top();
q.pop();
if(vv.size() == 1){
answer.push_back(vv.back());
}
else{
vector <int> v1, v2;
for(int i = 0;i < vv.size();i++){
if(i%2 == 0) v1.push_back(vv[i]);
else v2.push_back(vv[i]);
}
q.push(v2);
q.push(v1);
}
}
map <int, int> comp;
vector <int> aa;
for(int i = 0;i < v.size();i++){
if(v[i] == M) continue;
aa.push_back(answer[i]);
}
sort(aa.begin(), aa.end());
for(int i = 0;i < aa.size();i++){
// cout << aa[i] << ' ';
comp[aa[i]] = i+aaad;
}
// cout << '\n';
for(int i = 0;i < aa.size();i++){
answer[i+aaad] = comp[answer[i+aaad]];
}
vector <int> resposta;
while(resposta.size() < aaad){
resposta.push_back(M);
}
for(int i = 0;i < aa.size();i++){
resposta.push_back(v[answer[i+aaad]]);
}
return resposta;
}
void solve(int valor){
if(cnt[valor].empty()) {
c.push_back(valor);
return;
}
vector <int> aux = order(cnt[valor]);
queue <pair <vector <int>, int>> ans;
for(auto v : aux){
ans.push({{v}, v});
// cout << v << ' ';
}
// cout << '\n';
vector <pair <int, int>> novos;
while(ans.size() > 1){
auto [a, rep] = ans.front();
ans.pop();
auto [b, rep2] = ans.front();
ans.pop();
vector <int> nv;
for(int i = 0;i < a.size();i++){
nv.push_back(a[i]);
nv.push_back(b[i]);
}
if(rep == rep2){
ans.push({nv, rep});
}
else{
novos.push_back({rep, rep2});
ans.push({nv, at});
at--;
}
}
for(auto [a, b] : novos){
if(a == M) a = ans.back().second;
if(b == M) b = ans.back().second;
x.push_back(a);
y.push_back(b);
}
c.push_back(ans.back().second);
}
void create_circuit(int m, std::vector<int> A) {
int n = A.size();
A.push_back(0);
cnt[0].push_back(A[0]);
for(int i = 0;i < n;i++){
cnt[A[i]].push_back(A[i+1]);
}
for(int i = 0;i <= m;i++){
solve(i);
}
for(auto x : c){
// cout << x << ' ';
}
// cout << '\n';
for(int i = 0;i < x.size();i++){
// cout << x[i] << ' ' << y[i] << '\n';
}
answer(c, x, y);
return;
}
