// P10786 [NOI2024] 百万富翁
#include "richest.h"
#include <cstdio>
#include <iostream>
#include <vector>
#include <cassert>
#define ll long long
#define rep(i, s, t) for(int i=s; i<=t; ++i)
#define debug(x) cerr<<#x<<":"<<x<<endl;
const int N=1000010;
using namespace std;
char buf[1<<23], *p1=buf, *p2=buf;
#define gc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
    int x=0, f=1; char c=gc();
    while(c<'0' || c>'9') c=='-' && (f=-1), c=gc();
    while('0'<=c && c<='9') x=(x<<3)+(x<<1)+c-'0', c=gc();
    return x*f;
}

namespace t1
{
    vector<int> a[3]; int deg[N];
    int solve(int n)
    {
        a[0].clear(), a[1].clear(), a[2].clear(); rep(i, 0, n-1) deg[i]=0;
        rep(i, 0, n-1) rep(j, i+1, n-1)
        {
            a[0].push_back(i), a[1].push_back(j);
        }
        a[2]=ask(a[0], a[1]);
        rep(i, 0, (int)a[0].size()-1)
            deg[a[2][i]]++;
        rep(i, 0, n-1) if(deg[i]==n-1) return i;
        return -1;
    }
}

namespace t2
{
    int l[]={1000000, 500000, 250000, 125000, 62500, 20833, 3472, 183, 1};
    vector<int> q[3]; int deg[N];
    void Cons(vector<int> &a)
    {
        int n=a.size();
        rep(i, 0, n-1) rep(j, i+1, n-1)
        {
            assert(0<=a[i] && a[i]<1000000);
            assert(0<=a[j] && a[j]<1000000);
            q[0].push_back(a[i]), q[1].push_back(a[j]);
        }
    }
    int Ask(int l, int r, int n)
    {
        rep(i, l, r) deg[q[2][i]]++;
        int res=-1;
        rep(i, l, r) if(deg[q[2][i]]==n-1) res=q[2][i];
        rep(i, l, r) deg[q[2][i]]--;
        return res;
    }
    int solve(int n, int t, int s)
    {
        vector<int> b;
        rep(i, 0, n-1) b.push_back(i);
        rep(k, 1, 8)
        {
            vector<vector<int>> a(l[k]);
            rep(i, 0, l[k-1]-1) a[i%l[k]].push_back(b[i]);
            b.clear();
            q[0].clear(), q[1].clear(), q[2].clear();
            rep(i, 0, l[k]-1) Cons(a[i]);
            q[2]=ask(q[0], q[1]);
            int L=0, R=0;
            rep(i, 0, l[k]-1)
            {
                int n=a[i].size();
                R=L+n*(n-1)/2-1;
                b.push_back(Ask(L, R, n));
                L=R+1;
            }
        }
        return b[0];
    }
}

int richest(int n, int T, int S)
{
    if(n<=1000) return t1::solve(n);
    return t2::solve(n, T, S);
}