#include "richest.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128;
using u128 = unsigned __int128;
template <typename T>
void chkmax(T &x, const T &y) {
  x = max(x, y);
}
template <typename T>
void chkmin(T &x, const T &y) {
  x = min(x, y);
}
void work(vector<int> &id, int x) {
  vector<int> nid(x), a, b;
  for (int i = 0; i < x; ++i) {
    for (int j = i; j < (int)id.size(); j += x) {
      for (int k = j + x; k < (int)id.size(); k += x) {
        a.emplace_back(id[j]);
        b.emplace_back(id[k]);
      }
    }
  }
  vector<int> c = ask(a, b), deg(id.size());
  for (int i = 0, p = 0; i < x; ++i) {
    for (int j = i; j < (int)id.size(); j += x) {
      for (int k = j + x; k < (int)id.size(); k += x) {
        if (c[p++] == id[j]) {
          ++deg[j];
        } else {
          ++deg[k];
        }
      }
    }
    int bst = i;
    for (int j = i + x; j < (int)id.size(); j += x)
      if (deg[j] > deg[bst]) bst = j;
    nid[i] = id[bst];
  }
  id = move(nid);
}
int richest(int n, int, int) {
  static constexpr int magic[] = {500000, 250000, 125000, 62496, 20832, 3472, 183, 1};
  vector<int> vec(n);
  iota(vec.begin(), vec.end(), 0);
  if (n == 1000) {
    work(vec, 1);
  } else {
    for (auto x : magic) work(vec, x);
  }
  return vec[0];
}
/*
g++ B.cpp grader.cpp -o B -std=c++14 -O2 -Wall -Wextra -Wshadow -g -fsanitize=address,undefined
*/
/*
1000000 20 2000000 0
*/