#include <iostream>
#include <vector>
#include "prize.h"
#include <chrono>
using namespace std;
int tot, Ans = 0;
vector<int> res;
vector<int> Ask(int id){
res = ask(id);
if (res[0] + res[1] == 0)
Ans = id;
return res;
}
void Solve(int l, int r, int k, int cnt){
vector<int> rs;
if (cnt == 0 or l == r)
return;
int mid = (l + r) / 2;
rs = Ask(mid);
if (rs[0] + rs[1] != tot){
int m1 = mid + 1;
while (m1 < r){
rs = Ask(m1);
if (rs[0] + rs[1] == tot)
break;
m1++;
}
if (m1 == r)
Solve(l, mid, k, cnt - (m1 - mid));
else
Solve(l, mid, k, k - rs[1] - (m1 - mid));
Solve(m1, r, rs[1], cnt - (k - rs[1]));
return;
}
Solve(l, mid, k, k - rs[1]);
Solve(mid, r, rs[1], cnt - (k - rs[1]));
}
int find_best(int n){
srand(time(0));
if (n <= 150){
for (int i=0;i<n;i++){
Ask(i);
tot = max(tot, res[0] + res[1]);
}
}
else{
for (int i=1;i<=20;i++){
int id = rand() % n;
Ask(id);
tot = max(tot, res[0] + res[1]);
}
for (int k=0;k<70;k++){
Ask(k);
tot = max(tot, res[0] + res[1]);
}
for (int k=0;k<70;k++){
Ask(n - k - 1);
tot = max(tot, res[0] + res[1]);
}
for (int k=0;k<70;k++){
Ask(min(n - 1, k + 513));
tot = max(tot, res[0] + res[1]);
}
}
Solve(0, n, tot, tot);
return Ans;
}
