#include<bits/stdc++.h>
#include "richest.h"
using namespace std;
vector<int> lis[10];
vector<int> v1,v2,q,res;
int st[500010],pos=0,cnt=0;
void addquery(vector<int> v){
	st[pos]=cnt; pos++;
	int sz=v.size();
	for(int i=0;i<sz;i++)
		for(int j=i+1;j<sz;j++)
			v1.push_back(v[i]),v2.push_back(v[j]),cnt++;
}
bool ok[500010];
int richer(vector<int> v,int l){
	int sz=v.size();
	for(int i=0;i<sz;i++) ok[i]=1;
	for(int i=0;i<sz;i++)
		for(int j=i+1;j<sz;j++)
			if(res[l]==v[i]) ok[j]=0,l++;
			else ok[i]=0,l++;
	for(int i=0;i<sz;i++)
		if(ok[i]) return v[i];
}
void div(int id,int num,int sz1,int sz2){
    v1.clear(); v2.clear();
	int sz=lis[id].size();
	pos=0; cnt=0;
	for(int i=0;i<num*sz1;i+=sz1){
		q.clear();
		for(int j=0;j<sz1;j++)
			q.push_back(lis[id][i+j]);
		addquery(q);
	}
	for(int i=num*sz1;i<sz;i+=sz2){
		q.clear();
		for(int j=0;j<sz2;j++)
			q.push_back(lis[id][i+j]);
		addquery(q);
	}
	res=ask(v1,v2);
	int pos2=0;
	for(int i=0;i<num*sz1;i+=sz1){
		q.clear();
		for(int j=0;j<sz1;j++)
			q.push_back(lis[id][i+j]);
		lis[id+1].push_back(richer(q,st[pos2]));
		pos2++;
	}
	for(int i=num*sz1;i<sz;i+=sz2){
		q.clear();
		for(int j=0;j<sz2;j++)
			q.push_back(lis[id][i+j]);
		lis[id+1].push_back(richer(q,st[pos2]));
		pos2++;
	}
}
int smalldata(int n){
    lis[0].clear(); lis[1].clear();
    for(int i=0;i<n;i++) lis[0].push_back(i);
    div(0,1,n,0);
    return lis[1][0];
}
int bigdata(){
    for(int i=0;i<=8;i++) lis[i].clear();
    for(int i=0;i<1000000;i++) lis[0].push_back(i);
    div(0,500000,2,0);
    div(1,250000,2,0);
    div(2,125000,2,0);
    div(3,62500,2,0);
    div(4,20832,3,4);
    div(5,3471,6,7);
    div(6,5,18,19);
    div(7,1,lis[7].size(),0);
    return lis[8][0];
}
int richest(int N,int T,int S) {
    if(N!=1000000) return smalldata(N);
    else return bigdata();
}