#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int find_best(int n) {
// ask 450 qn first
int sumMax = 0, posMax = 0, maxRight = 0;
for (int i = 0; i < 450; i++){
vector<int> q = ask(i);
if (q[0] + q[1] == 0){
// found it alr lmao
return i;
}
if (sumMax <= q[0] + q[1]){
sumMax = q[0] + q[1];
maxRight = q[1];
posMax = i;
}
}
int cur = 450;
if (posMax != 449){
// cout << "hey its not worst" << endl;
// means we have to climb
while(true){
vector<int> q = ask(cur);
if (q[0] + q[1] == 0){
// found it alr lmao
return cur;
}
// cout << cur << endl;
if (sumMax <= q[0] + q[1]){
sumMax = q[0] + q[1];
maxRight = q[1];
break;
}
cur++;
}
}
// now that we are at the worst one
while(true){
// find right endpoint
int l = cur, r = min(n-1, cur+75);
while(l < r){
int mid = (l + r + 1)/2;
vector<int> askMid = ask(mid);
if (askMid[0] + askMid[1] == 0){
// found it alr lmao
return mid;
}
if (askMid[0] + askMid[1] == sumMax && askMid[1] == maxRight){
l = mid;
}
else{
r = mid-1;
}
}
// cout << "from " << cur << " to " << l << endl;
// we got the l = lastRight
// climb to next worst one
cur = l + 1;
while(true){
// cout << "hey its not worst" << endl;
vector<int> q = ask(cur);
if (q[0] + q[1] == 0){
// found it alr lmao
return cur;
}
// cout << cur << endl;
if (sumMax <= q[0] + q[1]){
sumMax = q[0] + q[1];
maxRight = q[1];
break;
}
cur++;
}
}
}
