#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;
ll suff[maxn];
ll pref[maxn];
ll res[maxn];
int find_best(int n)
{
for (int i = 0; i < n; i++)
{
suff[i] = 0;
pref[i] = 0;
res[i] = 0;
}
std::mt19937 rng(69420);
std::uniform_int_distribution<> dist(0, n - 1);
int br = 10000;
while (br--)
{
int pos = dist(rng);
std::vector <int> res = ask(pos);
pref[pos] += res[0];
suff[pos] += res[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;
return maxx;
}
