#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 270013
#define INF 998244353
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int N, M, T;
vi ord;
vi seq[2 * MAXN];
vi ans, ch[2];
int rv[2 * MAXN], arr[2 * MAXN];
int dif;
void build(int w, int L, int R)
{
if (L == R)
{
L = rv[L];
if (L < dif)
{
arr[w] = -1;
return;
}
L -= dif;
arr[w] = ord[L];
//do smth
return;
}
int mid = (L + R) >> 1;
build(w << 1, L, mid);
build(w << 1 | 1, mid + 1, R);
arr[w] = -w;
}
void dfs(int w, int L, int R)
{
if (L == R) return;
ch[0][w - 1] = arr[w << 1];
ch[1][w - 1] = arr[w << 1 | 1];
int mid = (L + R) >> 1;
dfs(w << 1, L, mid);
dfs(w << 1 | 1, mid + 1, R);
}
void create_circuit(int n, vi A)
{
n++; N = n;
A.insert(A.begin(), 0);
A.PB(0);
M = SZ(A);
FOR(i, 0, M - 1)
{
seq[A[i]].PB(A[i + 1]);
}
ans.resize(N);
FOR(i, 0, N)
{
if (seq[i].empty()) continue;
// if (SZ(seq[i]) == 1)
// {
// ans[i] = seq[i][0]; continue;
// }
ans[i] = -1;
}
ans[0] = A[1];
// cerr << SZ(ans) << endl;
FOR(i, 2, M)
{
// if (SZ(seq[A[i - 1]]) == 1) continue;
ord.PB(A[i]);
}
// for (int x : ord)
// {
// cerr << x << ' ';
// }
// cerr << endl;
if (SZ(ord) != 0)
{
int sz = (32 - __builtin_clz(SZ(ord)));
FOR(i, 0, (1 << sz))
{
int sum = 0;
FOR(j, 0, sz)
{
if (i & (1 << j))
{
sum += (1 << (sz - 1 - j));
}
}
rv[sum] = i;
//reverse the
}
sz = (1 << sz);
dif = sz - SZ(ord);
ch[0].resize(sz - 1); ch[1].resize(sz - 1);
build(1, 0, sz - 1);
dfs(1, 0, sz - 1);
}
// cerr << "SZ " << SZ(ch[0]) << endl;
answer(ans, ch[0], ch[1]);
//let's try for 100
//build a segtree on ord. except we need to apply compression.
}
