#include "prize.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef vector<int> vi;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int get_rand() {
long long x = rnd();
if (x < 0) {
x = -x;
}
x %= (int)1e9;
return x;
}
int gen(int l, int r) {
return l + (get_rand() % (r - l + 1));
}
int f(int n) {
int p = gen(0, n - 1);
vector <int> vec = ask(p);
return vec[0] + vec[1];
}
int find_best(int n) {
if (n == 1) {
return 0;
}
int S = sqrt(n);
if (S * S < n) {
S++;
}
int pos = 0;
int big = 0;
if (n < 1e5) {
for (int i = 0; i <= S * 2; i++) {
vector <int> res = ask(i);
if (res[0] == 0 && res[1] == 0) {
return i;
}
big = max(big, res[0] + res[1]);
}
pos = S + 1;
} else {
for (int i = 1; i <= 10; i++) {
big = max(big, f(n));
}
pos = 0;
}
while(1) {
vector <int> pres = ask(pos);
if (pres[0] == 0 && pres[1] == 0) {
return pos;
}
if (pres[0] + pres[1] == big) {
int l = pos, r = n;
while(r - l > 1) {
int mid = (l + r) >> 1;
vector <int> mres = ask(mid);
if (pres[0] == mres[0] && pres[1] == mres[1]) {
l = mid;
} else {
r = mid;
}
}
pos = l + 1;
} else {
pos++;
}
}
}
