#include "prize.h"
#include <cmath>
#include <iostream>
#include <cassert>
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 200000;
int identity = 0, diamond = -1;
int queries = 0;
std::vector<int> already[1 + nmax];
std::vector<int> realask(int x){
if(already[x].size() == 0) {
std::vector<int> sol = ask(x);
already[x] = sol;
if(sol[0] + sol[1] == 0)
diamond = x;
}
return already[x];
}
void solve(int from, int to, int left, int right){
///invalid interval
if(to < from) {
//std::cout << "Invalid\n";
return ;
}
///no special element here :(
if(identity == left + right) {
//std::cout << "Muggle\n";
return ;
}
///diamond was already found
if(0 <= diamond) {
//std::cout << "Already\n";
return ;
}
int mid = (from + to) / 2;
std::vector<int> sol = realask(mid);
if(sol[0] + sol[1] == identity){
solve(from, mid - 1, left, sol[1]);
solve(mid + 1, to, sol[0], right);
} else {
int mid2 = mid + 1;
if(0 < sol[1]){
while(mid2 <= to){
sol = realask(mid2);
if(sol[0] + sol[1] == identity) {
solve(mid2 + 1, to, sol[0], right);
break;
}
mid2++;
}
}
if(0 < sol[0]) {
mid2 = mid - 1;
while(from <= mid2){
sol = realask(mid2);
if(sol[0] + sol[1] == identity){
solve(from, mid2 - 1, left, sol[1]);
break;
}
mid2--;
}
}
}
}
int find_best(int n) {
int special = 0;
int n2 = sqrt(n);
while(1 <= n2){
special += n2;
n2 = sqrt(n2 - 1);
}
//special = 0;
//std::cout << n << " " << special << '\n';
assert(special <= 800);
for(int i = 0;i < MIN(special + 1, n - 1); i++){
std::vector<int> sol = realask(i);
identity = MAX(identity, sol[0] + sol[1]);
}
solve(MIN(special + 1, n - 1), n - 1, 0, 0);
assert(0 <= diamond);
assert(queries <= 10000);
return diamond;
}
