Тёплые воспоминания

// OK http://contest.uni-smr.ac.ru/ru/problemset/6353/

# include <iostream>
# include <vector>
# include <algorithm>

bool check(std::vector<std::vector<size_t>> &min_value, std::vector<std::vector<size_t>> &max_value,
        std::vector<size_t> &p, size_t l, size_t r, size_t l_ex, size_t r_ex) {
    size_t j = p[r - l + 1];
    size_t min_el = std::min(min_value[l][j], min_value[r - ((1u << j) - 1)][j]);
    size_t max_el = std::max(max_value[l][j], max_value[r - ((1u << j) - 1)][j]);
    return min_el < (l_ex - 1) || max_el >= r_ex;
}
// included l_ex, included r_ex, enumerate from 1

int main() {
    uint32_t n, q;
    std::cin >> n >> q;
    std::vector<std::pair<int32_t, size_t>> m(n + 1);
    for (size_t i = 0; i < n; i++) {
        int32_t a;
        std::cin >> a;
        m[i] = {a, i};
    }
    m[n] = {15700000, n - 1};
    std::sort(m.begin(), m.end());
    std::vector<size_t> p(n + 2);
    p[1] = 0;
    for (size_t i = 2; i <= (n + 1); i++) {
        p[i] = p[i / 2] + 1;
    }

    std::vector<std::vector<size_t>> min_value(n + 1, std::vector<size_t> (p[n + 1] + 1, INT32_MAX));
    std::vector<std::vector<size_t>> max_value(n + 1, std::vector<size_t> (p[n + 1] + 1, INT32_MAX));

    for (size_t i = 0; i < (n + 1); i++) {
        min_value[i][0] = m[i].second;
        max_value[i][0] = m[i].second;
    }

    for (size_t j = 1; j <= p[n + 1]; j++) {
        for (size_t i = 0; i + (1u << j) <= (n + 1); i++) {
            min_value[i][j] = std::min(min_value[i][j - 1], min_value[i + (1u << (j - 1))][j - 1]);
            max_value[i][j] = std::max(max_value[i][j - 1], max_value[i + (1u << (j - 1))][j - 1]);
        }
    }
    for (size_t i = 0; i < q; i++) {
        size_t l, r;
        int32_t x;
        std::cin >> l >> r >> x;
        // first bs, right req
        int32_t left = -1;
        int32_t right = (n + 1) - 1;
        while (right - left > 1) {
            size_t mid = (left + right) / 2;
            if (x <= m[mid].first) {
                right = mid;
            } else {
                left = mid;
            }
        }
        size_t true_left_r = right;
        left = right;
        right = n + 1;
        // right -> ++ans
        while (right - left > 1) {
            size_t mid = (left + right) / 2;
            if (check(min_value, max_value, p, true_left_r, mid - 1, l, r)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        std::cout << m[right - 1].first << '\n';
    }
    return 0;
}