#ifndef GRADER
#include "prize.h"
#endif
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
int find_best(int n) {
map<int,vi> qs;
map<int,set<int>> ma;
set<pi> intervals = {{0,n-1}};
auto removeivs = [&](int l, int r) {
intervals.erase(intervals.lower_bound(pi{l,-oo}), intervals.upper_bound(pi{r,-oo}));
};
while(!intervals.empty()) {
auto iv = *intervals.begin();
intervals.erase(intervals.begin());
int mid = (iv.first+iv.second+1)/2;
auto v = qs[mid] = ask(mid);
int type = v[0]+v[1];
if(type==0) return mid;
auto [it,good] = ma[type].insert(mid);
if(iv.first<=mid-1) intervals.insert(pi{iv.first,mid-1});
if(mid+1<=iv.second) intervals.insert(pi{mid+1,iv.second});
if(it==ma[type].begin() ) {
if(v[0]==0) removeivs(0,mid);
} else {
auto vv = qs[*prev(it)];
if(vv[0]==v[0]) removeivs(*prev(it),mid);
}
if(next(it)==ma[type].end()) {
if(v[1]==0) removeivs(mid,n);
} else {
auto vv = qs[*(++it)];
if(vv[1]==v[1]) removeivs(mid,*it);
}
}
return -1;
}
