#include "doll.h"
#include <string.h>
using namespace std;
typedef vector<int> vi;
const int M = 100000, N_ = 1 << 18; /* N_ = pow2(ceil(log2(N))) */
int tmp[N_];
void split(int *aa, int n) {
int i, j, k;
for (i = 0, j = n / 2, k = 0; k < n; k++)
tmp[k % 2 == 0 ? i++ : j++] = aa[k];
memcpy(aa, tmp, n * sizeof *tmp);
}
vi xx, yy;
int build(int *aa, int n) {
static int idx;
if (n == 2)
xx[idx] = aa[0], yy[idx] = aa[1];
else {
split(aa, n);
xx[idx] = -(build(aa, n / 2) + 1), yy[idx] = -(build(aa + n / 2, n / 2) + 1);
}
return idx++;
}
int kk[M + 1], aa[N_];
void create_circuit(int m, vi aa_) {
vi cc(m + 1);
int n = aa_.size(), n_, n1, i, j;
for (i = 0; i < n; i++)
kk[aa_[i]]++;
for (j = 0; j <= m; j++)
cc[j] = -1;
cc[0] = aa_[0];
n1 = 0;
for (i = 0; i < n; i++)
if (kk[aa_[i]] > 1)
aa_[n1++] = i == n - 1 ? 0 : aa_[i + 1];
else
cc[aa_[i]] = i == n - 1 ? 0 : aa_[i + 1];
if (n1 != 0) {
n_ = 1;
while (n_ < n1)
n_ <<= 1;
for (i = 0; i < n_ - n1; i++)
aa[i] = -1;
for (i = 0; i < n1; i++)
aa[n_ - n1 + i] = aa_[i];
xx.resize(n_ - 1), yy.resize(n_ - 1);
build(aa, n_);
} else
for (j = 0; j <= m; j++)
if (cc[j] == -1)
cc[j] = 0;
answer(cc, xx, yy);
}
