#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], used;
int ans = -1;
vector<int> ask(int i);
vector<int> do_ask(int i)
{
if (answer[i].back() != -1)
return answer[i];
used.push_back(i);
return answer[i] = ask(i);
}
int sum(int x)
{
return do_ask(x).front() + do_ask(x).back();
}
bool same(int x, int y)
{
return sum(x) == sum(y);
}
void solve(int l, int r)
{
if (ans != -1 || l > r)
return ;
if (same(l - 1, r) && do_ask(r)[0] - do_ask(l - 1)[0] == 0)
return ;
int m = l + r >> 1;
if (sum(m) == 0)
{
ans = m;
return ;
}
bool lft = l < m;
bool rgt = m < r;
for (int x : used)
{
if (x < l && same(m, x) && do_ask(m)[0] - do_ask(x)[0] == 0)
lft = 0;
if (x > r && same(m, x) && do_ask(x)[0] - do_ask(m)[0] == 0)
rgt = 0;
if (!lft && !rgt)
break;
}
if (lft)
solve(l, m - 1);
if (rgt)
solve(m + 1, r);
}
int find_best(int n)
{
ans = -1;
used.clear();
for (int i = 0; i < n; i++)
answer[i] = vector<int>{-1, -1};
if (sum(0) == 0)
return 0;
if (sum(n - 1) == 0)
return n - 1;
solve(1, n - 2);
return ans;
}
