#include <bits/stdc++.h>
#include "prize.h"
#define endl '\n'
using namespace std;
const int MAX = (2e5) + 5;
vector<int> a[MAX];
bool d[MAX];
int find_best(int n)
{
random_device rd;
mt19937 rng(rd());
uniform_int_distribution<int> dist(0, n - 1);
int bx = 0, x = 0, id;
for (int i = 0; i < 20; i++)
{
id = dist(rng);
if (!d[id])
{
a[id] = ask(id);
d[id] = 1;
bx = max(bx, a[id][0] + a[id][1]);
}
}
int ans = -1;
for (int i = 0; i < n; i++)
{
if (!d[i])
{
a[i] = ask(i);
d[i] = 1;
}
x = a[i][0] + a[i][1];
if (x == bx)
{
int l = i, r = n, mid;
while (r - l > 1)
{
mid = l + (r - l) / 2;
if (!d[mid])
{
a[mid] = ask(mid);
d[i] = 1;
}
if (a[i][0] == a[mid][0] && a[i][1] == a[mid][1])
l = mid;
else
r = mid;
}
i = l;
}
else if (x == 0)
{
ans = i;
break;
}
}
return ans;
}
