#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<int>a, cnt;
namespace sub1{
void solve(){
vector<int>c(m + 1, 0);
c[0] = a[0];
for(int i = 0; i + 1 < n; i++){
c[a[i]] = a[i + 1];
}
answer(c, {}, {});
}
}
namespace sub2{
void solve(){
vector<int>x, y, c(m + 1, 0);
c[0] = a[0];
a.push_back(0);
for(int i = 0; i < n; i++){
if(cnt[a[i]] == 2){
x.push_back(a[i + 1]);
y.push_back(cnt[a[i]] = -1);
c[a[i]] = -int(x.size());
}
else if(cnt[a[i]] == -1){
y[-c[a[i]] - 1] = a[i + 1];
}
else{
c[a[i]] = a[i + 1];
}
}
answer(c, x, y);
}
}
namespace sub3{
void solve(){
vector<vector<int>>p(m + 1);
for(int i = 0; i < n; i++){
p[a[i]].push_back(i);
}
a.push_back(0);
vector<int>c(m + 1, 0), x, y;
c[0] = a[0];
for(int i = 1; i <= m; i++){
if(p[i].size() == 1){
c[i] = a[p[i][0] + 1];
}
else if(p[i].size() == 2){
x.push_back(a[p[i][0] + 1]);
y.push_back(a[p[i][1] + 1]);
c[i] = -int(x.size());
}
else if(p[i].size() == 3){
int siz = x.size();
x.push_back(-siz - 2);
x.push_back(a[p[i][0] + 1]);
x.push_back(a[p[i][1] + 1]);
y.push_back(-siz - 3);
y.push_back(c[i] = -siz - 1);
y.push_back(a[p[i][2] + 1]);
}
else if(p[i].size() == 4){
int siz = x.size();
x.push_back(-siz - 2);
x.push_back(a[p[i][0] + 1]);
x.push_back(a[p[i][1] + 1]);
y.push_back(-siz - 3);
y.push_back(a[p[i][2] + 1]);
y.push_back(a[p[i][3] + 1]);
c[i] = -siz - 1;
}
}
answer(c, x, y);
}
}
namespace sub456{
void solve(){
a.push_back(0);
n++;
int N = 1;
while(N < n){
N <<= 1;
}
vector<int>x, y;
vector<pair<int, bool>>f(N, make_pair(-1, false));
function<void(int, int, pair<int, bool>, int)>play;
play = [&] (int n, int s, pair<int, bool>to, int id){
if(n < 1){
if(to.second){
y[to.first] = -1;
}
else{
x[to.first] = -1;
}
return;
}
if(s == 1){
f[id] = to;
return;
}
int siz = x.size() + 1;
x.push_back(-1);
y.push_back(-1);
play(n - (s >> 1), s >> 1, make_pair(siz - 1, false), id);
play(n, s >> 1, make_pair(siz - 1, true), id + (N / s));
if(to.first != -1){
if(to.second){
y[to.first] = -siz;
}
else{
x[to.first] = -siz;
}
}
};
play(n, N, f[0], 0);
for(int i = 0, j = 0; i < N; i++){
if(f[i].first != -1){
if(f[i].second){
y[f[i].first] = a[j++];
}
else{
x[f[i].first] = a[j++];
}
}
}
answer(vector<int>(m + 1, -1), x, y);
}
}
void create_circuit(int _m, vector<int>_a){
swap(a, _a);
n = a.size();
cnt.assign((m = _m) + 1, 0);
for(int& i : a){
cnt[i]++;
}
int max_cnt = *max_element(cnt.begin(), cnt.end());
if(max_cnt <= 1){
return sub1::solve();
}
if(max_cnt <= 2){
return sub2::solve();
}
if(max_cnt <= 4){
return sub3::solve();
}
return sub456::solve();
}
