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

using namespace std;
typedef int ll;

ll on2(ll n) {
    vector<ll> a, b;
    for (ll i = 1; i < n; i++) {
        for (ll j = 0; j < i; j++) {
            a.push_back(i);
            b.push_back(j);
        }
    }

    vector<ll> c = ask(a, b);
    std::reverse(c.begin(), c.end());

    vector<vector<bool>> cmp(n, vector<bool>(n, true));
    for (ll i = 1; i < n; i++)
        for (ll j = 0; j < i; j++) {
            cmp[i][j] = c.back() == i;
            cmp[j][i] = c.back() == j;
            c.pop_back();
        }

    for (ll i = 0; i < n; i++) {
        bool good = true;
        for (ll j = 0; j < n; j++)
            good = good and cmp[i][j];

        if (good)
            return i;
    }
    return 0;
}

ll onlogn(ll n) {
    mt19937 rng(3498);

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

    while (p.size() > 1) {
        uniform_int_distribution<> uid(0, p.size() - 1);
        ll pivot = uid(rng);

        vector<ll> a(p.size() - 1, p[pivot]);
        vector<ll> b;
        b.reserve(p.size() - 1);
        for (auto &i : p)
            if (i != p[pivot])
                b.push_back(i);

        vector<ll> c = ask(a, b);

        vector<ll> t = {p[pivot]};
        t.reserve(n);
        for (ll &i : c)
            if (i != t[0])
                t.push_back(i);

        swap(p, t);
    }

    return p[0];
}

ll richest(ll N, ll T, ll S) {
    if (ll(N) * ll(N - 1) / 2ll <= (ll)S) {
        return on2(N);
    } else {
        return onlogn(N);
    }
}