#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int to;
pair<int, vector<int>> differentRight(int a, vector<int> inf)
{
int b = to;
int res = -1;
vector<int> rinf;
a++;
while (a <= b)
{
int mid = (a + b) / 2;
vector<int> cinf = ask(mid);
if (cinf[0] == 0 && cinf[1] == 0) return {mid, {0, 0}};
if (cinf[0] == 0)
{
vector<int> next = ask(mid + 1);
return {mid + 1, next};
}
if (cinf[1] == 0)
{
to = mid - 1;
}
if (cinf == inf)
{
a = mid + 1;
} else
{
res = mid;
rinf = cinf;
b = mid - 1;
}
}
return {res, rinf};
}
int find_best(int N) {
n = N;
to = n - 1;
if (n <= 5000)
{
int res = -1;
for (int i = 0; i < n; i++)
{
vector<int> v = ask(i);
if (v[0] == 0 && v[1] == 0) res = i;
}
return res;
}
vector<int> needed = {0, 0};
vector<int> big = {0, 0};
vector<int> inf;
int cur = 0;
inf = ask(cur);
big = max(big, inf);
if (inf == needed) return cur;
for (int i = 0; i < 4; i++)
{
auto p1 = differentRight(cur, inf);
cur = p1.first;
inf = p1.second;
if (inf == needed) return cur;
big = max(big, inf);
}
int ca = cur;
while(inf != needed)
{
if (inf[0] + inf[1] == big[0] + big[1])
{
ca++;
inf = ask(ca);
if (inf[0] + inf[1] == big[0] + big[1])
{
ca++;
inf = ask(ca);
if (inf[0] + inf[1] == big[0] + big[1])
{
auto p1 = differentRight(ca, inf);
ca = p1.first;
inf = p1.second;
}
}
} else
{
ca++;
inf = ask(ca);
}
}
return ca;
}
