#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
void create_circuit(int m, vector<int> a) {
int n = (int) a.size();
vector<int> c(m + 1, 0), x, y;
auto solve1 = [](vector<int> a, int n, int m) ->array<vector<int>, 3>{
vector<int> x, y, c(m + 1);
c[0] = a[0];
a.push_back(0);
function<int(vector<int>)> solve = [&](vector<int> z) -> int {
if (z.size() == 1) {
return z[0];
}
int last = -((int) x.size() + 1);
x.push_back(0), y.push_back(0);
vector<int> L, R;
for (int i = 0; i < (int) z.size(); ++i) {
if (i & 1 ^ 1) {
L.push_back(z[i]);
} else {
R.push_back(z[i]);
}
}
if (L.size() > R.size()) {
R.push_back(last);
}
int ll = solve(L), rr = solve(R);
x[-last - 1] = ll, y[-last - 1] = rr;
return last;
};
a.erase(a.begin());
int last = solve(a);
for (int i = 1; i <= m; ++i) {
c[i] = last;
}
return {c, x, y};
};
auto solve2 = [](vector<int> a, int n, int m) ->array<vector<int>, 3>{
vector<int> x, y, c(m + 1);
c[0] = a[0];
a.push_back(0);
vector<vector<int>> g(m + 1);
for (int i = 0; i < n; ++i) {
g[a[i]].push_back(a[i + 1]);
}
for (int i = 1; i <= m; ++i) {
if (!g[i].empty()) {
function<int(vector<int>)> solve = [&](vector<int> z) -> int {
if (z.size() == 1) {
return z[0];
}
int last = -((int) x.size() + 1);
x.push_back(0), y.push_back(0);
vector<int> L, R;
for (int i = 0; i < (int) z.size(); ++i) {
if (i & 1 ^ 1) {
L.push_back(z[i]);
} else {
R.push_back(z[i]);
}
}
if (L.size() > R.size()) {
R.push_back(last);
}
int ll = solve(L), rr = solve(R);
x[-last - 1] = ll, y[-last - 1] = rr;
return last;
};
c[i] = solve(g[i]);
}
}
return {c, x, y};
};
auto s1 = solve1(a, n, m), s2 = solve2(a, n, m);
if (s1[2].size() < s2[2].size()) {
answer(s1[0], s1[1], s1[2]);
} else {
answer(s2[0], s2[1], s2[2]);
}
}
