#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int find_best(int n) {
// ask 450 qn first
unordered_map<int, int> knownGood;
unordered_map<int, int> askedBeforeL, askedBeforeR;
int sumMax = 0, posMax = 0, maxRight = 0;
for (int i = 0; i < 1; i++){
vector<int> q;
if (askedBeforeR[i] != 0 || askedBeforeL[i] != 0){
q = {askedBeforeL[i], askedBeforeR[i]};
}
else{
q = ask(i);
askedBeforeL[i] = q[0];
askedBeforeR[i] = q[1];
}
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 = 1;
// check if its within the first 1023 queries
// now that we are at the worst one
while(cur < n){
// find right endpoint
int l = cur, r = min(n-1, cur + 512);
vector<int> askR;
if (askedBeforeR[r] != 0 || askedBeforeL[r] != 0){
askR = {askedBeforeL[r], askedBeforeR[r]};
}
else{
askR = ask(r);
askedBeforeL[r] = askR[0];
askedBeforeR[r] = askR[1];
}
if (askR[0] + askR[1] == 0){
// found it alr lmao
return r;
}
if (askR[0] + askR[1] == sumMax && askR[1] == maxRight){
l = r;
cur = r;
continue;
}
if (askR[0] + askR[1] < sumMax){
knownGood[r] = 1;
r++;
}
while(l < r){
int mid = (l + r + 1)/2;
vector<int> askMid;
if (askedBeforeR[mid] != 0 || askedBeforeL[mid] != 0){
askMid = {askedBeforeL[mid], askedBeforeR[mid]};
}
else{
askMid = ask(mid);
askedBeforeL[mid] = askMid[0];
askedBeforeR[mid] = askMid[1];
}
if (askMid[0] + askMid[1] == 0){
// found it alr lmao
return mid;
}
if (askMid[0] + askMid[1] < sumMax){
knownGood[mid] = 1;
}
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(cur < n){
if (knownGood[cur]){
cur++;
continue;
}
// cout << "hey its not worst" << endl;
vector<int> q;
if (askedBeforeR[cur] != 0 || askedBeforeL[cur] != 0){
q = {askedBeforeL[cur], askedBeforeR[cur]};
}
else{
q = ask(cur);
askedBeforeL[cur] = q[0];
askedBeforeR[cur] = q[1];
}
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++;
}
}
return 0;
}
