#include "prize.h"
#include <iostream>
using namespace std;
int sub1(int st, int ed) {
int mid = (st + ed) / 2;
vector<int> v = ask(mid);
int l = v[0], r = v[1];
if(l == 1) return sub1(st, mid-1);
else if(r == 1) return sub1(mid+1, ed);
else return mid;
}
int ls[200100], rs[200100], maxLR;
// u = sum of cheapest V's left and right
bool isDiamond(int i);
void makeLR(int i);
int findDiamond(int st, int ed);
int sub2(int n) { // idx: 0 ~ n-1
for(int i=0; i<n; i++) {
ls[i] = -1; rs[i] = -1;
}
int x = 236;
// find st, ed
int st = 0;
maxLR = -1;
while(st <= x) {
makeLR(st);
// check if it is dia
if(isDiamond(st)) return st;
// if no then record maxlr
maxLR = max(maxLR, ls[st] + rs[st]);
st++;
}
int ed = n-1;
while(ed >= n-1 - x) {
makeLR(ed);
// check if it is dia
if(isDiamond(ed)) return ed;
// if no then record maxlr
maxLR = max(maxLR, ls[ed] + rs[ed]);
ed--;
}
st = 0;
while(ls[st] + rs[st] < maxLR) {
makeLR(st);
if(isDiamond(st)) return st;
st++;
}
ed = n-1;
while(ls[ed] + rs[ed] < maxLR) {
makeLR(ed);
if(isDiamond(ed)) return ed;
ed--;
}
return findDiamond(st, ed);
}
bool isDiamond(int i) {
return ls[i] + rs[i] == 0;
}
void makeLR(int i) {
if(ls[i] != -1 && rs[i] != -1) return;
vector<int> v = ask(i);
ls[i] = v[0]; rs[i] = v[1];
}
// st, ed are cheapest
int findDiamond(int st, int ed) {
if(st == ed) {
if(isDiamond(st)) return st;
else return -1;
}
// if st~ed, no prize
if(ls[ed] - ls[st] == 0) return -1;
int mid = (st + ed) / 2;
makeLR(mid);
if(isDiamond(mid)) return mid;
// make led, rst
int led = mid;
while(/*led>=st*/ls[led] + rs[led] < maxLR) {
led--;
makeLR(led);
if(isDiamond(led)) return led;
}
int rst = mid;
while(/*rst<=ed*/ls[rst] + rs[rst] < maxLR) {
rst++;
makeLR(rst);
if(isDiamond(rst)) return rst;
}
int resL = findDiamond(st, led); // check initial condition
int resR = findDiamond(rst, ed);
return resL > resR ? resL:resR;
}
int find_best(int n) {
return sub2(n);
}
