#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
vector < int > memo[MAXN];
bool asked[MAXN];
vector < int > query(int idx)
{
if(asked[idx])
return memo[idx];
asked[idx] = true;
return memo[idx] = ask(idx);
}
int get_sum(int idx)
{
vector < int > cur = query(idx);
return cur[0] + cur[1];
}
map < int, vector < int > > sums[MAXN];
int dnc(int left, int right)
{
if(left > right)
return -1;
int mid = left + (right - left) / 2;
int sum = get_sum(mid);
if(sum == 0)
return mid;
auto it = sums[sum].upper_bound(mid);
bool found_left = false;
bool found_right = false;
if(it != sums[sum].end())
{
if(query(mid)[0] == it->second[0])
found_right = true;
}
if(it != sums[sum].begin())
{
it--;
if(query(mid)[0] == it->second[0])
found_left = true;
}
sums[sum][mid] = query(mid);
int result = -1;
if(!found_left)
result = dnc(left, mid - 1);
if(!found_right && result == -1)
result = dnc(mid + 1, right);
return result;
}
int find_best(int n)
{
for(int i = 0; i < n; i++)
{
memo[i].resize(2);
asked[i] = false;
}
return dnc(0, n - 1);
}
