#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];
int l1 = (l-1)/2+1;
auto check = ask(p+(1<<(l1)));
if(check[0] + check[1] != total || check[0] - pref != 0) {
l = l1;
}
for(int i=l; i>=0; --i) {
if(p+(1<<i)>=n) continue;
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;
int pos = -1;
for(int i=0; i<min(n, 500); ++i) {
auto res = ask(i);
if(i!=0 && res[0] + res[1] > total) {
total = res[0] + res[1];
pos = i-1;
}
if(res[0] + res[1]==0) return i;
if(res[0] + res[1] < total) pos = i;
}
while(true) {
pos = get_next(pos);
auto Ask = ask(pos);
if(Ask[0] + Ask[1] == 0) return pos;
}
return 0;
}
