#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
const int TAILLEMAXI=100*1000+2;
vector<int> vers[TAILLEMAXI];
vector<int> X,Y,prochain;
void create_circuit(int M,vector<int> A) {
A.push_back(0);
for (int i=0;i<(int)A.size()-1;i++){
vers[A[i]].push_back(A[i+1]);
}
int compt=-1;
prochain.push_back(A[0]);
for (int i=1;i<=M;i++){
if (vers[i].size()==0){
prochain.push_back(0);
}
else if (vers[i].size()==1){
prochain.push_back(vers[i][0]);
}
else {
int taille=1;
while (taille<(int)vers[i].size()){
taille*=2;
}
//cout<<taille<<endl;
vector<pair<int,int>> arbre={};
vector<int> etat={};
arbre.push_back({0,0});
etat.push_back(0);
for (int j=1;j<taille/2;j++){
arbre.push_back({2*j,2*j+1});
etat.push_back(0);
}
for (int j=taille/2;j<taille;j++){
arbre.push_back({0,0});
etat.push_back(0);
}
int pris=vers[i].size();
while (pris>1){
int ec=1;
while (ec<taille/2){
//cout<<42<<" "<<ec<<endl;
int anc=ec;
if (etat[ec]==0){
ec=ec*2;
}
else {
ec=ec*2+1;
}
etat[anc]+=1;
etat[anc]%=2;
}
//cout<<ec<<endl;
if (etat[ec]==0){
arbre[ec].first=vers[i][vers[i].size()-pris];
}
else {
arbre[ec].second=vers[i][vers[i].size()-pris];
}
etat[ec]+=1;
etat[ec]%=2;
pris--;
}
for (int j=1;j<taille;j++){
if (arbre[j].first==0){
arbre[j].first=compt;
}
if (arbre[j].second==0){
if (j==taille-1){
arbre[j].second=vers[i].back();
}
else {
arbre[j].second=compt;
}
}
}
//cout<<arbre[1].first<<" "<<arbre[1].second<<endl;
prochain.push_back(compt);
for (int i=1;i<taille/2;i++){
X.push_back(compt-arbre[i].first+1);
Y.push_back(compt-arbre[i].second+1);
}
for (int i=taille/2;i<taille;i++){
X.push_back(arbre[i].first);
Y.push_back(arbre[i].second);
}
compt-=taille-1;
}
}
/*for (auto a:prochain){
cout<<a<<" ";
}
cout<<endl;
for (auto a:X){
cout<<a<<" ";
}
cout<<endl;
for (auto a:Y){
cout<<a<<" ";
}
cout<<endl;*/
answer(prochain,X,Y);
//answer({1,-1},{-2,1,1},{-3,-1,0});
//cout<<vers[1].size()<<endl;
}
