#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
int buc[8] = {1000,0,0,0,0,0,0,0};
int count(vector<int> &v, int x) {return upper_bound(v.begin(),v.end(),x)-lower_bound(v.begin(),v.end(),x);}
int rich(vector<int> v, int it) {
  int sz = v.size();
  if(sz==1) return v[0];
  int bucket = buc[it];
  vector<int> a, b;
  for(int i=0;i<sz;i+=bucket) {
    for(int j=i;j<sz&&j<i+bucket;j++) for(int k=i;k<j;k++) a.push_back(v[j]),b.push_back(v[k]);
  }
  vector<int> c = ask(a,b);
  sort(c.begin(),c.end());
  vector<int> win;
  for(int i=0;i<sz;i+=bucket) {
    for(int j=i;j<sz&&j<i+bucket;j++) if(count(c,v[j])==min(bucket,sz-i)-1) win.push_back(v[j]);
  }
  return rich(win,it+1);
}
int richest(int N, int T, int S) {
  vector<int> v(N);
  iota(v.begin(),v.end(),0);
  return rich(v,0);
}
/*
int cdiv(int x, int y) {
  return (x-1)/y+1;
}
pair<long long,int> dp[9][1000005];
main() {
  // is x = ceil(1e6 / y) for some y?
  // x >= 1e6 / y
  // y >= 1e6 / x
  // check first value
  dp[0][1]={0,1};
  for(int i=2;i<1000005;i++) dp[0][i]={1000000000,1};
  for(int i=1;i<9;i++) for(int j=1;j<1000005;j++) if(j==cdiv(1000000,cdiv(1000000,j))) {
    dp[i][j]={dp[i-1][j].first,1};
    for(int k=2;k<=j;k++) dp[i][j]=min(dp[i][j],{dp[i-1][cdiv(j,k)].first+1LL*(k-1)*j,k});
  }
  cout << dp[8][1000000].first << "\n";
  for(int x=1000000,i=9;x>1;) {
    cout << "div by "<<dp[--i][x].second << "\n";
    x = cdiv(x,dp[i][x].second);
    cout << "x = " << x << "\n";
  }
}
// 1000000 (0)
// 500000 (500000)
// 250000 (750000)
// 125000 (875000)
// 62500 (937500)
*/