#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
const int N=(1<<19);
set<int> S;
vector<vector<int>> V;
vector<int> ask2(int i){
if(S.find(i)==S.end())V[i]=ask(i), S.insert(i);
return V[i];
}
int find_best(int n) {
V.resize(n);
map<int, int> M;
for(int i = 0; i < n; ) {
std::vector<int> res = ask2(i);
if(res==vector<int>{0, 0})return i;
auto it=S.lower_bound(i);
int l=0, r=n-i-1;
while(V[*it]==res){
l=*it-i;
it++;
}
if(it!=S.end())r=*it-i;
if(M[res[0]+res[1]]++>450){
while(l<r){
int m;
m=(l+r+1)/2;
vector<int> res2=ask2(i+m);
if(res2==res)l=m;
else r=m-1;
}
M[res[0]+res[1]]+=l;
}
i+=l+1;
}
return 0;
}
