#include <bits/stdc++.h>
#include "prize.h"

using namespace std;

const int N = 2e5 + 10;

vector<int> ans[N];

vector<int> query(int i)
{
	if (!ans[i].empty()) return ans[i];
	ans[i] = ask(i);
	return ans[i];
}

namespace bit
{
	int n, c[N];
	void init(int n)
	{
		bit::n = n;
		for (int i = 1; i <= n; i++) c[i] = 0;
	}
	
	void add(int pos)
	{
		pos++;
		for (; pos <= n; pos += pos & -pos) c[pos]++;	
	}
	
	int qsum(int pos)
	{
		pos++;
		int res = 0;
		for (; pos; pos -= pos & -pos) res += c[pos];
		return res;
	}
	
	int query(int l, int r)
	{
		if (l > r) return 0;
		return qsum(r) - qsum(l - 1);
	}
};

int vmax;

int find(int l, int r, int lsub, int rsub)
{
	if (l > r) return -1;
	int mid = (l + r) >> 1;
	vector<int> res;
	for (int t = 1, sgn = 1; mid >= l && mid <= r; mid += sgn * t, t++, sgn = -sgn)
	{
		auto a = query(mid);
		if (a[0] + a[1] == 0) return mid;
		if (a[0] + a[1] == vmax) 
		{
			res = a;
			break;
		}
		if (!bit::query(mid, mid)) bit::add(mid);
	}
	if (res.empty()) return -1;
	if (res[0] - bit::query(l, mid - 1) > lsub) 
	{
		int c = find(l, mid - 1, lsub, res[1]);
		if (c != -1) return c;
	}
	if (res[1] - bit::query(mid + 1, r) > rsub)
	{
		int c = find(mid + 1, r, res[0], rsub);
		if (c != -1) return c;
	}
	return -1;
}

int find_best(int n)
{
	// find vmax
	bit::init(n);
	set<int> s;
	int i;
	for (i = 0; i < min(n, 472); i++)
	{
		auto a = query(i);
		int sum = a[0] + a[1];
		s.insert(sum);
		if (sum == 0) return i;
		if (sum > 26) break;
	}
	for (int x : s) vmax = max(vmax, x);
	for (int j = 0; j <= min(i, min(n, 472)); j++)
	{
		auto a = query(i);
		if (a[0] + a[1] < vmax) bit::add(i);
	}
	return find(0, n - 1, 0, 0);
}

//signed main()
//{
//	int n; cin >> n;
//	cout << find_best(n);
//}