#include <iostream>
#include <vector>
#include <map>
#include "prize.h"
using namespace std;
typedef pair<int,int> pii;
struct Info {
int higher = 0;
int leftsum = 0;
int rightsum = 0;
};
map<int, map<pii, Info>> segments;
int find_best(int n) {
if (segments.empty()) {
int m = n/2;
auto q = ask(m);
int v = q[0]+q[1];
if (v == 0) return m;
segments[v][{0, m}] = Info{q[0], 0, q[1]};
segments[v][{m+1, n}] = Info{q[1], q[0], 0};
}
while (1) {
auto its = segments.end();
--its;
auto& s = its->second;
double bestp = 0;
auto bestit = s.end();
for (auto it = s.begin(); it != s.end(); ++it) {
int l = it->first.second - it->first.first;
if (l > 0) {
double p = ((double)it->second.higher)/l;
if (p>bestp) {
bestit = it;
bestp = p;
}
}
}
auto x = bestit->first;
auto oldinfo = bestit->second;
int m = (x.first+x.second)/2;
auto q = ask(m);
int v = q[0] + q[1];
if (v == 0) return m;
// fix here, different v.
s.erase(bestit);
s[{x.first, m}] = Info{q[0]-oldinfo.leftsum, oldinfo.leftsum, q[1]};
s[{m+1, x.second}] = Info{q[1]-oldinfo.rightsum, q[0], oldinfo.rightsum};
}
return -1;
}
