#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
typedef long long ll;
struct dat{
int l, r, lx, rx;
dat(){}
dat(int l, int r, int lx, int rx): l(l), r(r), lx(lx), rx(rx){}
};
vector<int> vec;
vector<int> chk[200002];
int connect[200002];
int queryCount;
vector<int> my_ask(int x){
if(chk[x].size() == 2) return chk[x];
queryCount++;
return chk[x] = ask(x);
}
int find_best(int n){
for(int i=1; i<=200000; i++){
int tmp = int(floor(sqrt(i)) + 1e-8);
connect[i] = connect[tmp] + i;
}
for(int i=0; i<n; i++) vec.push_back(i);
while((int)vec.size() > 1){
queue<dat> que;
int k = (int)vec.size();
int sum = 0, lim = 0;
for(int i=0; connect[i+1] + (i+1)*(i+1) <= k+10; i++) lim = connect[i+1];
vector<int> randomVec = vec;
random_shuffle(randomVec.begin(), randomVec.end());
stable_sort(randomVec.begin(), randomVec.end(), [&](auto x, auto y){
if(chk[x].size() == 2 && chk[y].size() != 2) return x<y;
if(chk[x].size() != 2 && chk[y].size() == 2) return x>y;
return false;
});
for(int i=0; i<=lim && i<k; i++){
auto tVec = my_ask(randomVec[i]);
sum = max(sum, tVec[0] + tVec[1]);
if(sum >= lim) break;
}
que.push(dat(0, k-1, 0, 0));
vector<int> newVec;
while(!que.empty()){
dat tmp = que.front(); que.pop();
int cnt = tmp.r - tmp.l + 1 - (sum - tmp.lx - tmp.rx);
if(cnt == 0){
for(int x=tmp.l; x<=tmp.r; x++){
newVec.push_back(vec[x]);
}
continue;
}
int mid = (tmp.l + tmp.r) / 2;
int midL = mid, midR = mid;
while(mid <= tmp.r){
auto tVec = my_ask(vec[mid]);
if(tVec[0] + tVec[1] == sum) break;
midR = mid;
newVec.push_back(vec[mid++]);
}
if(mid > tmp.r){
mid = (tmp.l + tmp.r) / 2;
while(mid >= tmp.l){
auto tVec = my_ask(vec[mid]);
if(tVec[0] + tVec[1] == sum) break;
midL = mid;
newVec.push_back(vec[mid--]);
}
}
if(mid < tmp.l) continue;
auto tVec = my_ask(vec[mid]);
assert(tVec[0] + tVec[1] == sum);
if(tVec[0] != tmp.lx){
int rightCount = tVec[1];
if(mid == midR + 1) rightCount += (midR - (tmp.l + tmp.r) / 2 + 1);
que.push(dat(tmp.l, midL-1, tmp.lx, rightCount));
}
if(midR+1 <= tmp.r && tVec[1] != tmp.rx) que.push(dat(midR+1, tmp.r, tVec[0], tmp.rx));
}
vec = newVec;
sort(vec.begin(), vec.end());
}
return vec[0];
}
