#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5;
int ans[MAX_N][2];
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];
}
return { ans[i][0], ans[i][1] };
}
void solve( int l, int r ) {
if ( found )
return;
if ( l > r )
return;
int mid = l + rand() % (r - l + 1) ;
auto [a, b] = askk( mid );
if ( a == 0 && b == 0 ) {
found = true;
pos = mid;
return;
}
if ( a < b ) {
solve( mid + 1, r );
solve( l, mid - 1 );
} else {
solve( l, mid - 1 );
solve( mid + 1, r );
}
}
int find_best( int n ) {
for( int i = 0; i < n; i++ )
ans[i][0] = ans[i][1] = -1;
solve( 0, n - 1 );
return pos;
}
