#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
#define sz(x) (int)x.size()
int S, N;
vector<int> X, Y;
vector<int> C;
// void build(int node, int mx_node)
// {
// if (node == 1)
// X.resize(sz(X) + mx_node - 1, -S - node), Y.resize(sz(Y) + mx_node - 1, -S - node);
// if (node * 2 >= mx_node)
// return;
// X[S + node - 1] = -S - node * 2;
// Y[S + node - 1] = -S - node * 2 - 1;
// build(2 * node, mx_node), build(2 * node + 1, mx_node);
// }
void build(int leaves_start, int node = 1)
{
if (node == 1)
{
X.resize(leaves_start - 1, -1), Y.resize(leaves_start - 1, -1);
C[0] = -1;
}
if (2 * node < leaves_start)
{
X[node - 1] = -2 * node;
build(leaves_start, 2 * node);
}
if (2 * node + 1 < leaves_start)
{
Y[node - 1] = -2 * node - 1;
build(leaves_start, 2 * node + 1);
}
}
void create_circuit(int M, vector<int> A)
{
N = A.size();
C.resize(M + 1);
int binLog = -1;
for (int i = 0; i < 20; i++)
if ((1 << i) >= N)
{
binLog = i;
break;
}
int pow2 = 1 << binLog;
build(pow2);
cout << pow2 << '\n';
int start_leaf = 2 * pow2 - N;
for (int i = 0; i < N; i++)
{
C[A[i]] = -1;
if (i == N - 1)
C[A[i]] = 0;
int mask = i;
int dest_node = 0;
for (int j = 0; j < binLog; j++)
if ((mask >> j) & 1)
dest_node += 1 << (binLog - j - 1);
dest_node += (1 << binLog);
int parent = (dest_node) / 2;
if (2 * parent == dest_node)
{
X[parent - 1] = A[i];
}
else
{
Y[parent - 1] = A[i];
}
// int destination_leaf = start_leaf + i;
// C[A[i]] = -1;
// if (i == N - 1)
// C[A[i]] = 0;
// if (destination_leaf % 2) // Y
// {
// Y[destination_leaf / 2 - 1] = A[i];
// }
// else // X
// {
// X[destination_leaf / 2 - 1] = A[i];
// }
}
for (auto x : C)
cout << x << " ";
cout << '\n';
for (auto x : X)
cout << x << " ";
cout << '\n';
for (auto x : Y)
cout << x << " ";
cout << '\n';
// C[0] = A[0];
// vector<int> make_switches;
// set<int> seen;
// vector<int> adj[M + 1];
// adj[0].push_back(A[0]);
// for (int i = 0; i < N; i++)
// {
// if (i < N - 1)
// adj[A[i]].push_back(A[i + 1]);
// else
// adj[A[i]].push_back(0);
// if (adj[A[i]].size() == 1)
// C[A[i]] = adj[A[i]][0];
// else if (seen.find(A[i]) == seen.end())
// {
// make_switches.push_back(A[i]);
// seen.insert(A[i]);
// }
// }
// int sz_switches = make_switches.size();
// // for (auto x : make_switches)
// // cout << x << " ";
// // cout << '\n';
// X.reserve(200005), Y.reserve(200005);
// S = 0;
// for (int i = 0; i < sz_switches; i++)
// {
// int root_trigger = make_switches[i];
// int root_switch = -S - 1;
// C[root_trigger] = root_switch;
// int K = sz(adj[root_trigger]);
// int log2;
// for (int i = 0; i < 32; i++)
// if ((1 << i) >= K)
// {
// log2 = i;
// break;
// }
// build(1, 1 << log2);
// auto leaves = adj[root_trigger];
// reverse(leaves.begin(), leaves.end());
// leaves.resize(1 << log2, root_switch);
// reverse(leaves.begin(), leaves.end());
// for (int i = 0; i < sz(leaves); i++)
// {
// // int mask = sz(leaves) - i - 1;
// int mask = i;
// int dest_node = 0;
// for (int j = 0; j < log2; j++)
// if ((mask >> j) & 1)
// dest_node += 1 << (log2 - j - 1);
// dest_node += (1 << log2);
// int parent = (dest_node) / 2;
// if (2 * parent == dest_node)
// X[S + parent - 1] = leaves[i];
// else
// Y[S + parent - 1] = leaves[i];
// // cout << "dest_node = " << dest_node << ", parent = " << parent << '\n';
// // cout << "S = " << S << ", S + parent + 1 = " << S + parent + 1 << '\n';
// }
// S += (1 << log2) - 1;
// }
answer(C, X, Y);
}
