// 12:10
#include "prize.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
//#define ll __int128
#define ll long long
//#define int long long
#define LEFT(a) ((a)<<1)
#define RIGHT(a) (LEFT(a) + 1)
#define MID(a,b) ((a+b)>>1)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define y1 y122
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
/*
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target ("avx2")
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/STACK: 20000000005")
*/
using namespace std;
const int N = 200005;
int a[N], b[N], F[N];
void mak (int x){
if (F[x])
return;
vector < int > res = ask (x);
a[x] = res[0];
b[x] = res[1];
F[x] = 1;
}
int m;
vector < int > solve (int l, int r, int L, int R){
vector < int > ans;
if (l > r || L > R)
return ans;
int mid = l + r >> 1;
while (mid >= l){
mak (mid);
if (a[mid] + b[mid] == m)
break;
ans.pb (mid);
mid--;
}
int le = mid-1;
int ri = (l+r>>1)+1;
int LL = L-1;
if (mid >= l)
LL = a[mid];
int RR = LL + 1 + (int)ans.size();
vector < int > A = solve (l, le, L, LL);
vector < int > B = solve (ri, r, RR, R);
for (int x : A)
ans.pb (x);
for (int x : B)
ans.pb (x);
return ans;
}
int find_best(int n) {
m = min (n-1, 446);
vector < int > V;
for (int i = 0; i < n; i++)
V.pb (i);
for (int i = 0; i < 20; i++)
random_shuffle(V.begin(), V.end());
int nn = 0;
for (int i, x = 0; x <= m; x++){
i = V[x];
mak (i);
nn = max (nn, a[i] + b[i]);
if (nn > 25)
break;
}
m = nn;
vector < int > ans = solve (0, n-1, 1, m);
for (int x : ans){
mak (x);
if (a[x] + b[x] == 0)
return x;
}
}
