#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int n, m, a[maxn];
vector < int > c, x, y;
struct state
{
int dev, lf_child, rf_child;
state()
{
dev = 0;
lf_child = rf_child = -1;
}
};
state tree[4 * maxn];
int qleft, qright, sum;
int build(int left, int right)
{
if (left >= qleft && right <= qright)
{
sum ++;
return -1;
}
if (left == right)
{
sum ++;
return -1;
}
int node = x.size() + 1;
x.push_back(0);
y.push_back(0);
int mid = (left + right) / 2;
tree[node].lf_child = build(left, mid);
tree[node].rf_child = build(mid + 1, right);
x[node - 1] = - tree[node].lf_child;
y[node - 1] = - tree[node].rf_child;
//cout << node << " : " << tree[node].lf_child << endl;
//cout << node << " : " << tree[node].rf_child << endl;
tree[node].dev = node;
return node;
}
int pos[4 * maxn];
struct element
{
int type, idx, val;
element(int _type, int _idx, int _val)
{
type = _type;
idx = _idx;
val = _val;
}
};
vector < element > fin;
bool cmp(element e1, element e2)
{
if (e1.idx == e2.idx)
return e1.type < e2.type;
return e1.idx < e2.idx;
}
bool cmp2(element e1, element e2)
{
return e1.val < e2.val;
}
void simulate_path(int node, int val)
{
///cout << "simulate " << node << " " << val << endl;
if (pos[node] == 0)
{
if (tree[node].lf_child == -1)
{
fin.push_back(element(0, node - 1, val));
///x[node - 1] = val;
}
else
{
simulate_path(tree[node].lf_child, val);
}
pos[node] = 1;
}
else
{
if (tree[node].rf_child == -1)
{
fin.push_back(element(1, node - 1, val));
///y[node - 1] = val;
}
else
{
simulate_path(tree[node].rf_child, val);
}
pos[node] = 0;
}
}
void create_circuit(int M, vector<int> A)
{
n = A.size();
m = M;
for (int i = 0; i < A.size(); i ++)
a[i] = A[i];
c.resize(m + 1);
for (int i = 0; i <= m; i ++)
c[i] = -1;
int nec = 1;
while(nec < n + 1)
nec *= 2;
qleft = 0;
qright = (nec - (n + 1)) - 1;
int root = build(0, nec - 1);
for (int i = 0; i < nec; i ++)
simulate_path(root, i);
sort(fin.begin(), fin.end(), cmp);
reverse(fin.begin(), fin.end());
int rub = nec - (n + 1);
for (int k = 0; k < rub; k ++)
{
element el = fin.back();
fin.pop_back();
///cout << el.idx << " :: " << el.type << endl;
if (el.type == 0)
x[el.idx] = - root;
else
y[el.idx] = - root;
}
///cout << sum << " " << fin.size() << endl;
sort(fin.begin(), fin.end(), cmp2);
for (int k = 0; k < n + 1; k ++)
{
element el = fin[k];
if (el.type == 0)
x[el.idx] = a[k];///, cout << "left " << el.idx << " " << a[k] << endl;
else
y[el.idx] = a[k];///, cout << "right " << el.idx << " " << a[k] << endl;
}
/**for (int i = 0; i <= m; i ++)
{
create_node(i);
continue;
}*/
/**cout << "--------------" << endl;
for (int i = 0; i <= m; i ++)
cout << c[i] << " ";
cout << endl;
cout << "--------------" << endl;
for (int i = 0; i < x.size(); i ++)
cout << x[i] << " " << y[i] << endl;*/
answer(c, x, y);
}
