#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
mt19937 random_generator(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e5 + 3;
/*
int m;
int a[maxn];
vector <int> ask(int x)
{
vector <int> ans;
ans.resize(2);
ans[0] = ans[1] = 0;
for (int i = 0; i < x; i++)
if (a[i] < a[x])
ans[0]++;
for (int i = x + 1; i < m; i++)
if (a[i] < a[x])
ans[1]++;
return ans;
}
*/
int max_sum;
bool is[maxn];
void f(int l, int r, int how_many, int sub_l, int sub_r)
{
if (l > r)
return;
if (how_many == r - l + 1)
{
for (int i = l; i <= r; i++)
is[i] = true;
return;
}
if (how_many <= (r - l + 1) * 3 / 4)
return;
for (;;)
{
int idx = l + random_generator() % (r - l + 1);
auto curr = ask(idx);
if (curr[0] + curr[1] == max_sum)
{
curr[0] -= sub_l;
curr[1] -= sub_r;
is[idx] = true;
f(l, idx-1, idx - l - curr[0], sub_l, sub_r + curr[1]);
f(idx+1, r, r - idx - curr[1], sub_l + curr[0], sub_r);
break;
}
}
}
int find_best(int n)
{
for (int i = 1; i <= 100; i++)
{
int idx = random_generator() % n;
auto curr = ask(idx);
max_sum = max(max_sum, curr[0] + curr[1]);
}
f(0, n-1, n - max_sum, 0, 0);
for (int i = 0; i < n; i++)
if (!is[i])
{
auto curr = ask(i);
if (curr[0] + curr[1] == 0)
return i;
}
return -1;
}
/*
int main()
{
cin >> m;
for (int i = 0; i < m; i++)
cin >> a[i];
cout << find_best(m) << endl;
}
*/
