#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#include "prize.h"
using namespace std;
typedef long long ll;
int arr[200005];
int n;
int tmp[200005];
int maxx;
// 22
vector<pair<int, pair<int, int> > > vec;
void f(int l, int r, int tane){
//cout << "f(" << l << ", " << r << ", " << tane << ")" << endl;
if (tane <= 0) return;
if (l > r) return;
if (l == r){
if (tane == 0) return;
vector<int> ans = ask(l);
vec.pb(mp(arr[l], mp(ans[0], ans[1])));
}
int m = (l+r)/2;
vector<int> ans = ask(arr[r]);
while (ans[0] + ans[1] != maxx && m < r){
vec.pb(mp(arr[r], mp(ans[0], ans[1])));
r--;
ans = ask(arr[r]);
}
int msol = m-1;
vector<int> ans2 = ask(m);
while (ans[0] + ans[1] != maxx && m < r) {
vec.pb(mp(arr[m], mp(ans2[0], ans2[1])));
m++;
ans2 = ask(arr[m]);
}
f(m+1, r-1, ans2[1] - ans[1]);
f(l, msol, tane - ans2[1] + ans[1]);
}
int find_best(int size){
n = size;
for (int i = 0; i < size; i++) arr[i] = i;
srand(159);
maxx = 0;
for (int i = 0; i < min(20, n); i++){
vector<int> ans = ask(rand()%n);
maxx = max(ans[0] + ans[1], maxx);
}
//cout << "maxx: " << maxx << endl;
int l = 0;
int r = n-1;
vector<int> ans1 = ask(l);
vector<int> ans2 = ask(r);
while (ans1[0] + ans1[1] != maxx){
vec.pb(mp(l, mp(ans1[0], ans1[1])));
l++;
ans1 = ask(l);
}
while (ans2[0] + ans2[1] != maxx){
vec.pb(mp(r, mp(ans2[0], ans2[1])));
r--;
ans2 = ask(r);
}
f(l+1, r-1, ans2[0] - ans1[0]);
for (int i = 0; i < vec.size(); i++){
if (vec[i].second.first + vec[i].second.second == 0) return vec[i].first;
}
assert(0);
}
