#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+1;
int total;
int n;
vector<int> vec;
int get_next(int pos) {
int l = log2(n-1 - pos);
int p = pos;
auto Ask = ask(p+1);
if(Ask[0] + Ask[1] != total) {
return p+1;
}
int pref = Ask[0];
for(int i=l; i>=0; --i) {
auto res = ask(p + (1<<i));
if(res[0] - pref==0 && res[0]+res[1]==total) {
p+= (1<<i);
}
}
p++;
return p;
}
int find_best(int N) {
n = N;
for(int i=0; i<min(n, 500); ++i) {
auto res = ask(i);
total = max(total, res[0] + res[1]);
}
int pos = -1;
while(true) {
pos = get_next(pos);
auto Ask = ask(pos);
if(Ask[0] + Ask[1] == 0) return pos;
}
return 0;
}
