#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
vector<pi>graph[2222];
bool used[2222];
int idx[2222];
vector<int>v,path;
void DFS(int cur,int edg){
while(graph[cur].size()){
int nxt = graph[cur].back().first;
int e = graph[cur].back().second;
graph[cur].pop_back();
if(used[e]) continue;
used[e] = 1;
DFS(nxt,e);
}
v.emplace_back(edg);
}
void construct_path(int n){
int mask = (1<<n)-1; mask>>=1;
for(int i=0; i<(1<<n); i++){
int from = i>>1;
int to = i&mask;
graph[from].emplace_back(pi(to,i));
}
DFS(1,-1);
v.pop_back();
reverse(v.begin(),v.end());
for(int i=0; i<v.size(); i++){
int a = v[i];
vector<int>vec;
for(int j=n-1; j>=0; j--){
if(a&(1<<j)) vec.emplace_back(1);
else vec.emplace_back(0);
}
if(path.empty()){
for(int z : vec) path.emplace_back(z);
}
else path.emplace_back(vec.back());
}
memset(idx,-1,sizeof(idx));
for(int i=0; i+9<path.size(); i++){
int val = 0;
for(int j=0; j<10; j++) val = val*2+path[i+j];
idx[val] = i;
}
}
std::vector<int> paint(int n){
if(v.empty()) construct_path(10);
std::vector<int> labels(n + 1, 1);
for(int i=0; i<n; i++) labels[i] = path[i];
labels[n] = (n >= 10?10:n);
return labels;
}
int find_location(int n, std::vector<int> c) {
if(v.empty()) construct_path(10);
int cnt = 0;
for(int x : c) cnt += (x == -1);
if(cnt) return n-c.size()+cnt;
if(n < 10) return 0;
assert(c.size() == 10);
int val = 0;
for(int x : c) val = val*2 + x;
return idx[val];
}
