#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define en '\n'
const int N = 2e5 + 10;
int k,mx,kol;
vector <int> was[N];
bool u[N];
vector <pii> q;
/*
8
3 2 3 1 3 3 2 3
*/
vector <int> Ask(int x) {
if(u[x])return was[x];
u[x] = 1;
was[x] = ask(x);
return was[x];
}
int fin(int L,int R) {
if(L > R)return -1;
int l = L,r = R;
int mid = (l + r) / 2;
//cout << l << " " << r << " " << mid << endl;
kol++;
assert(kol <= 10000);
vector <int> resp = Ask(mid);
if(resp[0] + resp[1] == 0)return mid;
if(resp[0] + resp[1] != mx)q.pb(mp(mid,resp[0] + resp[1]));
int x = resp[0];
for(auto to : q) {
if(to.f < mid && to.s > resp[0] + resp[1])x--;
}
if(x != 0) {
int val = fin(L,mid - 1);
if(val != -1)return val;
}
int y = resp[1];
for(auto to : q) {
if(to.f > mid && to.s > resp[0] + resp[1])y++;
}
if(y != 0) {
int val = fin(mid + 1,R);
return val;
}
return -1;
}
int find_best(int pp) {
k = pp;
int m = (k - 1) / 2;
for(int i = 0;i < min(500,k);i++) {
vector <int> rep = ask(i);
mx = max(mx,rep[0] + rep[1]);
}
// mx = 3;
//cout << k << " ";
//cout << m << endl;
kol++;
vector <int> tt = Ask(m);
if(tt[0] + tt[1] != mx)q.pb(mp(m,tt[0] + tt[1]));
if(tt[0] + tt[1] == 0)return m;
if(tt[0] != 0) {
int val = fin(0,m - 1);
if(val != -1)return val;
}
return fin(m + 1,k - 1);
}
