#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5;
int ans[MAX_N][2];
int n, t;
bool found = false;
int pos;
pair<int, int> askk( int i ) {
if ( i < 0 || i >= n )
return { -1, -1 };
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] };
}
int findMid( int &l, int &r ) {
if ( l > r )
return 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--;
r = mid;
return findMid( l, r );
}
return mid;
}
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 lmid = (l + r) / 2;
while ( lmid >= l && askk( lmid ).first + askk( lmid ).second != t && !found )
lmid--;
int tlmid = askk( lmid ).first;
int rmid = (l + r) / 2;
while ( rmid <= r && askk( rmid ).first + askk( rmid ).second != t && !found )
rmid++;
int trmid = askk( rmid ).first;
solve( l, lmid, tleft, tlmid );
solve( rmid + 1, r, trmid, tright );
}
int find_best( int N ) {
n = N;
for ( int i = 0; i < n; i++ )
ans[i][0] = ans[i][1] = -1;
t = 0;
for ( int i = 0; i < 100; 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;
}
