#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
using vi = vector<int>;
int N;
int lol = 0;
int isLol(const vi &a) {
return a[0] + a[1] == lol;
}
int get(int l, int r, int kiek, int kair, int des) {
// int sqr = (int)sqrt(r - l + 1);
// printf("l = %d, r = %d, kiek = %d\n", l, r, kiek);
int m = (l + r) / 2;
if (kiek <= 0) return -1;
if (l > r) return -1;
// int st = max(l, m - kiek / 2 - 5);
// ieskom did des [1]
vi viso(2, 0);
int ind = -1;
vi ans = ask(m);
if (ans[0] == ans[1] and ans[0] == 0)
return m;
if (isLol(ans)) {
ind = m;
viso = ans;
int left = get(l, ind - 1, viso[0] - kair, kair, viso[1]);
int right = get(ind + 1, r, viso[1] - des, viso[0], des);
if (left != -1) return left;
else return right;
}
int k = 1;
for (int i = 1; ind == -1 and (l <= (m - i) or (m + i) <= r); ++i)
{
if (l <= (m - i)) {
ans = ask(m - i);
// printf("askinu %d\n", m - i);
if (ans[0] == ans[1] and ans[0] == 0)
return m - i;
if (!isLol(ans)) {
k++;
} else {
ind = m - i;
viso = ans;
int left = get(l, ind - 1, viso[0] - kair, kair, viso[1]);
int right = get(m + i, r, viso[1] - des - k, viso[0] + k, des);
if (left != -1) return left;
else return right;
}
}
if ((m + i) <= r) {
ans = ask(m + i);
// printf("askinu %d\n", m + i);
if (ans[0] == ans[1] and ans[0] == 0)
return m + i;
if (!isLol(ans)) {
k++;
} else {
ind = m + i;
viso = ans;
int left = get(l, m - i - 1, viso[0] - kair - k, kair, viso[1] + k);
int right = get(ind + 1, r, viso[1] - des, viso[0], des);
if (left != -1) return left;
else return right;
}
}
}
// printf("l = %d, r = %d, kiek = %d, ind = %d, viso = %d %d, kair = %d, des = %d\n",
// l, r, kiek, ind, viso[0], viso[1], kair, des);
return -1;
// if (ind == -1) return -1;
// ind is lol
// int left = get(l, ind - 1, viso[0] - kair, kair, viso[1]);
// int right = get(ind + 1, r, viso[1] - des, viso[0], des);
// 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 < 475; ++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;
}
}
// printf("viso = %d %d\n", viso[0], viso[1]);
lol = viso[0] + viso[1];
return get(ind + 1, n - 1, viso[1], viso[0], 0);
}
