#include "prize.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
using namespace std;
int find_best(int n){
vector<vector<int>> tab(n);
auto zapytaj = [&](int i){
if(tab[i].empty()) tab[i] = ask(i);
return tab[i];
};
if(n <= 5000){
REP(i, n) if(zapytaj(i)[0]+zapytaj(i)[1] == 0) return i;
return -69;
}
int maks = 0;
REP(i, min(n, 500)){
int t = zapytaj(i)[0] + zapytaj(i)[1];
if(!t) return i;
maks = max(maks, t);
}
int wynik = -1;
function<void(int, int, int, int)> zwyciezaj = [&](int p, int k, int przed, int tutaj){
if(wynik>=0 || p>k || !tutaj) return;
int sr_org = (p+k)>>1;
int sr = sr_org, lewo = 0;
vector<int> t = zapytaj(sr);
while(1){
if(t[0]+t[1] == 0) return void(wynik = sr);
if(t[0]+t[1] < maks) break;
--sr;
if(sr < p) break;
t = zapytaj(sr);
}
lewo = t[0]-przed;
int roz = sr_org-sr;
zwyciezaj(p, sr-1, przed, lewo);
zwyciezaj(sr_org+1, k, przed+lewo+roz, tutaj-lewo-roz);
};
zwyciezaj(0, n-1, 0, maks);
return wynik;
}
