#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
const bool typetest = 0;
const int N = 1e3 + 5;
map<int, int> ck;
int a[N], m, s, ans, b[N];
bool dfs(int v, int dep)
{
ck[v] = dep;
b[dep - 1] = v;
if (dep == 971)
return true;
int u = v >> 1;
if (!ck[u + (1 << 29)])
if (dfs(u + (1 << 29), dep + 1))
return true;
if (!ck[u])
if (dfs(u, dep + 1))
return true;
return false;
}
int *paint(int n)
{
if (n <= 30)
{
for (int i = 0; i < n; ++i)
a[i] = 1;
a[n] = n;
return a;
}
ck.clear();
dfs(1, 1);
for (int i = 1; i < n - 30 + 1; ++i)
a[i - 1] = b[i - 1] & 1;
for (int i = 0; i < 30; ++i)
a[n - 30 + 1 + i - 1] = (b[n - 30 + 1 - 1] >> i) & 1;
a[n] = 30;
return a;
}
int find_location(int n, vector<int> c)
{
if (n <= 30)
{
for (int i = 0; i < n; ++i)
if (c[i] != 1)
return -1;
return 0;
}
ck.clear();
dfs(1, 1);
ans = -1;
for (int i = 1; i <= n - 30 + 1; ++i)
{
bool flag(0);
for (int j = 0; j < 30; ++j)
if (c[j] != a[i - 1 + j])
{
flag = 1;
break;
}
if (!flag)
{
ans = i - 1;
break;
}
}
return ans;
}
