#include <bits/stdc++.h>
#define N 200050
#include "prize.h"
using namespace std;
int n, v[N], maior, ans, raiz;
vector<int> dp[N];
vector<int> aski(int x)
{
if(!dp[x].empty()) return dp[x];
return dp[x] = ask(x);
}
int solve(int a, int b)
{
int mid = (a + b)/2;
int l = max(a + 1, mid - 250), r = min(b - 1, mid + 250);
vector<int> esq = aski(a), dir = aski(b);
if(esq[0] + esq[1] == 0) return a;
if(dir[0] + dir[1] == 0) return b;
if(b - a < 2) return -1;
for(int p = l; p <= r; p++)
{
vector<int> aux = aski(p);
if(aux[0] + aux[1] == 0) return p;
if(aux[0] + aux[1] == maior)
{
int cnt_esq = aux[0] - esq[0];
int cnt_dir = aux[1] - dir[1];
int solve_esq = -1, solve_dir = -1;
if(cnt_esq) solve_esq = solve(a, p);
if(cnt_dir) solve_dir = solve(p, b);
return max(solve_dir, solve_esq);
}
}
return -1;
}
int find_best(int n)
{
int st = 0, en = n - 1;
raiz = sqrt(n) + 1;
for(int i = 0; i < 500; i++)
{
vector<int> aux = aski(i);
if(aux[0] + aux[1] > maior)
{
maior = aux[0] + aux[1];
st = i;
}
if(aux[0] + aux[1] == 0) return i;
}
for(int i = n - 1, cnt = 0; cnt < 500; cnt ++)
{
vector<int> aux = aski(i);
if(aux[0] + aux[1] == maior)
{
en = i;
break;
}
if(aux[0] + aux[1] == 0) return i;
}
return solve(st, en);
}
