#include "richest.h"
#include <bits/stdc++.h>

using namespace std;
typedef int ll;

//vector<ll> W;
//ll ct = 0, cs = 0;
//vector<ll> ask(vector<ll> a, vector<ll> b) {
//    assert(a.size() == b.size());
//    ct++;
//    cs += (ll)a.size();
//
//    vector<ll> c(a.size());
//    for (ll i = 0; i < a.size(); i++) {
//        assert(a[i] != b[i]);
//        if (W[a[i]] > W[b[i]])
//            c[i] = a[i];
//        else
//            c[i] = b[i];
//    }
//    return c;
//}

ll on(ll n) {
    mt19937 rng(23);

    vector<ll> p(n);
    std::iota(p.begin(), p.end(), 0);

    while (n > 1) {
        std::shuffle(p.begin(), p.end(), rng);

        vector<ll> a(n / 2), b(n / 2);
        for (ll i = 0; i + 1 < n; i += 2)
            a[i / 2] = p[i], b[i / 2] = p[i + 1];

        a = ask(a, b);
        if (n % 2 == 1)
            a.push_back(p.back());

        p = a;
        n = (ll)p.size();
    }

    return p[0];
}

ll richest(ll N, ll T, ll S) {
    return on(N);
}

//ll main() {
//    random_device rd;
//    mt19937 rng(rd());
//
//    ll mt = 0, ms = 0;
//    ll t = 100;
//    while (t--) {
//        ll N = 1'000'000, T = 20, S = 2'000'000;
//        W.resize(N);
//        std::iota(W.begin(), W.end(), 0);
//        shuffle(W.begin(), W.end(), rng);
//
//        ct = 0, cs = 0;
//        richest(N, T, S);
//        cout << ct << " " << cs << "\n";
//        ms = max(ms, cs);
//        mt = max(mt, ct);
//    }
//
//    cout << "\n\n" << mt << " " << ms << "\n";
//
//    return 0;
//
//}