#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200000,buk = 480;
vector<int> res[N];
int n,mx = -1;
vector<int> ASK(int p){
if(res[p].size())
return res[p];
return res[p] = ask(p);
}
int FIND(int l,int r){
if(l == r){
vector<int> tmp = ASK(l);
if(tmp[0] == 0 && tmp[1] == 0)
return l;
return -1;
}
vector<int> tmp1,tmp2;
tmp1 = ASK(l);
tmp2 = ASK(r);
if(tmp1[0] == tmp1[1] && tmp1[0] == 0)
return l;
if(tmp2[0] == tmp2[1] && tmp2[0] == 0)
return r;
int md = (l+r)/2;
if(tmp1 == tmp2)
return -1;
int t = FIND(l,md);
int t2 = FIND(md+1,r);
if(t != -1)
return t;
return t2;
}
int find_best(int _N) {
n = _N;
return FIND(0,n-1);
}
