#include "richest.h"
#include<bits/stdc++.h>
#define ll long long
#define ph emplace_back
#define rep(i,l,r) for(int i(l),i##end(r);i<=i##end;++i)
#define per(i,r,l) for(int i(r),i##end(l);i>=i##end;--i)
using namespace std;
std::vector <int> ask(std::vector <int> a, std::vector <int> b);
const int N=1e6+20,trans[10]={10000000 , 500000 , 250000 , 125000 , 62500 , 20833 , 3472 , 183 , 1};
int cnt[N],p[N],f[N];
void solve(int x,int y){
    int s=0; vector<int> a,b;
    rep(k,1,y-x%y){
        rep(i,s+1,s+x/y) rep(j,i+1,s+x/y) a.ph(p[i]),b.ph(p[j]);
        s+=x/y;
    }
    rep(k,1,x%y){
        rep(i,s+1,s+x/y+1) rep(j,i+1,s+x/y+1) a.ph(p[i]),b.ph(p[j]);
        s+=x/y+1;
    } vector<int> c=ask(a,b);
    
    rep(i,1,x) cnt[p[i]]=0;
    for(int x:c) cnt[x]++;
    int t=0;
    rep(i,1,(y-x%y)*(x/y)){
        if(cnt[p[i]]==x/y-1) f[++t]=p[i];
    }
    rep(i,(y-x%y)*(x/y)+1,x){
        if(cnt[p[i]]==x/y) f[++t]=p[i];
    }
    // printf("ask %d %d  %d\n",x,y,t);
    rep(i,1,y) p[i]=f[i];
    // printf("trans %d %d : %d %d\n",x,y,s,n);
}
int richest(int n,int T,int S){//变量名可以随意改！类型正确即可！
    rep(i,1,n) p[i]=i;
    if(n<=1000) solve(n,1);
    else{
        rep(k,1,8){
            if(trans[k]>=n) continue;
            solve(n,trans[k]),n=trans[k];
        }
    } return p[1];
}
// int n,a[N];
// vector<int> ask(vector<int> x,vector<int> y){
//     // cerr<<"ask "<<x.size()<<'\n';
//     // for(int v:x) cerr<<v<<' '; cerr<<'\n';
//     // for(int v:y) cerr<<v<<' '; cerr<<'\n';
//     if(x.size()!=y.size()){
//         puts("Wrong Ask");
//         exit(0);
//     }
//     int n=x.size()-1; vector<int> z;
//     rep(i,0,n) z.ph(a[x[i]]>a[y[i]]?x[i]:y[i]);
//     return z;
// }
// signed main(){
//     srand(time(0));
//     n=1000000;
//     rep(i,1,n) a[i]=i;//!
//     random_shuffle(a+1,a+n+1);
//     int k=1; rep(i,2,n) if(a[i]>a[k]) k=i;
//     // rep(i,1,n) cerr<<a[i]<<' '; cerr<<'\n';
//     cerr<<k<<'\n';
//     printf("%d\n",richest(n,0,0));
//     return 0;
// }//g++ -g my.cpp -o my -std=c++14 -O2   -Wall -Wextra -Wshadow -Wconversion