#include<bits/stdc++.h>
#include "richest.h"
using namespace std;
const int N=1e6+5;
int n,A[N],Cnt;
int num[35]={500000,250000,125000,62500,20834,3472,182,1};
// inline vector<int> ask(vector<int>a,vector<int>b){
//     vector<int>c;
//     for(int i=0;i<a.size();++i){
//         int x=a[i],y=b[i];
//         // if(x>n||y>n||x<0||y<0)cerr<<x<<" "<<y<<"\n";
//         c.push_back(A[x]>A[y]?x:y);
//     }
//     Cnt+=c.size();
//     return c;
// }
int richest(int n,int s,int t){
    vector<int>a,b,c;
    if(n==1000){
        for(int i=0;i<n;++i){
            for(int j=i+1;j<n;++j)a.push_back(i),b.push_back(j);
        }
        c=ask(a,b);
        vector<int>rd(n,0);
        for(int i=0;i<499500;++i){
            if(c[i]==a[i])++rd[b[i]];
            else ++rd[a[i]];
        }
        for(int i=0;i<n;++i)if(!rd[i])return i;
    }
    vector<int>p(n);
    for(int i=0;i<n;++i)p[i]=i;
    for(int i=0;i<8;++i){
        a.clear(),b.clear();
		for(int j=0;j<p.size();++j){
			for(int k=j%num[i];k<j;k+=num[i])if(j!=k)a.push_back(p[j]),b.push_back(p[k]);
		}
        vector<int>c=ask(a,b),q,rd(n,0);
        for(int j=0;j<c.size();++j){
            if(c[j]==a[j])++rd[b[j]];
            else ++rd[a[j]];
        }
        for(int j=0;j<p.size();++j)if(!rd[p[j]])q.push_back(p[j]);
        p=q;
	}
    return p[0];
    // a.clear(),b.clear();for(int i=0;i<1000000;i+=2)a.push_back(p[i]),b.push_back(p[i+1]);
    // p=ask(a,b);
    // a.clear(),b.clear();for(int i=0;i<500000;i+=2)a.push_back(p[i]),b.push_back(p[i+1]);
    // p=ask(a,b);
    // a.clear(),b.clear();for(int i=0;i<250000;i+=2)a.push_back(p[i]),b.push_back(p[i+1]);
    // p=ask(a,b);
    // a.clear(),b.clear();for(int i=0;i<125000;i+=2)a.push_back(p[i]),b.push_back(p[i+1]);
    // p=ask(a,b);

    // {
    //     a.clear(),b.clear();
    //     int k0=p[62499];
    //     for(int i=0;i<62499;i+=3){
    //         a.push_back(p[i]),b.push_back(p[i+1]);
    //         a.push_back(p[i+1]),b.push_back(p[i+2]);
    //         a.push_back(p[i+2]),b.push_back(p[i]);
    //     }
    //     c=ask(a,b);
    //     vector<int>rd(n,0),q;
    //     for(int i=0;i<62499;++i)++rd[c[i]];
    //     for(int i=0;i<62499;++i)if(rd[p[i]]==2)q.push_back(p[i]);
    //     p=q,p.push_back(k0);
    // }

    // {
    //     a.clear(),b.clear();
    //     int k0=p[20833],k1=p[20832];
    //     for(int i=0;i<20832;i+=6){
    //         for(int j=0;j<6;++j){
    //             for(int k=j+1;k<6;++k)a.push_back(p[i+j]),b.push_back(p[i+k]);
    //         }
    //     }
    //     a.push_back(k0),b.push_back(k1);
    //     c=ask(a,b);
    //     vector<int>rd(n,0),q;
    //     for(int i=0;i<52080;++i)++rd[c[i]];
    //     for(int i=0;i<20832;++i)if(rd[p[i]]==5)q.push_back(p[i]);
    //     p=q,p.push_back(c[52080]);
    // }

    // {
    //     a.clear(),b.clear();
    //     for(int i=0;i<3173;i+=19){
    //         for(int j=0;j<19;++j){
    //             for(int k=j+1;k<19;++k)a.push_back(p[i+j]),b.push_back(p[i+k]);
    //         }
    //     }
    //     for(int i=3173;i<3473;i+=20){
    //         for(int j=0;j<20;++j){
    //             for(int k=j+1;k<20;++k)a.push_back(p[i+j]),b.push_back(p[i+k]);
    //         }
    //     }
    //     c=ask(a,b);
    //     vector<int>rd(n,0),q;
    //     for(int i=0;i<(int)c.size();++i)++rd[c[i]];
    //     for(int i=0;i<3173;++i)if(rd[p[i]]==18)q.push_back(p[i]);
    //     for(int i=3173;i<3473;++i)if(rd[p[i]]==19)q.push_back(p[i]);
    //     p=q;
    // }

    // {
    //     a.clear(),b.clear();
    //     for(int j=0;j<182;++j){
    //         for(int k=j+1;k<182;++k)a.push_back(p[j]),b.push_back(p[k]);
    //     }
    //     c=ask(a,b);
    //     vector<int>rd(n,0),q;
    //     for(int i=0;i<(int)c.size();++i)++rd[c[i]];
    //     for(int i=0;i<182;++i)if(rd[p[i]]==181)q.push_back(p[i]);
    //     return q[0];
    // }
}
// signed main(){
//     freopen("in.in","r",stdin);
//     n=1e6;
//     for(int i=0;i<n;++i){
//         cin>>A[i];
//         if(A[i]==n)cout<<i<<"\n";
//     }
//     cout<<richest(n,0,0);
//     cerr<<"\n Cnt  "<<Cnt<<"\n";
// }