#include "bits/stdc++.h"
#include "prize.h"
#define MAXN 200009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x) cerr<< #x <<" = "<< x<<endl;
#define left cep
#define right sag
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<=b){a=b;return 1;}return 0;}
int n;
const int c=450;
//~ int arr[MAXN],query=0;
//~ int left[MAXN],right[MAXN],cnt[123];
//~ vector<int>ask(int x){
//~ query++;
//~ vector<int>res(2,0);
//~ assert(res[0]+res[1]==0);
//~ res[0]=left[x];
//~ res[1]=right[x];
//~ return res;
//~ }
int find_best(int N){
n=N;
int mx=0,who;
vector<int>res,tmp;
for(int i=0;i<min(n,500);i++){
res=ask(i);
if(res[0]+res[1]==0)
return i;
if(umax(mx,res[0]+res[1]))
who=i;
}who++;
while(who<n){
tmp=ask(who);
if(tmp[0]+tmp[1]==0)
return who;
if(tmp[0]+tmp[1]<mx){
who++;
continue;
}
while(who+c<n and ask(who+c)==tmp)
who+=c;
int st=who+1,en=n-1,pos=who;
while(st<=en){
int mid=(st+en)/2;
res=ask(mid);
if(res!=tmp)
en=mid-1;
else{
pos=mid;
st=mid+1;
}
}
who=pos+1;
}
return -1;
}
//~ int main(){
//~ freopen("file.in", "r", stdin);
//~ int N;
//~ scanf("%d",&N);
//~ for(int i=0;i<N;i++)
//~ scanf("%d",arr+i);
//~ for(int i=0;i<N;i++){
//~ for(int j=1;j<arr[i];j++)
//~ left[i]+=cnt[j];
//~ cnt[arr[i]]++;
//~ }
//~ memset(cnt,0,sizeof cnt);
//~ for(int i=N-1;i>=0;i--){
//~ for(int j=1;j<arr[i];j++)
//~ right[i]+=cnt[j];
//~ cnt[arr[i]]++;
//~ }
//~ int ans=find_best(N);
//~ assert(arr[ans]==1);
//~ printf("%d\n",ans);
//~ debug(query);
//~ return 0;
//~ }
