#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5;
int ans[MAX_N][2];
int t;
bool found = false;
int pos;
pair<int, int> askk( int i ) {
if ( ans[i][0] == -1 ) {
auto x = ask( i );
ans[i][0] = x[0];
ans[i][1] = x[1];
}
if ( ans[i][0] + ans[i][1] == 0 ) {
found = true;
pos = i;
}
return { ans[i][0], ans[i][1] };
}
void solve( int l, int r, int tleft, int tright ) {
if ( tleft == tright )
return;
if ( found )
return;
if ( l > r )
return;
//printf( "%d %d\n", l, r );
int mid = (l + r) / 2;
while ( mid <= r && askk( mid ).first + askk( mid ).second != t && !found )
mid++;
if ( mid >= r ) {
mid--;
while ( mid >= l && askk( mid ).first + askk( mid ).second != t && !found )
mid--;
if ( mid < l )
return;
}
int tmid = askk( mid ).first;
solve( l, mid, tleft, tmid );
solve( mid + 1, r, tmid, tright );
}
int find_best( int n ) {
for( int i = 0; i < n; i++ )
ans[i][0] = ans[i][1] = -1;
t = 0;
for ( int i = 0; i < 10; i++ ) {
int p = rand() % n;
t = max( t, askk( p ).first + askk( p ).second );
}
solve( 0, n - 1, 0, t );
// for ( int i = 0; i < n; i++ )
// askk( i );
return pos;
}
