#include <bits/stdc++.h>
#define ll long long
#define el cout << '\n'
#define ii pair<int, int>
#define fi first
#define se second
using namespace std;
const int maxn = 2e5;
vector<int> answer[maxn + 10];
vector<int> ask(int i);
vector<int> do_ask(int i)
{
if (answer[i].back() != -1)
return answer[i];
return answer[i] = ask(i);
}
int find_best(int n)
{
for (int i = 0; i < n; i++)
answer[i] = vector<int>{-1, -1};
int SQRT = 2 * sqrt(n);
SQRT = min(n, SQRT);
int mx = 0;
for (int i = 0; i <= 2 * SQRT; i++)
{
vector<int> x = do_ask(i);
if (x.front() + x.back() == 0)
return i;
mx = max(mx, x.front() + x.back());
}
for (int i = 0; i < n; )
{
int l = i;
int r = n - 1;
int ans = 0;
vector<int> pivot = do_ask(i);
if (pivot.back() + pivot.front() == 0)
return i;
if (pivot.back() + pivot.front() != mx)
{
i++;
continue;
}
while (l <= r)
{
int m = l + r >> 1;
vector<int> x = do_ask(m);
if (x.front() + x.back() == 0)
return m;
if (x.front() + x.back() == mx && x.front() == pivot.front())
l = m + 1;
else
{
ans = m;
r = m - 1;
}
}
i = ans;
}
return 0;
}
