#include"prize.h"
#include<bits/stdc++.h>
using namespace std;
int ans = -1;
bool check(vector<int> res) {
return (res[0] == res[1] && res[0] == 0);
}
void calc(int l, int r) {
if (l == r || ans != -1) {
return;
}
int m = (l+r)/2;
vector<int> seg1l, seg1r, seg2l, seg2r;
seg1l = ask(l);
seg1r = ask(m);
seg2l = ask(m+1);
seg2r = ask(r);
if (check(seg1l)) {
ans = l;
}
if (check(seg1r)) {
ans = m;
}
if (check(seg2l)) {
ans = m+1;
}
if (check(seg2r)) {
ans = r;
}
if (seg1l != seg1r) {
calc(l, m);
}
if (seg2l != seg2r) {
calc(m+1, r);
}
}
int find_best(int n) {
calc(0, n-1);
return ans;
}
