#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
const long long inf = 1e18;
int init, w[9][N], C1[9][N], C2[9][N];
long long f[9][N];
void upd(int i, int j, int k) {
	for(int c2 = j % k, c1 = j / k - c2, t = 0; c1 >= 0 && t < 10; c1 -= k + 1, c2 += k, t++) {
		long long res = k * (k - 1ll) / 2 * c1 + k * (k + 1ll) / 2 * c2 + f[i - 1][c1 + c2];
		if(res < f[i][j]) f[i][j] = res, w[i][j] = k, C1[i][j] = c1, C2[i][j] = c2;
	}
}
void Init() {
	init = 1;
	for(int i = 2; i < N; i++) f[0][i] = inf;
	for(int i = 1; i < 9; i++)
		for(int j = 1; j < N; j++) {
			f[i][j] = inf;
			int lim = ((j <= N / 8) ? min(20, j) : 2);
			for(int k = 2; k <= lim; k++) upd(i, j, k);
			upd(i, j, j);
		}
}
int richest(int N, int T, int S) {
	vector<int> l, r, ok(N, 1), cand(N);
	iota(cand.begin(), cand.end(), 0);
	auto query = [&](int L, int R) {
		for(int i = L; i < R; i++)
			for(int j = L; j < i; j++)
				l.push_back(cand[i]), r.push_back(cand[j]);
	};
	auto solve = [&]() {
		auto res = ask(l, r);
		for(int i = 0; i < (int)l.size(); i++)
			ok[l[i]] &= (res[i] == l[i]), ok[r[i]] &= (res[i] == r[i]);
	};
	if(T == 1) {
		vector<int>().swap(l), vector<int>().swap(r);
		l.reserve(N * (N - 1) / 2), r.reserve(N * (N - 1) / 2);
		query(0, N);
		solve();
		for(int i = 0; i < N; i++) if(ok[i]) return i;
	}
	if(!init) Init(), cerr << f[8][::N - 1] << endl;
	for(int t = 8; (int)cand.size() > 1; t--) {
		int n = cand.size(), v = w[t][n], c1 = C1[t][n], c2 = C2[t][n],
			len = v * (v - 1) / 2 * c1 + v * (v + 1) / 2 * c2;
		vector<int>().swap(l), vector<int>().swap(r);
		l.reserve(len), r.reserve(len);
		for(int i = 0; i < c1; i++)
			query(i * v, (i + 1) * v);
		for(int i = 0; i < c2; i++)
			query(c1 * v + i * (v + 1), c1 * v + (i + 1) * (v + 1));
		solve();
		vector<int> nxt;
		nxt.reserve(c1 + c2);
		for(auto x: cand) if(ok[x]) nxt.push_back(x);
		cand = nxt;
	}
	return cand[0];
}