// Oh damn! Suddenly you're free to fly...
#include<bits/stdc++.h>
#include "prize.h"
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
int n;
int dp[maxn];
bool Big(int x){
return dp[x] >= n;
}
void go(int l, int r){
if(r-l <= 0)
return;
int mid = (l+r) >> 1;
int pos = mid;
while(pos < r){
vector<int> v = ask(pos);
if(!Big(v[0] + v[1])){
if(v[0] + v[1] == 0)
throw pos;
pos++;
}
else{
if(v[1] > 0)
go(pos + 1, r);
break;
}
}
pos = mid-1;
while(pos >= l){
vector<int> v = ask(pos);
if(!Big(v[0] + v[1])){
if(v[0] + v[1] == 0)
throw pos;
pos--;
}
else{
if(v[0] > 0)
go(l, pos);
break;
}
}
}
int find_best(int n){
dp[1] = 1;
for(int i = 1; i < maxn; i++){
if(1ll * i * i < maxn){
for(int j = i*i + 1; j < maxn; j++){
dp[j] = max(dp[j], dp[i] + j);
}
}
}
::n = n;
try{
go(0, n);
}
catch(int ans){
return ans;
}
assert(0);
}
