#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <future>
#include <string>
#include <mutex>

struct Request {
    int left; int right;
};

std::mutex m;
struct X {
    std::vector<std::vector<int>> nums;

    void make_rmq(const std::vector<int>& numbers) {
        nums.emplace_back();
        for (int i: numbers) {
            nums[0].emplace_back(i);
        }
        for (int j = 1; pow(2, j) <= numbers.size(); ++j) {
            nums.emplace_back();
            for (int i = 0; i < numbers.size() - int(pow(2, j)) + 1; ++i) {
                nums[j].emplace_back(std::max(nums[j - 1][i], nums[j - 1][i + int(pow(2, j - 1))]));
            }
        }
    }

    void process_partial(long long l, long long r, const std::vector<Request>& requests, std::vector<int>& ans) {
        std::lock_guard<std::mutex> lk(m);
        for (long long i = l; i < r; ++i) {
            int lg = floor(log2(r - l));
            ans[i] = std::max(nums[lg][requests[i].left], nums[lg][requests[i].right - int(pow(2, lg))]);
        }
    }
};

std::vector<int> ProcessRequests(
        const std::vector<int>& numbers, const std::vector<Request>& requests) {
    X x;
    x.make_rmq(numbers);
    std::vector<int> ans(requests.size());
    long long i0 = requests.size() / 4;
    long long i1 = requests.size() / 2;
    long long i2 = 3 * requests.size() / 4;
    auto a1 = std::async(std::launch::deferred, &X::process_partial, &x, 0, i0, requests, ans);
    auto a2 = async(&X::process_partial, &x, i0, i1, requests, ans);
    auto a3 = async(&X::process_partial, &x, i1, i2, requests, ans);
    auto a4 = async(&X::process_partial, &x, i2, requests.size(), requests, ans);
    return ans;
}