#include "prize.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define ull unsigned long long
#define ll long long
#define rep(i,j,k) for(int i = (j);i <= (k);i++)
#define per(i,j,k) for(int i = (j);i >= (k);i--)
#define mkp make_pair
using namespace std;
mt19937 rnd(0);

template <class P>
void chkmax(P &x,P y){
	if(x < y) x = y;
}

pii qry(int p){
	vector <int> res = ask(p - 1);
	return mkp(res[0],res[1]);
}

int bas,answer,collect = 0;
void slv(int l,int r,int x,int y){
	if(l > r) return;
	int mid = (l + r) >> 1,pos = mid;
	while(pos <= r){
		pii temp = qry(pos);
		if(temp.first + temp.second != bas){
			if(temp.first + temp.second == 0){
				assert(!answer);
				answer = pos;
			}
			collect++;
			pos++;
			continue;
		}
		if(temp.first != x + pos - mid) slv(l,mid - 1,x,temp.second + pos - mid);
		if(temp.second != y) slv(pos + 1,r,temp.first,y);
		return;
	}
	slv(l,mid - 1,x,y + r - mid + 1);
}

int find_best(int n) {
	if(n <= 5000){
		rep(i,1,n){
			pii temp = qry(i);
			if(temp.first + temp.second == 0){
				return i - 1;
			}
		}
		assert(0);
	}
	bas = 0;
	rep(i,1,100){
		int p = rnd() % n + 1;
		pii temp = qry(p);
		chkmax(bas,temp.first + temp.second);
	}
	slv(1,n,0,0);
	if(collect != bas || !answer){
		ull msk = 1;
		ll cur = 1;
		while(cur <= 1e12){
			msk = msk * msk + 3 * msk + 5;
			cur++;
		}
		return msk % n;
	}
	return answer - 1;
}
/*
g++ prize.cpp grader.cpp -Wall -Wshadow -O2 -std=c++14 -Wno-unused-result -o grader.exe
*/