#include<bits/stdc++.h>
#include "richest.h"
using namespace std;
mt19937 rd(5384);
int rg(int l,int r){return rd()%(r-l+1)+l;}
int f[8]={500000,250000,125000,62500,20832,3472,183,1};
int N;
vector<int>slv(int m,vector<int>d) {
    int n=d.size(),k=n/m,r=n%m;
    vector<int>qa,qb,qc,a,del(N);
    for(int i=0,l=0;i<m;i++) {
        int R=l+k+(i<r);
        for(int j=l;j<R;j++)for(int k=j+1;k<R;k++)qa.push_back(d[j]),qb.push_back(d[k]);
        l=R;
    }
    qc=ask(qa,qb);
    for(int i=0;i<qc.size();i++)if(qa[i]==qc[i])del[qb[i]]=1;else del[qa[i]]=1;
    for(int i:d)if(!del[i])a.push_back(i);else del[i]=0;
    return a;
}
int richest(int n,int T,int S) {
    vector<int>a(N=n);
    iota(a.begin(),a.end(),0);
    if(T==1)return slv(1,a)[0];
    for(int i=0;i<8;i++)a=slv(f[i],a);
    return a[0];
}