#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
bool asked[200000];
int L[200000], R[200000];
int v, N;
vector<int> previous_queries;
void Ask(int i)
{
if (asked[i]) return;
asked[i] = true;
previous_queries.push_back(i);
vector<int> res = ask(i);
L[i] = res[0], R[i] = res[1];
}
int find_best(int n)
{
memset(asked, false, sizeof(asked));
N = n;
int i = 0;
while (i < n)
{
Ask(i);
if (L[i] + R[i] == 0)
return i;
for (int j = 18; j >= 0; j--)
if (i + (1 << j) < n)
{
bool bad_query = false;
for (int x : previous_queries)
if (i <= x && x <= i + (1 << j) && (L[x] != L[i] || R[x] != R[i]))
{
bad_query = true;
break;
}
if (bad_query) continue;
Ask(i + (1 << j));
if (L[i + (1 << j)] + R[i + (1 << j)] == 0)
return i + (1 << j);
if (L[i + (1 << j)] == L[i] && R[i + (1 << j)] == R[i])
i += (1 << j);
}
i++;
}
return 0;
}
