#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[MAXN];
vi ans, ch[2];
int arr[2 * MAXN];
int good[2 * MAXN];
vi compress;
//proparrgarrte shit up the tree.
void build(int w, int L, int R)
{
arr[w] = -INF - 1;
if (L == R)
{
//lol reverse the strings.
if (good[L] != -1)
{
arr[w] = good[L];
// cerr << "GOOD " << w << endl;
}
return;
}
int mid = (L + R) >> 1;
build(w << 1, L, mid);
build(w << 1 | 1, mid + 1, R);
}
void dfs(int w, int L, int R)
{
if (L == R) return;
int mid = (L + R) >> 1;
dfs(w << 1, L, mid);
dfs(w << 1 | 1, mid + 1, R);
// if (arr[w << 1] == -INF - 1)
// {
// cerr << "FUCK " << w << endl;
// }
// assert(arr[w << 1] != -998244354);
if (arr[w << 1 | 1] == -INF - 1)
{
arr[w] = arr[w << 1];
arr[w << 1] = -INF - 1;
}
else
{
arr[w] = -INF;
}
}
void dfs1(int w, int L, int R)
{
if (arr[w] != -INF) return;
T++;
arr[w] = -T;
ch[0].PB(0); ch[1].PB(0);
int mid = (L + R) >> 1;
dfs1(w << 1, L, mid);
dfs1(w << 1 | 1, mid + 1, R);
int v = arr[w << 1];
// cerr << "MODIFY " << -arr[w] - 1 << "ch0 ord " << v;
ch[0][-arr[w] - 1] = (v >= 0 ? ord[v] : v);
v = arr[w << 1 | 1];
// cerr << " ch1 ord " << v << endl;
ch[1][-arr[w] - 1] = (v >= 0 ? ord[v] : v);
}
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 (SZ(seq[i]) == 1)
{
ans[i] = seq[i][0];
}
else
{
ans[i] = -1;
}
}
// cerr << SZ(ans) << endl;
FOR(i, 1, SZ(A))
{
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) - 1));
FOR(i, 0, (1 << sz)) good[i] = -1;
FOR(i, 0, SZ(ord))
{
int sum = 0;
FOR(j, 0, sz)
{
if (i & (1 << j))
{
sum += (1 << (sz - 1 - j));
}
}
good[sum] = i;
//reverse the
}
sz = (1 << sz);
build(1, 0, sz - 1);
dfs(1, 0, sz - 1);
dfs1(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.
}
