#include "richest.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll mod = 1e9 + 7;
// cope counter = 2254

ll rng(void) {
	static ll x = 123456789, y = 362436069, z = 521288629;
	ll t;
	x ^= x << 16, x ^= x >> 5, x ^= x << 1;
	t = x, x = y, y = z, z = t ^ x ^ y;
	return x ^ y ^ z;
}

int num[8] = {1, 2, 2, 2, 2, 3, 6, 19};
vector<int> arr, nxt, a, b, c, diff;

int richest(int st, int end) {
	int rich = 0, i = st;
	for(; i < min((int)a.size(), end); i++) {
		if(i == st || a[i] != a[i - 1]) {
			if(rich) return a[i - 1];
			rich = 1;
		}
		if(c[i] != a[i]) rich = 0;
	}
	return c[i - 1];
}
int bf() {
	int n = arr.size();
	if(n == 1) return arr[0];
	a.clear(), b.clear();
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) a.push_back(arr[i]), b.push_back(arr[j]);
	}
	c = ask(a, b);
	return richest(0, a.size());
}
int richest(int n, int t, int s) {
	arr.resize(n);
	for(int i = 0; i < n; i++) arr[i] = i;
	if(t == 1) return bf();
	for(int i = 1; i < 8; i++) {
		a.clear(), b.clear(), diff.clear();
		diff.push_back(num[i]);
		for(int j = 0; j < n; j += diff.back()) {
			for(int i2 = j; i2 < min(n, j + diff.back()); i2++) {
				for(int j2 = i2 + 1; j2 < min(n, j + diff.back()); j2++) a.push_back(arr[i2]), b.push_back(arr[j2]);
			}
			diff.push_back(num[i]);
		}
		c = ask(a, b);
		nxt.clear();
		for(int st = 0, i = 0; st < (int)a.size(); st += diff[i] * (diff[i] - 1) / 2, i++) nxt.push_back(richest(st, st + diff[i] * (diff[i] - 1) / 2));
		if(b.back() != arr.back()) nxt.push_back(arr.back());
		arr = nxt, n = arr.size();
		if(arr.size() == 1) break;
	}
	return bf();
}