#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);
}
int give() {
srand(time(NULL));
return rand() % 2;
}
vector<vector<int>> seg(200005, {-1, -1});
void calc(int l, int r, bool f) {
if (l == r || ans != -1) {
return;
}
int m = (l+r)/2;
if (f) {
if (seg[l][0] == -1) {
seg[l] = ask(l);
}
if (check(seg[l])) {
ans = l;
return;
}
if (seg[m][0] == -1) {
seg[m] = ask(m);
}
if (check(seg[m])) {
ans = m;
return;
}
if (seg[l] != seg[m] || seg[m][0]-seg[l][0] != 0) {
calc(l, m, give());
}
if (ans != -1) {
return;
}
if (seg[m+1][0] == -1) {
seg[m+1] = ask(m+1);
}
if (check(seg[m+1])) {
ans = m+1;
return;
}
if (seg[r][0] == -1) {
seg[r] = ask(r);
}
if (check(seg[r])) {
ans = r;
return;
}
if (seg[m+1] != seg[r] || seg[r][0]-seg[m+1][0] != 0) {
calc(m+1, r, give());
}
} else {
if (seg[m+1][0] == -1) {
seg[m+1] = ask(m+1);
}
if (check(seg[m+1])) {
ans = m+1;
return;
}
if (seg[r][0] == -1) {
seg[r] = ask(r);
}
if (check(seg[r])) {
ans = r;
return;
}
if (seg[m+1] != seg[r] || seg[r][0]-seg[m+1][0] != 0) {
calc(m+1, r, give());
}
if (ans != -1) {
return;
}
if (seg[l][0] == -1) {
seg[l] = ask(l);
}
if (check(seg[l])) {
ans = l;
return;
}
if (seg[m][0] == -1) {
seg[m] = ask(m);
}
if (check(seg[m])) {
ans = m;
return;
}
if (seg[l] != seg[m] || seg[m][0]-seg[l][0] != 0) {
calc(l, m, give());
}
}
}
int find_best(int n) {
calc(0, n-1, give());
return ans;
}
