#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 2e5+50;
const int oo = 1e9;
const int mod = 1e9+7;
int dsu[N];
vector<int> a;
int find(int u){
return u==dsu[u]?u:dsu[u] = find(dsu[u]);
}
int find_best(int n){
int cur = 0;
set<int> st;
for(int i=0;i<n;i++){
dsu[i]=i;
st.insert(i);
}
for(int i=0;i<5000;i++){
a = ask(cur);
if(!a[0] && !a[1])return cur;
if(a[0] > a[1]){
int md = cur/2;
md = find(md);
st.erase(md);
auto it = st.lower_bound(md);
if(it != st.begin())it--;
dsu[md] = *it;
cur = md;
}else{
int md = (n+cur-1)/2;
md = find(md);
st.erase(md);
auto it = st.lower_bound(md);
if(it != st.begin())it--;
dsu[md] = *it;
cur = md;
}
}
return 0;
}
