/*
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e6 + 5, K = 10;

int n, m;
LL f[N], g[N];
int p[K][N];

inline LL Calc(int i, int j)
{
    LL t = i / j, p = i % j, q = j - p;
    return q * t * (t - 1) / 2 + p * t * (t + 1) / 2;
}
inline void Solve(int k, int l, int r, int L, int R)
{
    L = max(L, 1), R = min(R, n);
    if(l > r) return ;
    if(L == R)
    {
        for(int i = l; i <= r; i ++ )
        {
            f[i] = g[L] + Calc(i, L);
            p[k][i] = L;
        }
        return ;
    }
    int mid = (l + r) >> 1;
    for(int i = L; i <= min(R, mid); i ++ )
    {
        if(g[i] + Calc(mid, i) < f[mid])
        {
            f[mid] = g[i] + Calc(mid, i);
            p[k][mid] = i;
        }
    }
    Solve(k, l, mid - 1, L, p[k][mid] + 20);
    Solve(k, mid + 1, r, p[k][mid] - 20, R);
}

int main()
{
    n = 1e6, m = 8;
    memset(g, 0x3f, sizeof g);
    g[1] = 0;
    for(int i = 1; i <= m; i ++ )
    {
        memset(f, 0x3f, sizeof f);
        Solve(i, 1, n, 1, n);
        memcpy(g, f, sizeof g);
        int mx = 0;
        for(int j = 1; j < n; j ++ ) mx = max(mx, p[i][j] - p[i][j + 1]);
    }
    printf("%lld\n", f[n]);
    for(int i = m, j = n; i >= 1; i -- )
    {
        j = p[i][j];
        printf("%d\n", j);
    }
    return 0;
}
*/

#include "richest.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
const int num[] = {500000, 250000, 125000, 62496, 20832, 3472, 183, 1};

int cnt[N];
vector<int> p, q, qx, qy, res;

inline void MakeQuery(int l, int r)
{
    for(int i = l; i < r; i ++ )
        for(int j = i + 1; j < r; j ++ )
            qx.push_back(q[i]), qy.push_back(q[j]);
}
inline void GetMax(int l, int r, int L, int R)
{
    int k = r - l;
    for(int i = L; i < R; i ++ )
        cnt[res[i]] ++ ;
    for(int i = l; i < r; i ++ )
        if(cnt[q[i]] == k - 1)
            p.push_back(q[i]);
}

int richest(int n, int t, int s)
{
    p.clear(), q.clear(), qx.clear(), qy.clear();
    memset(cnt, 0, sizeof cnt);
    for(int i = 0; i < n; i ++ ) q.push_back(i);
    if(t == 1)
    {
        MakeQuery(0, n);
        res = ask(qx, qy);
        GetMax(0, n, 0, n * (n - 1) / 2);
        return p[0];
    }
    else
    {
        for(int i = 0; i < 8; i ++ )
        {
            qx.clear(), qy.clear();
            int n = q.size(), m = num[i];
            if(1)
            {
                int x = n / m, p = n % m, q = m - p;
                int k = 0, l = 0;
                for(int i = 1; i <= q; i ++ )
                {
                    MakeQuery(k, k + x);
                    k += x;
                }
                for(int i = 1; i <= p; i ++ )
                {
                    MakeQuery(k, k + x + 1);
                    k += x + 1;
                }
                res = ask(qx, qy);
                k = 0, l = 0;
                for(int i = 1; i <= q; i ++ )
                {
                    GetMax(k, k + x, l, l + x * (x - 1) / 2);
                    k += x, l += x * (x - 1) / 2;
                }
                for(int i = 1; i <= p; i ++ )
                {
                    GetMax(k, k + x + 1, l, l + x * (x + 1) / 2);
                    k += x + 1, l += x * (x + 1) / 2;
                }
            }
            for(int i = 0; i < n; i ++ ) cnt[q[i]] = 0;
            q = p, p.clear();
        }
        return p[0];
    }
}