/**
* user: ppavic
* fname: Patrik
* lname: Pavić
* task: prize
* score: 100.0
* date: 2019-06-16 09:02:45.353752
*/
#include "prize.h"
#include <vector>
#include <algorithm>
#include <cstring>
#define PB push_back
using namespace std;
typedef vector < int > vi;
const int N = 2e5 + 500;
int L[N], R[N];
int get_L(int i){
if(L[i] != -1) return L[i];
vi res = ask(i);
L[i] = res[0], R[i] = res[1];
return L[i];
}
int get_R(int i){
if(L[i] != -1) return R[i];
vi res = ask(i);
L[i] = res[0], R[i] = res[1];
return R[i];
}
int loli;
vi svi;
void solve(int l,int r){
if(l > r) return;
if(get_L(l) + get_R(l) < loli){
svi.PB(l); solve(l + 1, r);
return;
}
if(l == r) return;
if(get_L(r) + get_R(r) < loli){
svi.PB(r); solve(l, r - 1);
return;
}
if(get_L(l) == get_L(r) || l + 1 == r) return;
solve(l, (l + r) / 2);
solve((l + r) / 2, r);
}
int find_best(int n) {
memset(L, -1, sizeof(L));
svi.clear();
loli = 0;
for(int i = 0;i < 100;i++){
int x = (rand() + rand()) % n;
x = (x % n + n) % n;
loli = max(loli, get_L(x) + get_R(x));
}
solve(0, n - 1);
for(int x : svi){
if(get_L(x) + get_R(x) == 0)
return x;
}
return 0;
}
