#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
int find_best(int n) {
int sum = 0, pos = -1;
vector<int> ar;
for(int i = 0 ; i < 500 ; i++)
{
ar = ask(i);
if(ar[0] + ar[1] == 0)
return i;
sum = max(sum, ar[0] + ar[1]);
}
pos = 499;
while(true)
{
pos++;
ar = ask(pos);
if(ar[0] + ar[1] == 0)
return pos;
if(ar[0] + ar[1] == sum)
break;
}
vector<vector<int>> query(n);
while(true)
{
for(int i = 17 ; i >= 0 ; i--)
{
int target = pos + (1<<i);
if(target < n)
{
if(query[target].empty())
query[target] = ask(target);
if(query[target][0] + query[target][1] == sum and query[target][1] == ar[1])
pos = target;
}
}
pos++;
while(true)
{
if(query[pos].empty())
query[pos] = ask(pos);
ar = query[pos];
if(ar[0] + ar[1] == 0)
return pos;
else if(ar[0] + ar[1] == sum)
break;
pos++;
}
}
}
