#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> glst;
void init(int l, int r){
if (l > r)
return;
int m = (l + r) >> 1;
glst.push_back(m);
init(l, m - 1);
init(m + 1, r);
}
int find_best(int n) {
init(0, n - 1);
vector<bool> blocked(n, false);
map<long long, int> zip;
vector<vector<pair<int, int>>> lst(6, vector<pair<int, int>>(n, { -1, -1 }));
int k = 1;
for (int i : glst){
if (blocked[i])
continue;
vector<int> ret = ask(i);
if (ret[0] + ret[1] == 0)
return i;
if (!zip[ret[0] + ret[1]]){
zip[ret[0] + ret[1]] = k;
k++;
}
if (lst[zip[ret[0] + ret[1]] - 1][ret[0]].first == -1){
lst[zip[ret[0] + ret[1]] - 1][ret[0]].first = lst[zip[ret[0] + ret[1]] - 1][ret[0]].second = i;
}else{
if (i < lst[zip[ret[0] + ret[1]] - 1][ret[0]].first){
for (int o = i; o < lst[zip[ret[0] + ret[1]] - 1][ret[0]].first; o++)
blocked[o] = true;
lst[zip[ret[0] + ret[1]] - 1][ret[0]].first = i;
}else{
for (int o = lst[zip[ret[0] + ret[1]] - 1][ret[0]].second; o < i; o++)
blocked[o] = true;
lst[zip[ret[0] + ret[1]] - 1][ret[0]].second = i;
}
}
}
return 0;
}
