#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
int res;
bool check(vector<int> &tmp) {
return !tmp[0] && !tmp[1];
}
void cal(int l, int r, int fl, int fr) {
if (l == r || l + 1 == r || res != -1) return;
int mid = (l + r) >> 1;
vector<int> tmp = ask(mid);
if (check(tmp)) { res = mid; return; }
if (tmp[0] != fr) cal(mid, r, tmp[0], fr);
if (tmp[0] != fl) cal(l, mid, fl, tmp[0]);
}
int find_best(int n) {
res = -1;
vector<int> l = ask(0);
vector<int> r = ask(n - 1);
if (check(l)) return 0;
if (check(r)) return n - 1;
cal(0, n - 1, l[0], r[0]);
return res;
}
