/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/IOI17_prize
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
#include <string.h>
#include <set>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define sz(x) (int)(x).size()
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 200007
#define MAXE 100007
const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
int x, y;
int val;
int visited;
bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
struct EDGE {
int from, to;
ll weight;
bool operator<(EDGE other) const { return weight < other.weight; }
};
bool debug=false;
/** since cnt(t) > cnt(t-1)^2 and cnt(1) = 1, number of prize is more than 1, 2^1, 2^2, 2^3, ...
* which means the sum of # of more expensive items is unique since the sum of all prize <t is less than cnt(t)
* make totMore = a[0] + a[1]
* then for i and j, if totMore[i] == totMore[j], then they are the same type
* we can divide and conquer to find the higher prize item (until totMore == 0)
* for each totMore, if a[0] on the left is the same the a[0] here, then there is no more expensive between those two
*/
#include "prize.h"
int ans=-1;
set<int> cnt[MAXV];
int leMore[MAXV];
bool divRcon(int l, int r) {
if(l>r) return false;
int m = (l+r)/2;
auto a = ask(m);
int totMore = a[0] + a[1];
leMore[m] = a[0];
if(totMore==0) {ans = m; return true;}
auto it = cnt[totMore].insert(m).ff;
if(it==cnt[totMore].begin())
if(divRcon(l,m-1)) return true;
else if(leMore[*prev(it)] != leMore[*it])
if(divRcon(l, m-1)) return true;
if(next(it)==cnt[totMore].end())
if(divRcon(m+1,r)) return true;
else if(leMore[*next(it)] != leMore[*it])
if(divRcon(m+1, r)) return true;
return false;
}
int find_best(int n) {
divRcon(0,n-1);
return ans;
}
