#include <iostream>
#include <vector>
#include "prize.h"
using namespace std;
int tot, Ans;
vector<int> res;
// vector<int> ask(int id){
// return {};
// }
void Solve(int l, int r, int k, int cnt){
vector<int> rs;
if (cnt == 0 or l == r)
return;
// cout<<l<<" "<<r<<" "<<cnt<<endl;
int mid = (l + r) / 2;
rs = ask(mid);
// cout<<l<<" "<<mid<<" "<<r<<" "<<k<<" "<<cnt<<" "<<rs[0]<<" "<<rs[1]<<endl;
if (rs[0] + rs[1] != tot){
int m1 = mid + 1;
if (rs[0] + rs[1] == 0)
Ans = mid;
while (m1 < r){
rs = ask(m1);
if (rs[0] + rs[1] == 0)
Ans = m1;
if (rs[0] + rs[1] == tot)
break;
m1++;
}
// cout<<"here "<<m1<<" "<<rs[0]<<" "<<rs[1]<<endl;
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));
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, tot);
return Ans;
}
