#include "richest.h"

#include <bits/stdc++.h>
using namespace std;   

vector<int> work(vector<int> v, int b) { // returns the candidate value after one iteration
        int N=v.size();

        vector<array<int,3>> info;
        vector<int> qa,qb;
        for(int i=0;i<N;i+=b) {
                if(i+b-1<N) {
                        for(int j=0;j<b;j++) {
                                for(int k=j+1;k<b;k++) {
                                        qa.push_back(v[i+j]);
                                        qb.push_back(v[i+k]);
                                        info.push_back({i/b,i+j,i+k});
                                }
                        }
                } else {
                        int c=N-i;
                        for(int j=0;j<c;j++) {
                                for(int k=j+1;k<c;k++) {
                                        qa.push_back(v[i+j]);
                                        qb.push_back(v[i+k]);
                                        info.push_back({i/b,i+j,i+k});
                                }
                        }
                }
        }       

        vector<int> res=ask(qa,qb);

        vector<bool> rem(N);

        for(int i=0;i<info.size();i++) {
                auto [x,y,z]=info[i];
                if(res[i]==v[y]) rem[z]=1;
                else rem[y]=1;
        }

        vector<int> ans;
        for(int i=0;i<N;i++) 
                if(!rem[i]) ans.push_back(v[i]);

        assert(ans.size()==(N+b-1)/b);

        return ans;
}

int richest(int N, int T, int S) {
        vector<int> cur;
        for(int i=0;i<N;i++) cur.push_back(i);

        if(N==1000) {
                cur=work(cur,1000);
                return cur[0];
        }

        cur=work(cur,2);
        cur=work(cur,2);
        cur=work(cur,2);
        cur=work(cur,3);
        cur=work(cur,6);
        cur=work(cur,18);
        cur=work(cur,20);
        cur=work(cur,20); 

        assert(cur.size()==1);
        return cur[0];
}