#include "prize.h"
/**
____ ____ ____ __________________ ____ ____ ____
||I || ||c || ||e || || || ||M || ||a || ||n ||
||__|| ||__|| ||__|| ||________________|| ||__|| ||__|| ||__||
|/__\| |/__\| |/__\| |/________________\| |/__\| |/__\| |/__\|
*/
#include <algorithm>
#include <iostream>
#include <vector>
#include <random>
#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;
int find_best(int n)
{
std::vector <int> pref(n , 0) , suff(n , 0) , res(n , 0);
std::mt19937 rng(69420);
std::vector <int> poss(n);
for (int i = 0; i < n; i++)
poss[i] = i;
std::shuffle(poss.begin(), poss.end(), rng);
for (int i = 0; i < std::min(n , 10000); i++)
{
int pos = poss[i];
std::vector <int> rr = ask(pos);
pref[pos] += rr[0];
suff[pos] += rr[1];
}
ll ss = 0;
for (int i = 0; i < n; i++)
{
res[i] = ss;
ss += suff[i];
}
ss = 0;
for (int i = n - 1; i >= 0; i--)
{
res[i] = ss;
ss += pref[i];
}
for (int i = 0; i < n; i++)
res[i] = pref[i] + suff[i];
int maxx = 0;
for (int i = 1; i < n; i++)
if (res[i] > res[maxx])
maxx = i;
std::vector <int> pp;
for (int i = 0; i < n; i++)
if (res[i] == res[maxx])
pp.push_back(i);
std::shuffle(pp.begin(), pp.end(), rng);
return pp[0];
}
