#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
// void answer(vector<int> C, vector<int> X, vector<int> Y){
// printArr(C);
// printArr(X);
// printArr(Y);
// }
void create_circuit(int m, vector<int> a) {
int n = a.size();
a.push_back(0);
vector<vector<int>> fw(m+1);
for(int i = 0; i<n; ++i){
fw[a[i]].push_back(a[i+1]);
}
fw[0].push_back(a[0]);
vector<int> C(m+1, 0);
vector<int> X, Y;
for(int i = 0; i<=m; ++i) {
if (fw[i].size() > 2) exit(1);
if (fw[i].size() == 0) continue;
if (fw[i].size() == 1) C[i] = fw[i][0];
if (fw[i].size() == 2){
int cur = X.size(); cur = -cur - 1;
C[i] = cur;
X.push_back(fw[i][0]);
Y.push_back(fw[i][1]);
}
}
answer(C, X, Y);
}
// int main(void){
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// create_circuit(4, {1, 2, 1, 3});
// return 0;
// }
