async DO1

#include "profile.h"
#include <algorithm>
#include <execution>
#include <random>
#include <iostream>
#include <vector>
#include <cmath>

#define ll long long

std::mt19937 generator;

int counter = 0;

struct Request {
    int left;
    int right;

    Request(int size){
        left = std::uniform_int_distribution(0, size - 1)(generator);
        right = std::uniform_int_distribution(left, size - 1)(generator);
    }

    Request(int L, int R){
        left = L;
        right = R;
    }
};

struct node{
public:
    long long L, R, val;

    node(int L = -1, int R = -1, long long val = INT64_MAX){
        this->L = L;
        this->R = R;
        this->val = val;
    }

    ~node() = default;
};

std::vector<node> tree;

long long init_node(int indx, int L, int R, const std::vector<long long>& init_array){
    if (L == R) {
        if (counter < init_array.size())
            tree[indx] = {L, R, init_array[counter]};
        else
            tree[indx] = {L, R, INT64_MAX};
        counter++;
        return tree[indx].val;
    }
    long long l = init_node(indx * 2 + 1, L,L + (R - L) / 2 , init_array);
    long long r = init_node(indx * 2 + 2, L + (R - L) / 2  + 1, R, init_array);
    tree[indx] = node(L,R, std::min(l,r));
    return tree[indx].val;
}

void init(const std::vector<long long>& init_array) {
    int n = log2(init_array.size());
    if ( 1 << n != init_array.size())
        n ++;
    int K = 1 << n;
    tree.resize(K*2 - 1);
    auto it = tree.rbegin();
    int i = 0;
    long long a = init_node(0, 0, K - 1, init_array);
    tree[0] = {0, K - 1, a};
}

long long gets(int indx, int L, int R) {
    if (R >= tree[indx].R && L <= tree[indx].L)
        return tree[indx].val;
    if (R < tree[indx].L || L > tree[indx].R)
        return INT64_MAX;
    return std::min(gets(indx * 2 + 1, L, R), gets(indx * 2 + 2, L, R));
}

long long get(Request req, int indx = 0) {
    auto L = req.left, R = req.right;
    if (R >= tree[indx].R && L <= tree[indx].L)
        return tree[indx].val;
    if (R < tree[indx].L || L > tree[indx].R)
        return INT64_MAX;
    return std::min(gets(indx * 2 + 1, L, R), gets(indx * 2 + 2, L, R));
}


std::vector<ll> ProcessRequests(const std::vector<ll>& numbers, const std::vector<Request>& requests){
    std::vector<ll> ans(requests.size());
    init(numbers);
    std::transform(std::execution::par, requests.begin(), requests.end(), ans.begin(), [](Request r){return get(r);});
    return ans;

}

std::vector<ll> ProcessRequestsOld(const std::vector<ll>& numbers, const std::vector<Request>& requests){
    std::vector<ll> ans;
    init(numbers);
    for(auto el: requests){
        ans.push_back(get(el));
    }
    return ans;
}

int main(){
    ll N= 100000000, R = 10000000;
    std::vector<ll> num(N);
    const std::vector<Request> request(R, N);
    for(ll i = 0; i < N; i++){
        num[i] = std::uniform_int_distribution(0, 1000000)(generator);
    }
    {
        LOG_DURATION("Old");
        ProcessRequestsOld(num, request);
    }
    tree.clear();
    {
        LOG_DURATION("New");
        ProcessRequests(num, request);
    }
}