#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<int> big;
pair<int, vector<int>> differentRight(int a, int b, vector<int> inf)
{
int res = -1;
vector<int> rinf;
while (a <= b)
{
int mid = (a + b) / 2;
vector<int> cinf = ask(mid);
if (cinf == inf)
{
a = mid + 1;
} else
{
res = mid;
rinf = cinf;
b = mid - 1;
}
}
return {res, rinf};
}
pair<int, vector<int>> differentLeft(int a, int b, vector<int> inf)
{
int res = -1;
vector<int> rinf;
while (a <= b)
{
int mid = (a + b) / 2;
vector<int> cinf = ask(mid);
if (cinf == inf)
{
b = mid - 1;
} else
{
res = mid;
rinf = cinf;
a = mid + 1;
}
}
return {res, rinf};
}
int find_best(int N) {
n = N;
if (n <= 5000)
{
int res = -1;
for (int i = 0; i < n; i++)
{
vector<int> v = ask(i);
if (v[0] == 0 && v[1] == 0) res = i;
}
return res;
}
vector<int> needed = {0, 0};
big = {0, 0};
vector<int> inf;
int cur = 0;
inf = ask(cur);
if (inf[0] + inf[1] > big[0] + big[1]) big = inf;
if (inf == needed) return cur;
for (int i = 0; i < 4; i++)
{
auto p1 = differentRight(cur, n - 1, inf);
if (p1.first == -1) break;
cur = p1.first;
inf = p1.second;
if (inf == needed) return cur;
if (inf[0] + inf[1] > big[0] + big[1]) big = inf;
}
int sum = big[0] + big[1];
vector<vector<int>> infAt(n, vector<int>(2));
for (int i = 0; i < n; i += 150)
{
infAt[i] = ask(i);
if (infAt[i] == needed) return i;
}
for (int i = 0; i + 150 < n; i += 150)
{
int l = i;
int r = i + 150;
if (infAt[l] == needed) return l;
if (infAt[r] == needed) return r;
if (infAt[l][0] + infAt[l][1] == infAt[r][0] + infAt[r][1])
{
if (infAt[l][1] - infAt[r][1] == 0) continue;
}
if (infAt[l][0] + infAt[l][1] == sum)
{
auto p1 = differentRight(l, r, infAt[l]);
l = p1.first;
if (l == -1) continue;
infAt[l] = p1.second;
}
if (infAt[r][0] + infAt[r][1] == sum)
{
auto p2 = differentLeft(l, r, infAt[r]);
r = p2.first;
if (r == -1) continue;
infAt[r] = p2.second;
}
if (l != -1 && infAt[l] == needed) return l;
if (r != -1 && infAt[r] == needed) return r;
if (l == -1 || r == -1) continue;
if (r - l <= 1) continue;
if ((infAt[l][0] + infAt[l][1] == infAt[r][0] + infAt[r][1] && infAt[l][1] - infAt[r][1] > 0) || (infAt[l][0] + infAt[l][1] != infAt[r][0] + infAt[r][1]))
{
for (int j = l + 1; j < r; j++)
{
vector<int> cinf = ask(j);
if (cinf[0] == 0 && cinf[1] == 0) return j;
}
}
}
for (int i = 0; i < n; i += 150)
{
if (i + 150 >= n)
{
for (int j = i + 1; j < n; j++)
{
vector<int> cinf = ask(j);
if (cinf == needed) return j;
}
}
}
return 0;
}
