#include "prize.h"
#include <iostream>
#include <vector>
#include <random>
#include <ctime>
using namespace std;
const int maxn = 200005;
int N;
int max_result = 0;
int divide(int l, int r, int removed_from_left, int removed_from_right)
{
if (l > r)
{
return 0;
}
int mid = (l + r) / 2;
vector<int> curr;
while (mid <= r)
{
curr = ask(mid);
if (curr[0] + curr[1] == 0)
{
return mid;
}
if (curr[0] + curr[1] == max_result)
{
break;
}
++mid;
}
if (mid <= r)
{
curr[0] -= (removed_from_left - (mid - (l + r) / 2));
curr[1] -= removed_from_right;
if (curr[0] > 0)
{
int idx = divide(l, (l + r) / 2 - 1, removed_from_left, removed_from_right + curr[1] + (mid - (l + r) / 2));
if (idx != 0)
{
return idx;
}
}
if (curr[1] > 0)
{
int idx = divide(mid + 1, r, removed_from_left + curr[0] + (mid - (l + r) / 2), removed_from_right);
if (idx != 0)
{
return idx;
}
}
return 0;
}
else
{
mid = (l + r) / 2 - 1;
while (mid >= l)
{
curr = ask(mid);
if (curr[0] + curr[1] == 0)
{
return mid;
}
if (curr[0] + curr[1] == max_result)
{
return mid;
}
--mid;
}
if (mid == l - 1)
{
return 0;
}
curr[0] -= removed_from_left;
if (curr[0] > 0)
{
return divide(l, mid - 1, removed_from_left, removed_from_right + (r - mid));
}
return 0;
}
return 0;
}
int find_best(int n)
{
N = n;
for (int i = 1; i <= 450; ++i)
{
int idx = rand() % N;
vector<int> curr_res = ask(idx);
if (curr_res[0] + curr_res[1] == 0)
{
return idx;
}
max_result = max(max_result, curr_res[0] + curr_res[1]);
}
return divide(0, N - 1, 0, 0);
}
