#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
using vi = vector<int>;
int N;
int get(int l, int r, int kiek) {
// int sqr = (int)sqrt(r - l + 1);
int m = (l + r) / 2;
if (kiek <= 0) return -1;
int st = max(l, m - kiek / 2);
// ieskom did des [1]
vi viso(2, 0);
int ind = 0;
for (int i = 0; i < kiek + 1 and st + i <= r; ++i)
{
vi ans = ask(st + i);
if (ans[0] == ans[1] and ans[0] == 0)
return i;
if (ans[0] + ans[1] >= viso[0] + viso[1]) {
ind = st + i;
viso = ans;
}
}
int left = get(l, ind - 1, kiek - viso[1]);
int right = get(ind + 1, r, kiek - viso[0]);
if (left != -1) return left;
else return right;
}
int find_best(int n) {
N = n;
// if (n <= 5000) {
// for (int i = 0; i < n; ++i)
// {
// vi ans = ask(i);
// if (ans[0] == ans[1] and ans[0] == 0)
// return i;
// }
// }
vi viso(2, 0);
int ind = 0;
for (int i = 0; i < 10; ++i) {
vi ans = ask(i);
if (ans[0] == ans[1] and ans[0] == 0)
return i;
if (ans[0] + ans[1] >= viso[0] + viso[1]) {
ind = i;
viso = ans;
}
}
return get(ind + 1, n - 1, viso[1]);
}
