#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
bool asked[maxn];
int ansL[maxn], ansR[maxn];
void query(int pos)
{
if (asked[pos] == true) return;
vector<int> curr = ask(pos);
ansL[pos] = curr[0];
ansR[pos] = curr[1];
}
const int SEARCH_TO = 500;
int find_best(int n)
{
if (n <= 5000)
{
for (int i = 0; i < n; ++i)
{
query(i);
if (ansL[i] + ansR[i] == 0) return i;
}
}
for (int i = 0; i < SEARCH_TO; ++i)
{
query(i);
}
int start = 0, better = 0;
int maxSum = ansL[0] + ansR[0];
for (int i = 1; i < SEARCH_TO; ++i)
{
if (ansL[start] + ansR[start] < ansL[i] + ansR[i])
{
start = i;
better = i - 1;
maxSum = ansL[i] + ansR[i];
}
else
{
++better;
}
}
while (true)
{
int l = start + 1;
int r = n - 1;
while (l <= r)
{
int mid = (l + r) / 2;
query(mid);
if (ansL[mid] + ansR[mid] == 0) return mid;
if (ansL[mid] + ansR[mid] < maxSum)
{
r = mid - 1;
}
else
{
if (ansL[mid] + ansR[mid] > better) r = mid - 1;
else l = mid + 1;
}
}
int blockEnd = r;
for (int i = blockEnd + 1; i < n; ++i)
{
query(i);
if (ansL[i] + ansR[i] == 0) return i;
if (ansL[i] + ansR[i] == maxSum)
{
start = i;
break;
}
++better;
}
}
}
