#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define pii pair<int,int>
const int maxn=2e5+5;
int dp[maxn][3],ans;
bool tr;
void f(int l,int r){
if(dp[l][0] == -1 and dp[l][1]==-1){
vector<int> p = ask(l);
dp[l][0]=p[0];
dp[l][1]=p[1];
}
if(dp[l][0]+dp[l][1]==0){
ans=l,tr=1;
return;
}
if(dp[r][0]==-1 and dp[r][1]==-1){
vector<int> p = ask(r);
dp[r][0] = p[0];
dp[r][1] = p[1];
}
if(dp[r][0]+dp[r][1]==0){
ans = r,tr=1;
return;
}
if(dp[l][0]+dp[l][1] == dp[r][0]+dp[r][1] and dp[r][0]-dp[l][0]==0) return;
if(r-l+1 <= 2) return;
f(l+1,(l+r)/2);
if(tr) return;
f((l+r)/2+1,r-1);
if(tr) return;
}
int find_best(int n){
memset(dp,-1,sizeof(dp));
f(0,n-1);
return ans;
}
