#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> ans;
bool aske(int l, int r, int x){
vector<int> v(n);
for(int i = 0; i < n; i++){
if(i & 1) v[i] = x;
else v[i] = n;
}
for(int i = l; i <= r; i++){
if(!(i & 1)) v[i] = -1;
}
if(perform_experiment(v) != n) return 1;
return 0;
}
bool asko(int l, int r, int x){
vector<int> v(n);
for(int i = 0; i < n; i++){
if(i & 1) v[i] = n;
else v[i] = x;
}
for(int i = l; i <= r; i++){
if(i & 1) v[i] = -1;
}
if(perform_experiment(v) != n) return 1;
return 0;
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y){
n = N;
ans.resize(n);
for(int x = 0; x < n; x++){
int l = 0, r = n - 1;
while(asko(l, r, x)){
while(l < r){
int mid = (l + r) / 2;
if(asko(l, mid, x)) r = mid;
else l = mid + 1;
}
ans[l] = x;
l++;
r = n - 1;
}
l = 0, r = n - 1;
while(aske(l, r, x)){
while(l < r){
int mid = (l + r) / 2;
if(aske(l, mid, x)) r = mid;
else l = mid + 1;
}
ans[l] = x;
l++;
r = n - 1;
}
}
return ans;
}
