#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int m, n;
vector<int> a;
vector<int> c;
vector<int> x;
vector<int> y;
vector<array<int, 2>> sAt;
int used;
int N;
vector<bool> endNode;
void solve(int ca, int cb, int node)
{
if (ca == cb)
{
endNode[node] = true;
return;
}
int mid = (ca + cb) / 2;
array<int, 2> cur = {-node * 2, -node * 2 - 1};
sAt[node] = cur;
solve(ca, mid, node * 2);
solve(mid + 1, cb, node * 2+ 1);
}
void create_circuit(int M, std::vector<int> A) {
m = M;
a = A;
n = A.size();
std::vector<int> C(M + 1);
C[0] = -1;
N = 1;
while (N < (n / 2))
{
N *= 2;
}
endNode.resize(4 * N);
sAt.resize(4 * N);
c = C;
for (int i = 1; i <= m; i++) c[i] = -1;
c[0] = a[0];
used = 1;
solve(1, N, 1);
int cur = 1;
int endNodeNum = 1;
vector<int> switched(4 * N);
while (true)
{
if (endNode[cur])
{
if (endNodeNum == N * 2)
{
sAt[cur][1] = 0;
} else
{
if (used < n)
{
sAt[cur][switched[cur]] = a[used];
used++;
switched[cur] = (switched[cur] + 1) % 2;
} else
{
sAt[cur][switched[cur]] = -1;
used++;
switched[cur] = (switched[cur] + 1) % 2;
}
}
if (endNodeNum == N * 2) break;
cur = 1;
endNodeNum++;
} else
{
int next = sAt[cur][switched[cur]] * (-1);
switched[cur] = (switched[cur] + 1) % 2;
cur = next;
}
}
vector<int> x;
vector<int> y;
map<int, int> turnTo;
set<int> nums;
for (int i = 0; i < 4 *N; i++)
{
if (!(sAt[i][0] == 0 && sAt[i][1] == 0))
{
if (sAt[i][0] < 0) nums.insert(sAt[i][0]);
if (sAt[i][1] < 0) nums.insert(sAt[i][1]);
}
}
int cnum = -1;
for (auto it = nums.rbegin(); it != nums.rend(); it++)
{
turnTo[*it] = cnum;
cnum--;
}
for (int i = 0; i < 4 *N; i++)
{
if (!(sAt[i][0] == 0 && sAt[i][1] == 0))
{
if (sAt[i][0] < 0) x.push_back(turnTo[sAt[i][0]]);
else x.push_back(sAt[i][0]);
if (sAt[i][1] < 0) y.push_back(turnTo[sAt[i][1]]);
else y.push_back(sAt[i][1]);
}
}
answer(c, x, y);
}
/*
*/
