#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
int n, threshold, fir, sec, counter, globalMin;
int finalReturn = -1;
bool checked[300000];
int firr[300000];
vector<pair<int, int> > regions;
bool isLolly(int x) {
vector<int> v = ask(x);
checked[x] = true;
if (v[0] + v[1] == 0)
{
finalReturn = x;
return true;
}
if (v[0] + v[1] > n/2)
{
fir = v[0];
firr[x] = fir;
sec = v[1];
return true;
}
return false;
}
int stage2(int firstPos, int lastPos, int bigsBeforeFirst, int bigsBeforeLast) {
//cout << "In stage 2 from " << firstPos << " to " << lastPos << "\n";
int p = firstPos;
while (p + 10 < lastPos)
{
while (!checked[p] and !isLolly(p))
{
p++;
}
if (firr[p] > bigsBeforeFirst)
{
for (int i = firstPos; i <= p; i++)
{
if (!checked[i])
{
isLolly(i);
}
}
bigsBeforeFirst = firr[p];
firstPos = p;
}
p += 10;
}
for (int i = p; i <= lastPos; i++)
{
if (!checked[i])
{
isLolly(i);
}
}
return finalReturn;
}
int find_best(int ln) {
n = ln;
if (n <= 5000)
{
for (int i = 0; i < n; i++)
{
vector<int> v = ask(i);
if (v[0] == 0 and v[1] == 0)
{
return i;
}
}
}
fir = 1;
sec = 1;
counter = 0;
/*while (fir + sec < n/2)
{
vector<int> v = ask(counter);
fir = v[0];
sec = v[1];
if (fir + sec == 0)
{
return counter;
}
counter++;
}
threshold = fir + sec;
globalMin = counter; */
int prevFirsts = 0;
int prevMin = 0;
while (counter + 50 < n)
{
while (!isLolly(counter))
{
counter++;
}
if (finalReturn > 0)
{
return finalReturn;
}
if (firr[counter] > prevFirsts)
{
int x = stage2(prevMin, prevMin + 50, prevFirsts, firr[counter]);
if (x >= 0) {
return x;
}
}
prevFirsts = firr[counter];
prevMin = counter;
counter += 50;
}
for (int i = counter; i < n; i++)
{
vector<int> v = ask(i);
checked[i] = true;
if (v[0] + v[1] == 0)
{
return i;
}
}
return finalReturn;
}
