#include "prize.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<int, int>
const int mod = 1e9 + 7;
const int mxN = 2e3 + 5;
const int mnN = 1e9 * -1;
using namespace std;
vector<vector<int>> res;
int cntask;
vector<int> getVal(int i){
if(res[i].empty()){
res[i] = ask(i);
cntask++;
}
if(cntask >= 9000) assert(0);
return res[i];
}
int find_best(int n)
{
res.resize(n);
assert(0);
if (n <= 5000)
{
for (int i = 0; i < n; i++)
{
res[i] = getVal(i);
if (res[i][0] + res[i][1] == 0)
return i;
}
}
int mx = 0;
for (int tmp = 0; tmp < 20; tmp++)
{
int md = rand() % n;
if (res[md].empty())
res[md] = getVal(md);
mx = max(res[md][0] + res[md][1], mx);
}
int sq = sqrt(n);
int s = 0, e = sq;
while (s < e)
{
// cout<<s<<' '<<e<<'\n';
while (s <= e)
{
if (res[s].empty())
res[s] = getVal(s);
if (res[s][0] + res[s][1] != mx)
{
if (res[s][0] + res[s][1] == 0)
return s;
s++;
continue;
}
if (res[e].empty())
res[e] = getVal(e);
if (res[s] == res[e])
break;
int num = res[s][0];
int l = s - 1, r = e, md;
while (l < r)
{
md = (l + r + 1) / 2;
if (res[md].empty())
res[md] = getVal(md);
if (res[md][0] + res[md][1] == 0)
return md;
if (res[md][0] + res[md][1] != mx || res[md][0] != num)
{
r = md - 1;
}
else
l = md;
}
l++;
if (res[l].empty())
res[l] = getVal(l);
if (res[l][0] + res[l][1] == 0)
return l;
s = l + 1;
}
s = e + 1;
e += sq + 1;
e = min(e, n - 1);
}
}
