// ~ Be Name Khoda ~ //
#include "prize.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 5e5 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
pair <int, int> ans[maxn5];
vector <int> av, have;
vector <pair<int, int>> todo;
bool done[maxn5], mark[maxn5];
int cnt = 0, mx = 0;
pair <int, int> assk(int id){
assert(cnt < 10000);
if(!done[id]){
cnt++;
vector <int> x = ask(id);
done[id] = true;
ans[id].fi = x[0];
ans[id].se = x[1];
}
mx = max(mx, ans[id].fi + ans[id].se);
auto ret = ans[id];
for(auto u : av){
if(u < id && ans[u].fi + ans[u].se < ans[id].fi + ans[id].se)
ret.fi--;
if(u > id && ans[u].fi + ans[u].se < ans[id].fi + ans[id].se)
ret.se--;
}
return ret;
}
int find_best(int n) {
for(int i = 0; i < n; i++)
have.pb(i);
while(av.size() < 500){
int l = 0, r = have.size(); // [l, r)
if(todo.size()){
l = lower_bound(all(have), todo.back().fi) - have.begin();
r = lower_bound(all(have), todo.back().se) - have.begin();
todo.pop_back();
}
while(r - l > 1){
int mid = (l + r) >> 1;
pair <int, int> ans = assk(have[mid]);
if(::ans[have[mid]].fi + ::ans[have[mid]].se == 0)
return have[mid];
if(::ans[have[mid]].fi + ::ans[have[mid]].se < mx){
l = mid;
break;
}
assert(ans.fi >= 0 && ans.se >= 0);
if(ans.fi && ans.se){
if(rng() % 2)
l = mid;
else
r = mid;
//todo.pb({have[mid], (r == have.size() ? maxn5 : have[r])});
}
else{
if(ans.se)
l = mid;
else
r = mid;
}
}
av.pb(have[l]);
//assert(!mark[l]);
mark[have[l]] = true;
auto ans = assk(have[l]);
if(ans.fi == -1)
return 0;
if(::ans[have[l]].fi == 0 && ::ans[have[l]].se == 0)
return have[l];
vector <int> tmp;
int keep = have[l];
for(auto u : have) if(u != keep)
tmp.pb(u);
have = tmp;
}
return 0;
}
