#include <iostream>
#include <vector>
#include "prize.h"
using namespace std;
int tot;
vector<int> Ans, res;
int Solve(int l, int r, int k){
vector<int> rs;
if (l == r)
return 0;
int mid = (l + r) / 2, C = 0;
rs = ask(mid);
if (rs[0] + rs[1] != tot){
C = Solve(l, mid, k) + 1;
Ans.push_back(mid);
C += Solve(mid+1, r, k - C);
return C;
}
C = Solve(l, mid, k);
C += Solve(mid+1, r, rs[1]);
return C;
}
int find_best(int n){
srand(time(0));
for (int i=1;i<=20;i++){
int id = rand() % n;
res = ask(id);
tot = max(tot, res[0] + res[1]);
}
Solve(0, n, tot);
for (int i : Ans){
res = ask(i);
if (res[0] + res[1] == 0)
return i;
}
return 0;
}
