#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
// int N;
// vector <int> nums;
// vector <int> ask(int i) {
// vector <int> ans(2, 0);
// for (int j = 0; j < i; j++) {
// if (nums[j] > nums[i])
// ans[0]++;
// }
// for (int j = i+1; j < N; j++) {
// if (nums[j] > nums[i])
// ans[1]++;
// }
// return ans;
// }
int rng(int i) {
return rand() % i;
}
int find_best(int n) {
srand(time(0));
vector <int> guesses(n);
for (int i = 0; i < n; i++)
guesses[i] = i;
random_shuffle(guesses.begin(), guesses.end(), rng);
int cnt = 0;
int lo = 0, hi = n-1;
for (int i = 0; i < n && cnt < 10000; i++) {
if (guesses[i] < lo || guesses[i] > hi)
continue;
cnt++;
auto res = ask(guesses[i]);
if (res[0] + res[1] == 0)
return guesses[i];
if (res[0] + res[1] == 1) {
if (res[0] == 1)
hi = guesses[i] - 1;
else
lo = guesses[i] + 1;
if (lo == hi)
return lo;
}
if (cnt == 10000)
return guesses[i+1];
}
return 0;
}
// int main() {
// cin >> N;
// nums.resize(N+1);
// for (int i = 0; i < N; i++)
// cin >> nums[i];
// find_best(N);
// }
