#include "richest.h"

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()

vector<int> compute(vector<int> a, vector<int> k) {
        int n = a.size();
        //int zz=n;
        //for(auto&x:k) { x=min(x,zz);zz-=x; }
        //while(k.back()==0)k.pop_back();

        vector<int> qa, qb;
        vector<int> nx;
        //printf(": %d %d\n",accumulate(all(k),0),n);
        assert(accumulate(all(k),0)==n);
        int i=0;
        for(auto l: k) {
                int j=i+l;
                if(l==1) nx.push_back(a.back());
                for(int j=0;j<l;j++)
                        for(int k=j+1;k<l;k++)
                                assert(j!=k),
                                assert(a[i+j]!=a[i+k]),
                                qa.push_back(a[i+j]),qb.push_back(a[i+k]);
                i=j;
        }
        auto ans = ask(qa,qb);
        //for(int i=0;i<ans.size();i++)printf("%d %d %d\n",qa[i],qb[i],ans[i]);
        i=0;
        for(auto l:k) {
                int j=i+l*(l-1)/2;
                map<int,int> occ;
                for(int z=i;z<j;z++)occ[ans[z]]++;
                int ad=0;
                //for(int z=i;z<j;z++)printf("(%d %d %d ",qa[z],qb[z],ans[z]);
                //printf("\n");
                for(auto [x,v]:occ)if(v==l-1) {
                        //printf("add %d\n",x);
                        nx.push_back(x);
                        ad++;
                }
                //if(!(l==1||ad==1)) {
                //for(int z=i;z<j;z++)printf("(%d %d %d ",qa[z],qb[z],ans[z]);
                //printf("\n");
                //for(auto [x,v]:occ)printf("! %d %d\n",x,v);
                //printf("\n\n");
                //}
                assert(l==1 || ad==1);
                i=j;
        }
        //printf("%d %d %d\n",a.size(),k.size(),nx.size());
        return nx;
}

int richest(int N, int T, int S) {
        if(N<=1000) {
                vector<int> a,b;
                vector<int> occ(N);
                for(int i=0;i<N;i++)for(int j=i+1;j<N;j++) a.push_back(i),b.push_back(j);
                auto res = ask(a,b);
                for(auto x:res)occ[x]++;
                return max_element(all(occ)) - occ.begin();
        }
        vector<int> p{2, 2, 2, 2, 3, 6, 19, (int)1e9};
        vector<int> pos(N);
        for(int i=0;i<N;i++)pos[i]=i;

/*
1000000 2       500000  0
500000  2       250000  0
250000  2       125000  0
125000  2       62500   0
62500   3       62499   1
20834   6       52081   2
3473    19      31227   15
183 16653
*/
        // 2
        vector<int> pl(N/2,2);
        pos=compute(pos,pl);
        // 2
        pl=vector<int>(pos.size()/2,2);
        pos=compute(pos,pl);
        // 2
        pl=vector<int>(pos.size()/2,2);
        pos=compute(pos,pl);
        // 2
        pl=vector<int>(pos.size()/2,2);
        pos=compute(pos,pl);
        // 3 +1
        pl.clear();
        for(int i=0;i<20832;i++)pl.push_back(3);
        pl.push_back(4);
        pos=compute(pos,pl);
        // 6 +2
        pl.clear();
        for(int i=0;i<3471;i++)pl.push_back(6);
        pl.push_back(7);
        pos=compute(pos,pl);
        // 19 +15
        pl.clear();
        for(int i=0;i<183-5;i++)pl.push_back(19);
        for(int i=0;i<5;i++)pl.push_back(18);
        pos=compute(pos,pl);
        // 183
        pl={183};
        pos=compute(pos,pl);

        return pos[0];
}