//Sylwia Sapkowska
#include <bits/stdc++.h>
#include "prize.h"
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
typedef pair<int, int> T;
// mt19937 rng(chrono::steady_clock().time_since_epoch().count());
// int p(int a, int b){
// return a + rng()%(b-a+1);
// }
int find_best(int n) {
if (n <= 5000){
for (int i = 1; i<=n; i++){
auto x = ask(i-1);
if (max(x[0], x[1]) == 0){
return i-1;
}
}
assert(false);
}
//duzo elementow
int curr = 0, pos = 0;
for (int rep = 1; rep <= 470; rep++){
auto x = ask(rep-1);
if (max(x[0], x[1]) == 0){
return rep-1;
}
int s = x[0] + x[1];
if (s > curr){
curr = s;
pos = rep;
}
}
debug(pos);
int left = n-curr; //tyle nie najgorszych elementow
//powinno byc left <= 500
vector<int>where, pref(n+1);
vector<bool>vis(n+1);
for (int i = 1; i<=left; i++){
where.clear();
pref.assign(n+1, 0);
for (int rep = 0; rep <= n; rep++){
if (!vis[rep]){
where.emplace_back(rep);
}
if (vis[rep]) pref[rep]++;
if (rep) pref[rep] += pref[rep-1];
}
int l = 1, r = (int)where.size()-1;
int ans = -1;
while (r >= l){
int m = (l+r)/2;
auto x = ask(where[m]-1);
if (x[0] + x[1] == 0) return where[m]-1;
if (x[0] + x[1] < pos){
ans = m;
break;
}
//najgorszy
int left = pref[where[m]];
if (x[0] == left){
l = m+1;
} else {
r = m-1;
}
}
assert(ans != -1);
vis[ans] = 1;
debug(ans);
}
assert(false);
}
