#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
map<int, map<int, int>> memo;
pair<int, int> Ask(int pos) {
auto ans = ask(pos);
return make_pair(ans[0], ans[1]);
}
int Solve(int left, int right) {
int mid = left + (right - left) / 2;
auto ans = Ask(mid);
int color = ans.first + ans.second;
memo[color][mid] = ans.first;
if (color == 0) {
return mid;
}
if (left == right) {
return -1;
}
auto it = memo[color].upper_bound(mid);
if (it == memo[color].end() || ans.first != it->second) {
int aux = Solve(mid + 1, right);
if (aux != -1) return aux;
}
--it;
if (it == memo[color].begin() || ans.first != prev(it)->second) {
int aux = Solve(left, mid);
if (aux != -1) return aux;
}
return -1;
}
int find_best(int n) {
return Solve(0, n - 1);
}
