#include<bits/stdc++.h>
using namespace std;
#include "prize.h"
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count() ^ (long long) (make_unique<char>().get()));
template<typename T> T rnd(T v) {
T k = (T) rng();
return (T) (((k % v) + v) % v);
}
#define pb push_back
#define sz(a) (int)((a).size())
const vector<int> good = {0, 0};
constexpr int maxn = 2e5+10;
set<int> s;
// map<int,set<int>> s;
int ans[maxn], base;
// int solve(int l, int r) {
// if(l > r) return -1;
// int m = (l+r) >> 1;
// vector<int> get = ask(m);
// if(get == good) return m;
// ans[m] = get[0];
// auto it = s[get[0]+get[1]].insert(m).first;
// if(it == s[get[0]+get[1]].begin() || ans[*prev(it)] != ans[m]) {
// int ans = solve(l, m-1);
// if(ans != -1) return ans;
// }
// if(it == --s[get[0]+get[1]].end() || ans[*next(it)] != ans[m]) {
// int ans = solve(m+1, r);
// if(ans != -1) return ans;
// }
// return -1;
// }
int solve(int l, int r) {
if(l > r) return -1;
int m = (l+r) >> 1;
vector<int> get = ask(m);
if(get == good) return m;
ans[m] = get[0];
auto it = s.begin();
if(get[0]+get[1] == base)
it = s.insert(m).first;
if(get[0]+get[1] != base || it == s.begin() || ans[*prev(it)] != ans[m]) {
int ans = solve(l, m-1);
if(ans != -1) return ans;
}
if(get[0]+get[1] != base || it == --s.end() || ans[*next(it)] != ans[m]) {
int ans = solve(m+1, r);
if(ans != -1) return ans;
}
return -1;
}
int find_best(int n) {
for(int i = 0; i < min(475, n); i++) {
vector<int> a = ask(i);
base = max(base, a[0]+a[1]);
}
return solve(0, n-1);
}
