#include "prize.h"
/**
____ ____ ____ __________________ ____ ____ ____
||I || ||c || ||e || || || ||M || ||a || ||n ||
||__|| ||__|| ||__|| ||________________|| ||__|| ||__|| ||__||
|/__\| |/__\| |/__\| |/________________\| |/__\| |/__\| |/__\|
*/
#include <algorithm>
#include <iostream>
#include <vector>
#include <random>
#include <map>
#define maxn 200005
#define PB push_back
#define X first
#define Y second
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;
typedef std::pair<int, ll> pil;
typedef std::pair<ll, int> pli;
typedef long double ld;
std::map <int , std::vector <int>> store;
std::vector <int> myq(int x)
{
if (store.count(x))
return store[x];
return store[x] = ask(x);
}
int find_best(int n)
{
int maxx = -1;
for (int i = 0; i < std::min(n , 450); i++)
{
std::vector <int> cc = myq(i);
if(cc[0] + cc[1] == 0)
return i;
maxx = std::max(cc[0] + cc[1] , maxx);
}
for (int i = std::min(450 , n); i < n; i++)
{
std::vector <int> cc = myq(i);
if (cc[0] + cc[1] == 0)
return i;
if (cc[0] + cc[1] != maxx)
continue;
int l = i + 1 , r = n - 1;
while (l < r)
{
int mid = (l + r) / 2;
std::vector <int> ccc = myq(mid);
if (ccc[0] + ccc[1] == 0)
return mid;
if (ccc[0] + ccc[1] < maxx)
r = mid;
else
{
if (cc[1] > ccc[1])
r = mid - 1;
else
l = mid + 1;
}
}
std::vector <int> pom = myq(l);
if (pom[0] + pom[1] == 0)
return l;
i = l;
}
return n - 1;
}
