#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;
//}

vector<ll> p, q;

ll onlogn(ll n) {
    ll N = n;
    p.resize(n);
    p.shrink_to_fit();
    std::iota(p.begin(), p.end(), 0);

    ll cnt = 0;
    while (n > 1) {
        cnt++;
        if (cnt > 20)
            assert(false);

        q.resize(n);
        q.shrink_to_fit();
        for (ll i = 0; i < n; i++)
            q[i] = p[(i + 1) % n];

        for (ll i = 0; i < n; i++)
            if (p[i] == q[i] or p[i] < 0 or p[i] >= N or q[i] < 0 or q[i] >= N)
                assert(false);

        q = ask(p, q);

        p.clear();
        p.reserve(n / 2 + 2);
        for (ll i = 0; i < n; i++) {
            if (q[i] == q[(i + 1) % n]) {
                p.push_back(q[i]);
                i++;
            }
        }
        p.shrink_to_fit();
        n = p.size();
    }

    return p[0];
}

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