#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
int richest(int N, int T, int S) {
    // 确定分组数量
    // 如果 T == 1，则所有比较必须在一次请求中完成
    // 否则，分为 K = T - 1 组，并留出一次请求用于比较局部最大值
    int K = (T > 1) ? T - 1 : 1;
    // 计算每组的大小，确保均匀分配
    int group_size = (N + K - 1) / K;

    vector<int> local_maxima; // 存储每组的局部最大值

    for(int k = 0; k < K; k++) {
        int start = k * group_size;
        int end = min(start + group_size, N);

        if(start >= end) continue;

        // 初始化当前组的最大值为第一个客户
        int current_max = start;

        // 准备比较的向量
        vector<int> a;
        vector<int> b;

        for(int i = start + 1; i < end; i++) {
            a.push_back(current_max);
            b.push_back(i);
        }

        // 发送请求并获取比较结果
        vector<int> res = ask(a, b);

        // 根据比较结果更新当前组的最大值
        for(int i = 0; i < res.size(); i++) {
            if(res[i] == b[i]) {
                current_max = b[i];
            }
            // 如果 res[i] == a[i]，current_max 保持不变
        }

        // 将当前组的局部最大值加入列表
        local_maxima.push_back(current_max);
    }

    // 如果只进行了 K=1 组的比较，直接返回该组的最大值
    if(local_maxima.size() == 1) {
        return local_maxima[0];
    }

    // 准备比较所有局部最大值以找到全局最大值
    // 初始化全局最大值为第一个局部最大值
    int global_max = local_maxima[0];
    vector<int> a_final;
    vector<int> b_final;

    for(int i = 1; i < local_maxima.size(); i++) {
        a_final.push_back(global_max);
        b_final.push_back(local_maxima[i]);
    }

    // 发送最终的比较请求
    vector<int> res_final = ask(a_final, b_final);

    // 根据比较结果更新全局最大值
    for(int i = 0; i < res_final.size(); i++) {
        if(res_final[i] == b_final[i]) {
            global_max = b_final[i];
        }
        // 如果 res_final[i] == a_final[i]，global_max 保持不变
    }

    return global_max;
}