#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 identity = 0, diamond = -1;
int queries = 0;
std::vector<int> realask(int x){
queries++;
std::vector<int> sol = ask(x);
if(sol[0] + sol[1] == 0)
diamond = x;
return sol;
}
void solve(int from, int to, int left, int right){
///invalid interval
if(to < from)
return ;
///no special element here :(
if(identity == left + right)
return ;
///diamond was already found
if(0 <= diamond)
return ;
int mid = (from + to) / 2;
std::vector<int> sol = realask(mid);
if(sol[0] + sol[1] == identity){
solve(from, mid - 1, left, right + sol[1]);
solve(mid + 1, to, left + sol[0], right);
} else {
int mid2 = mid + 1;
while(mid2 <= to){
sol = realask(mid2);
if(sol[0] + sol[1] == identity) {
solve(mid2 + 1, to, left + sol[0], right);
break;
}
mid2++;
}
mid2 = mid - 1;
while(from <= mid2){
sol = realask(mid2);
if(sol[0] + sol[1] == identity){
solve(from, mid2 - 1, left, right + 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';
special = 1000;
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(0, n - 1, 0, 0);
assert(0 <= diamond);
assert(queries <= 10000);
return diamond;
}
