#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
map<int, pair<int, int>> memo;
vector<int> query(int i) {
vector<int> res;
if (memo.count(i)) {
res.emplace_back(memo[i].first);
res.emplace_back(memo[i].second);
} else {
res = ask(i);
memo[i] = {res[0], res[1]};
}
return res;
}
int numValuable;
vector<int> candidates; // non-lollipop boxes
void binarySearch(int leftValuable, int rightValuable, int left, int right) {
if (left > right || leftValuable + rightValuable == numValuable) {
return;
}
int mid = (left + right) / 2;
vector<int> res = query(mid);
if (res[0] + res[1] == numValuable) { // mid is a lollipop box
binarySearch(leftValuable, res[1], left, mid - 1);
binarySearch(res[0], rightValuable, mid + 1, right);
} else { // mid is a non-lollipop box
candidates.emplace_back(mid);
int nearestLeft, nearestRight;
for (int i = mid + 1; i <= right; i++) {
res = query(i);
if (res[0] + res[1] == numValuable) {
nearestRight = i;
binarySearch(query(nearestRight)[0], rightValuable, nearestRight + 1, right);
break;
} else { // i is a non-lollipop box
candidates.emplace_back(i);
}
}
for (int i = mid - 1; i >= left; i--) {
res = query(i);
if (res[0] + res[1] == numValuable) {
nearestLeft = i;
binarySearch(leftValuable, query(nearestLeft)[1], left, nearestLeft - 1);
break;
} else { // i is a non-lollipop box
candidates.emplace_back(i);
}
}
}
}
int find_best(int n) {
numValuable = 0;
for (int i = 0; i < min(n, 500); i++) { // least valuable box must satisfy sum^2 <= n, and since n <= 200000 then sum <= 500 will suffice
vector<int> res = query(i);
if (res[0] + res[1] > numValuable) {
numValuable = res[0] + res[1];
}
if (numValuable > 30) { // second least valuable box must satisfy (sum^2)^2 <= n, and since n <= 200000 then sum <= 30 will suffice
break; // we will only check at most one least valuable box, the rest will be valuable and checked later anyways
}
}
binarySearch(0, 0, 0, n - 1);
int ans = -1;
for (auto &c : candidates) {
vector<int> res = query(c);
if (res[0] == 0 && res[1] == 0) {
ans = c;
}
}
return ans;
}
