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