#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
#include "doll.h"
int calc(int x) { // depth needed
int curr = 1;
int res = 0;
while (curr < x) {
curr *= 2;
res++;
}
return res - 1;
}
vi calcOrder(int d) {
vi order = {0};
for (int j = 0; j <= d; j++) {
vi order2;
for (int x : order) {
order2.pb(x);
order2.pb(x + (1 << j));
}
order = order2;
}
return order;
}
void create_circuit(int M, vi A) {
int N = A.size();
/* cout<<"A: ";
for (int i = 0; i < N; i++) {
cout<<A[i]<<" ";
}
cout<<endl;*/
vi allr[M + 1];
allr[0].pb(A[0]);
for (int i = 0; i < N - 1; i++) {
allr[A[i]].pb(A[i + 1]);
}
allr[A[N - 1]].pb(0);
/* cout<<"allr: "<<endl;
for (int i = 0; i <= M; i++) {
cout<<i<<": ";
for (int x : allr[i])
cout<<x<<" ";
cout<<endl;
}*/
int curr = -1; // current id
vi ans(M + 1, 0);
vector<ii> rit; // negative to negative
// create binary tree
for (int i = 0; i <= M; i++) {
// cout<<"at "<<i<<endl;
int K = allr[i].size();
if (K == 0) { // never used
ans[i] = 0;
continue;
}
if (K == 1) {
ans[i] = allr[i][0];
continue;
}
ans[i] = curr; // go to binary tree
int depth = calc(K);
vi order = calcOrder(depth);
// order[i]: time that cell i is used
/* cout<<"order: ";
for (int x : order)
cout<<x<<" ";
cout<<endl;*/
int gap = (1 << (depth + 1)) - K;
vi conv((1 << (depth + 1)), -1);
// conv[i]: cell used at time i
for (int j = 0; j < (1 << (depth + 1)); j++) {
conv[order[j]] = j;
}
for (int j = 0; j < (1 << depth) - 1; j++) {
rit.pb({curr - (2 * j + 1), curr - (2 * j + 2)});
}
for (int j = (1 << depth) - 1; j < (1 << (depth + 1)) - 1; j++) {
int pos = j - ((1 << depth) - 1);
ii tp = {curr, curr};
if (gap <= order[2 * pos])
tp.fi = allr[i][order[2 * pos] - gap];
if (gap <= order[2 * pos + 1])
tp.se = allr[i][order[2 * pos + 1] - gap];
rit.pb(tp);
}
curr -= ((1 << (depth + 1)) - 1);
}
vi ans1, ans2;
for (ii p : rit) {
ans1.pb(p.fi);
ans2.pb(p.se);
}
/* cout<<"ans: ";
for (int x : ans)
cout<<x<<" ";
cout<<endl;
cout<<"ans1: ";
for (int x : ans1)
cout<<x<<" ";
cout<<endl;
cout<<"ans2: ";
for (int x : ans2)
cout<<x<<" ";
cout<<endl;*/
answer(ans, ans1, ans2);
}
