#include "prize.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define Mp make_pair
#define endl "\n"
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int N = 1e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
int n;
map < int, vector < int > > mp;
inline vector < int > Ask(int pos)
{
if(mp.find(pos) != mp.end())
{
return mp[pos];
}
return mp[pos] = ask(pos);
}
int FindRight(int p);
int FindLeft(int p)
{
vector < int > V = Ask(p);
int Me = V[0] + V[1];
if(V[0] == 0) return -1;
int l = 0, r = p;
while(r - l > 1)
{
int mid = (l + r) >> 1;
vector < int > now = Ask(mid);
int you = now[0] + now[1];
if(Me > you)
{
l = mid;
continue;
}
if(Me == you)
{
if(V[0] == now[0])
{
r = mid;
}
else
{
l = mid;
}
continue;
}
int id = mid;
while(id < p && Ask(id)[0] + Ask(id)[1] >= Me)
{
id = FindRight(id);
}
if(id == p)
{
r = mid;
}
else
{
l = mid;
}
}
return l;
}
int FindRight(int p)
{
vector < int > V = Ask(p);
int Me = V[0] + V[1];
if(V[1] == 0) return -1;
int l = p, r = n - 1;
while(r - l > 1)
{
int mid = (l + r) >> 1;
vector < int > now = Ask(mid);
int you = now[0] + now[1];
if(Me > you)
{
r = mid;
continue;
}
if(Me == you)
{
if(V[1] == now[1])
{
l = mid;
}
else
{
r = mid;
}
continue;
}
int id = mid;
while(id > p && Ask(id)[0] + Ask(id)[1] >= Me)
{
id = FindLeft(id);
}
if(id == p)
{
l = mid;
}
else
{
r = mid;
}
}
return r;
}
int find_best(int _n)
{
n = _n;
int p = 0;
while(Ask(p)[0] + Ask(p)[1])
{
p = FindRight(p);
}
return p;
}
