#include "prize.h"

#include <bits/stdc++.h>

std::map<int, std::array<int, 2>> map;

std::array<int, 2> get(int i) {
    if (map.count(i)) {
        return map[i];
    }
    std::array<int, 2> ar;
    assert(map.size() < 0.99e4);

    auto vec = ask(i);
    std::copy(vec.begin(), vec.end(), ar.begin());
    map[i] = ar;
    return ar;
}

int get_sum(int i) {
    auto [l, r] = get(i);
    return l + r;
}

#define ask FUCK

int find_best(int n) {
    static std::mt19937 rnd;
    map.clear();

    int max = 0;
    for (int i = 0; i < 100; i++) {
        int p = rnd() % n;
        max = std::max(max, get_sum(p));
    }

    std::vector<int> all;
    bool suc = false;

    auto fuck = [&](auto fuck, int l, int r) -> void {
        if (suc) {
            return;
        }
        while (l < r && get_sum(l) < max) {
            all.push_back(l);
            if (get_sum(all.back()) == 0) {
                suc = true;
                return;
                ;
            }
            l++;
        }
        while (l < r && get_sum(r - 1) < max) {
            --r;
            all.push_back(r);
            if (get_sum(all.back()) == 0) {
                suc = true;
                return;
            }
        }
        if (l + 2 < r) {
            int s1 = get(l)[0];
            int s2 = get(r - 1)[1];
            int md = max - s1 - s2;
            assert(md >= 0);
            if (md) {
                // l++;
                // r--;
                int m = (l + r) / 2;
                fuck(fuck, l, m + 1);
                fuck(fuck, m, r);
            }
        }
    };
    fuck(fuck, 0, n);

    for (int i : all) {
        if (get_sum(i) == 0) {
            return i;
        }
    }
    assert(false);
}