#include "prize.h"
#include<bits/stdc++.h>
#define ll long long
#define lld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define vr(v) v.begin(),v.end()
#define rv(v) v.rbegin(),v.rend()
#define Code ios_base::sync_with_stdio(false);
#define By cin.tie(NULL);
#define Davit cout.tie(NULL);
using namespace std;
namespace RND {
mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
ll RANDOM(ll l, ll r) {
ll res = myrand() % (r - l + 1) + l;
return res;
}
void shuffle(vector<int> &a) {
for (int i = 0; i < (int) a.size(); i++) {
int idx = RANDOM(0, (int) a.size() - 1);
swap(a[i], a[idx]);
}
}
};
int find_best(int n) {
int ina = 0, inb = n - 1, answer = n - 1;
while (ina <= inb) {
int mid = (ina + inb) >> 1;
vector<int> tmp = ask(mid);
if (tmp[0] == tmp[1] && tmp[0] == 0) {
return mid;
}
if (tmp[0]) {
inb = mid - 1;
answer = mid - 1;
} else {
ina = mid + 1;
answer = mid + 1;
}
}
return answer;
}
