#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
void create_circuit(int M, vector<int> A) {
int N = A.size();
vector<int> C(M + 1), X, Y, needin, unsure;
vector<vector<int> > vec(M + 1, vector<int>());
for (int i = 0; i < N; i++) {
vec[A[i]].pb(i + 1 < N ? A[i + 1] : 0);
}
C[0] = A[0];
for (int i = 1; i <= M; i++) {
if (vec[i].empty()) {
C[i] = 0;
} else if (vec[i].size() == 1) {
C[i] = vec[i][0];
} else if (vec[i].size() == 2) {
// create new switch
C[i] = -((int)X.size() + 1);
X.pb(vec[i][0]);
Y.pb(vec[i][1]);
} else if (vec[i].size() == 3) {
// create 3 new switches
C[i] = -((int)X.size() + 1);
X.pb(C[i] - 1);
Y.pb(C[i] - 2);
X.pb(vec[i][0]);
Y.pb(vec[i][2]);
X.pb(vec[i][1]);
Y.pb(-(int)1e9);
needin.pb(C[i]);
unsure.pb((int)Y.size() - 1);
} else if (vec[i].size() == 4) {
// create 3 new switches
C[i] = -((int)X.size() + 1);
X.pb(C[i] - 1);
Y.pb(C[i] - 2);
X.pb(vec[i][0]);
Y.pb(vec[i][2]);
X.pb(vec[i][1]);
Y.pb(vec[i][3]);
}
}
if (!needin.empty()) {
for (int &i : C) {
if (i == 0) {
i = needin[0];
}
}
for (int &i : X) {
if (i == 0) {
i = needin[0];
}
}
for (int &i : Y) {
if (i == 0) {
i = needin[0];
}
}
for (int i = 0; i < (int)unsure.size(); i++) {
Y[unsure[i]] = (i + 1 < (int)unsure.size() ? needin[i + 1] : 0);
}
}
answer(C, X, Y);
}
