#include "prize.h"
#include <vector>
#include <iostream>
#include <random>
using namespace std;
int const N=2e5+10;
bool vis[N]={};
vector<int>val[N];
vector<int> qu(int i)
{
if (vis[i])
return val[i];
vis[i]=1;
val[i]=ask(i);
return val[i];
}
int find_best(int n)
{
srand(time(0));
int mx=0;
for (int i=0;i<min(n,1500);i++)
{
int x=rand()%n;
if (vis[x])
{
i--;
continue;
}
vector<int>g=qu(x);
if (g[0]+g[1]>mx)
mx=g[0]+g[1];
if (g[0]+g[1]==0)
return x;
}
int st=0;
while (1)
{
vector<int>g=qu(st);
if (g[0]==0&&g[1]==0)
break;
if (g[0]+g[1]>=mx)
{
int en=n;
mx=g[0]+g[1];
while (st+1<en)
{
int mid=(st+en)/2;
if (mid<n&&qu(mid)==g)
st=mid;
else
en=mid;
}
}
st++;
}
return st;
}
