#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,int gr) {
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] < gr)q.pb(mp(mid,resp[0] + resp[1]));
int x = resp[0];
int kk = min(gr,resp[0] + resp[1]);
for(auto to : q) {
if(to.f < mid && to.s < resp[0] + resp[1])x--;
}
if(x != 0) {
int val = fin(L,mid - 1,kk);
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,kk);
return val;
}
return -1;
}
int find_best(int pp) {
k = pp;
int m = (k - 1) / 2;
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,tt[0] + tt[1]);
if(val != -1)return val;
}
int ff = fin(m + 1,k - 1,tt[0] + tt[1]);
//assert(ff != -1);
return ff;
}
