#include<bits/stdc++.h>
//#include "squares.h"
using namespace std;
vector<int> paint(int n){
//low n test cases
if (n<=1000){
vector<int> ans(n+1,0);
ans[n]=n;
return ans;
}
//the actual solution
vector<int> v,vv;
for (int bit=0; bit<67 && v.size()!=n; bit++){
vv.clear();
for (int i=0; i<7; i++){
int tr = (bit >> i) & 1;
vv.push_back(tr);
}
for (int j=6; j>=0 && v.size()!=n; j--){v.push_back(vv[j]);}
for (int j=8; j>=0 && v.size()!=n; j--){v.push_back(1);}
}
v.push_back(16);
return v;
}
int find_location(int n, vector<int> vx){
//low n test cases
if (n<=1000){
int ans=0;
for (auto x : vx){if (x==-1){ans++;}}
return ans;
}
//ending with -1
int x=n-16;
for (int i=n-1; i>=0; i--){
if (vx[i]==-1){
x++;
}
}
if (x>n-16){return x;}
//the actual solution
vector<int> v,vv;
for (int bit=0; bit<67 && v.size()!=n; bit++){
vv.clear();
for (int i=0; i<7; i++){
int tr = (bit >> i) & 1;
vv.push_back(tr);
}
for (int j=6; j>=0 && v.size()!=n; j--){v.push_back(vv[j]);}
for (int j=8; j>=0 && v.size()!=n; j--){v.push_back(1);}
}
for (int i=0; i<n-15; i++){
vv.clear();
for (int j=i; j<i+16; j++){
vv.push_back(v[j]);
}
if (vv==vx){return i;}
}
return 0;
}
// subtask 1,2,3 -- > 70 = 2 * 35 -- > ((35 * 36 ) / 2) *2 > 1000 hence we can just do 35 1 then 35 0 then 34 1 ... so on
// subtask 4,5 {half point} 2^10 > 1024 {xxxxxxxxxx011111111}; 21 {i think it is obv on cases like xxx0111..1xxxx} use ur brain.
// subtask 5 {more than half score}
// as long as 2^(10-x) > 1000/(2^x) we can find it. xxxxxxx0111111
//
