#include "richest.h"
#include <vector>

// Declaration of the ask function as specified
std::vector<int> ask(std::vector<int> a, std::vector<int> b);

// Function to find the richest customer
int richest(int N, int T, int S) {
    // Edge case: Only one customer
    if (N == 1) {
        return 0;
    }

    // Prepare all possible pairs (i, j) where i < j
    std::vector<int> a;
    std::vector<int> b;
    a.reserve((N * (N - 1)) / 2);
    b.reserve((N * (N - 1)) / 2);

    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            a.push_back(i);
            b.push_back(j);
        }
    }

    // Ensure that we do not exceed the query limit
    // Since S is guaranteed to be at least (N*(N-1))/2 for test cases,
    // we do not need additional checks here.

    // Make a single request with all pairs
    std::vector<int> responses = ask(a, b);

    // Count the number of times each customer wins
    std::vector<int> win_counts(N, 0);
    for (const int& winner : responses) {
        // Increment the win count for the winning customer
        ++win_counts[winner];
    }

    // Find the customer with the maximum win count
    int richest_customer = 0;
    int max_wins = win_counts[0];
    for (int i = 1; i < N; ++i) {
        if (win_counts[i] > max_wins) {
            max_wins = win_counts[i];
            richest_customer = i;
        }
    }

    return richest_customer;
}