#include <bits/stdc++.h>
using namespace std;
#define FORi(i,a,b) for(int i=(int)a;i<(int)b;i++)
#define FOR(i,n) FORi(i,0,n)
#define FOA(v, a) for(auto v : a)
#define ll long long
#define F first
#define S second
typedef pair<int, int> ii;
#include "squares.h"
int ss = 0;
int n;
int bcnt(int x){
int cnt=0;
while(x) cnt++, x/=2;
return cnt;
}
int ans;
void rec(int x){
//cout<<"x "<<x<<endl;
if(bcnt(x)==n){ ans=x; return; }
// slide da windo
set<int> all;
int i=bcnt(x);
int c=0;
int ind=-ss+1;
while(i>=0){
c = c*2 % (1<<ss);
//cout<<"( "<<c<<" ";
if(x&(1<<i)) c++;
//cout<<c<<") ";
if(ind>=0) all.insert(c);
ind++;
i--;
}
//cout<<"all ";FOA(v, all) cout<<v<<" ";
//cout<<endl;
int next = c*2 % (1<<ss);
if(!all.count(next)) rec(x*2);
if(ans) return;
if(!all.count(next+1)) rec(x*2+1);
}
vector<int> paint(int N) {
n = N;
ans = 0;
ss = bcnt(n);
cout<<"ss "<<ss<<endl;
rec(1<<(ss-1));
vector<int> l;
while(ans) l.push_back(ans%2), ans/=2;
reverse(l.begin(), l.end());
/*
FOA(v,l) cout<<v<<" ";
cout<<endl;
cout<<endl;
*/
l.push_back(ss);
return l;
}
int find_location(int n, std::vector<int> f) {
ans=0;
ss = bcnt(n);
//cout<<"finding "<<endl;
rec(1<<(bcnt(n)-1));
//cout<<endl;
int x =0;
int ind=0;
FOA(v,f){
x*=2;
x+=v;
if(v==-1) return n-ind;
ind++;
}
//cout<<"target "<<x<<endl;
int i=bcnt(ans);
int c=0;
ind=-ss;
while(i>=0){
c = c*2 % (1<<ss);
//cout<<"( "<<c<<" ";
if(ans&(1<<i)) c++;
//cout<<c<<") ";
if(ind>=0 && x==c) return ind;
ind++;
i--;
}
//cout<<endl;
return -1;
}
