#include "prize.h"
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
#ifdef LOCAL
#include "../print.h"
#else
template <typename... Args> inline void print(const Args&... args) {}
inline void newline() {}
#endif
using ll = long long;
using pii = std::pair<int, int>;
#define endl '\n'
#define FOR1(n) for (int _ = 0; _ < n; _++)
#define FOR2(i, n) for (int i = 0; i < n; i++)
#define FOR3(i, a, b) for (int i = a; i < b; i++)
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload3(__VA_ARGS__, FOR3, FOR2, FOR1)(__VA_ARGS__)
using namespace std;
int search(int l, int r, pii left, pii right) {
if (l > r) {
return -1;
}
int m = (l + r) / 2;
vector<int> c = ask(m);
pii curr = {c [0], c [1]};
if (c [0] == 0 && c [1] == 0) {
return m;
}
if (l == r) {
return -1;
}
int ret = -1;
if (c [1] > 0 && curr != right) {
ret = search(m + 1, r, curr, right);
}
if (ret == -1 && c [0] > 0 && curr != left) {
ret = search(l, m - 1, left, curr);
}
return ret;
}
int find_best(int n) {
return search(0, n - 1, {-1, -1}, {-1, -1});
}
