#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int le[200001], ri[200001];
map<int, int> ge;
vector<int> vec;
int bad, unfound = 0;
vector<int> asksk(int n) {
if(le[n] >= 0) {
vector<int> v;
v.push_back(le[n]);
v.push_back(ri[n]);
return v;
}
else return ask(n);
}
int rec(int l, int r, int u) {
// cout << l << ' ' << r << ' ' << u << "\n";
int k = u;
if(u == 0) return 0;
int mid = (l+r)/2;
int l_r, r_l; l_r = r_l = mid;
while(l_r > l && u >= 0) {
auto v = asksk(l_r);
le[l_r] = v[0]; ri[l_r] = v[1];
if(le[l_r] + ri[l_r] != bad) u--;
else {
u -= rec(l, l_r, le[l_r] - le[l]);
break;
}
l_r--;
}
while(r_l < r && u >= 0) {
auto v = asksk(r_l);
le[r_l] = v[0]; ri[r_l] = v[1];
if(le[r_l] + ri[r_l] != bad && r_l != mid) u--;
else if(le[r_l] + ri[r_l] == bad) {
u -= rec(r_l, r, k - le[r_l] + le[l]);
break;
}
r_l++;
}
return k;
}
int find_best(int n) {
for(int i = 0; i < n; i++) le[i] = ri[i] = -1;
int k = 0;
while(7 * k * k / 8 < n) {
k++;
if(k == n) break;
}
if(n <= 5000) k = n;
for(int i = 0; i < k; i++) {
auto v = asksk(i);
le[i] = v[0]; ri[i] = v[1];
if(ge.find(le[i] + ri[i]) == ge.end()) ge[le[i] + ri[i]] = 1;
else ge[le[i] + ri[i]]++;
}
for(auto p : ge) {
vec.push_back(p.first);
}
bad = vec[vec.size() - 1]; // sum of lowest prize
unfound = bad;
int st = 0;
int buffer = 0;
for(int i = 0; i < k; i++) {
if(le[i] + ri[i] != bad) {
buffer++;
}
else {
unfound -= buffer; buffer = 0;
st = i;
}
}
rec(st, n, unfound);
for(int i = 0; i < n; i++) {
if(le[i] + ri[i] == 0) return i;
}
rec(0, n, bad);
for(int i = 0; i < n; i++) {
if(le[i] + ri[i] == 0) return i;
}
return bad+200000;
}
