#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
void create_circuit(int M, vector<int> A) {
int N = A.size();
vector<vector<int>> occ(M + 1);
for (int i = 0; i < N; ++i) occ[A[i]].push_back(i);
vector<int> C(M + 1, 0);
vector<int> X, Y;
int sw_id = 1;
map<int, int> head, tail;
for (int t = 1; t <= M; ++t) {
head[t] = sw_id++;
tail[t] = head[t];
}
for (int t = 1; t <= M; ++t) {
int sz = occ[t].size();
for (int i = 2; i < sz; ++i) {
int new_sw = sw_id++;
tail[t] = new_sw;
}
}
X.resize(sw_id);
Y.resize(sw_id);
C[0] = A[0];
for (int t = 1; t <= M; ++t) {
C[t] = -head[t];
}
for (int t = 1; t <= M; ++t) {
auto& pos = occ[t];
int sz = pos.size();
if (sz == 0) continue;
int cur = head[t];
for (int i = 0; i < sz; ++i) {
int nxt = (i + 1 < sz) ? -(head[t] + i + 1) : (pos[i] + 1 < N ? A[pos[i] + 1] : 0);
X[cur] = -cur;
Y[cur] = nxt;
if (nxt < 0) cur = -nxt;
}
}
for (int t = 1; t <= M; ++t) {
int s = tail[t];
if (!X[s]) X[s] = -s;
if (!Y[s]) Y[s] = 0;
}
X.erase(X.begin());
Y.erase(Y.begin());
answer(C, X, Y);
}
