#include <bits/stdc++.h>
using namespace std;
#include "prize.h"
//vector<int> ask(int i);
vector<int> series;
int N;
vector<int> memo[200001];
vector<int> query(int i) {
if(i < 0 or i > N-1)
return {0, 0};
if(memo[i][0] != -1) return memo[i];
else return memo[i] = ask(i);
}
/*int find(int l, int r) {
if(l == r) return l;
int mid = (l+r)/2;
vector<int> q = query(mid);
if(q[0] == 0 and q[1] == 0) return mid;
else if(q[0] == 0) return find(mid+1, r);
return find(l, mid-1);
}*/
bool bigger(int i, int j) {
vector<int> q1 = query(i);
vector<int> q2 = query(j);
return q1[0] + q1[1] < q2[0] + q2[1];
}
int MINI = -1;
bool ok(int i) {
vector<int> q = query(i);
return MINI == q[0] + q[1];
}
int L(int i) {
vector<int> q = query(i);
return q[0];
}
int R(int i) {
vector<int> q = query(i);
return q[1];
}
int S(int i) {
vector<int> q = query(i);
return q[0] + q[1];
}
int find(int l, int r) {
if(l == r) return l;
int rB = R(r+1);
int lB = L(l-1);
int mid = (l + r) / 2;
vector<int> q = query(mid);
vector<int> candidates = {mid};
if(R(mid) - rB != 0) candidates.push_back(find(mid+1, r));
if(L(mid) - lB != 0) candidates.push_back(find(l, mid-1));
int ans = -1;
int mini = N+1;
for(int i : candidates) if(S(i) < mini) mini = S(i), ans = i;
return ans;
}
int solve() {
/*if(N <= 5000) {
for(int i = 0; i < N; i++) {
vector<int> q = query(i);
if(q[0] + q[1] == 0) return i;
}
}*/
return find(0, N-1);
}
int find_best(int n) {
series.clear();
long long cur = 1;
series.push_back(cur);
while(cur * cur + 1LL < (long long)n) {
series.push_back(cur * cur + 1LL);
cur = cur * cur + 1LL;
}
N = n;
for(int i = 0; i < N; i++) memo[i] = {-1, -1};
//return find(0, N-1);
return solve();
}
