5.cpp

#include<vector>
#include<math.h>
#include<iostream>
#include<utility>

struct Pair {
    int elem;
    int index;  
    Pair(int e, int i) : elem(e), index(i) {}
    Pair() : elem(0), index(0) {}
    friend bool operator ==(Pair a,Pair b);
};
bool operator ==(Pair a,Pair b) {
    return b.elem==a.elem && a.index == b.index;
}

struct Stat{
    Pair first;
    Pair second;
};
Pair min(Pair a, Pair b){
    if(a.elem < b.elem)
        return a;
    else
        return b;
}
int min(int a, int b){
    return a < b? a : b;
}

double log2(double a) {
    return log(a)/log(2);
}

Stat min2(const std::vector<int>& tbl, int i, int j){
    Stat s;
    if(tbl[i] <= tbl[j]) {
        s.first  = Pair(tbl[i], i);
        s.second = Pair(tbl[j], j);
    } else {
        s.first  = Pair(tbl[j], j);
        s.second = Pair(tbl[i], i);
    }
    return s;
}

Stat min_stat(const std::vector<Stat>& tbl, int i, int j){
    Stat s;
    if (tbl[i].first == tbl[j].first) {
        s.first  = tbl[i].first;
        s.second = min(tbl[i].second, tbl[j].second);
    }
    else if (tbl[i].first.elem < tbl[j].first.elem) {
        s.first  = tbl[i].first;
        s.second = min(tbl[i].second, tbl[j].first);
    } else {
        s.first = tbl[j].first;
        s.second = min(tbl[i].first, tbl[j].second);
    }
    return s;
}

struct SparseTable{
 public:
    SparseTable(const std::vector<int> tbl);
    int RMQ_2(int, int);
 private:
    std::vector<std::vector<Stat> > table;
    std::vector<int>Log;
};

SparseTable::SparseTable(const std::vector<int> tbl) : table(log2(tbl.size())+1), Log(tbl.size() + 1){
    // база - минимумы пар
    for( int i = 0; i < tbl.size(); i++)
        table[0].push_back( min2(tbl, i, i) );
    for( int i = 0; i < tbl.size() - 1; i++)
        table[1].push_back( min2(tbl, i, i+1) );
    // рекурентная формула
    for(int k = 2; k < table.size(); k++)
        for(int i = 0; i < table[k-1].size() - pow(2, k - 1); i++)
            table[k].push_back( min_stat(table[k-1], i, i+pow(2, k - 1)) );
    // предрасчет логарифмов
    for( int i = 1; i < tbl.size() + 1; i++)
        Log[i] = log2(i);
}

int SparseTable::RMQ_2(int i, int j) {
    int k = Log[j - i + 1];
    return min_stat(table[k], i, j-pow(2,k) + 1).second.elem;
}



int main() {   
    int n = 0,
        m = 0;
    std::cin >> n >> m;
    std::vector<int> vec(n);

    for(int i = 0; i  < n; i++)
        std::cin >> vec[i];
    SparseTable ST( vec );

    std::vector<std::pair<int,int> > intervals(m);
    for (int i = 0; i < m; i++)
        std::cin >> intervals[i].first >> intervals[i].second;
    
    for (int i = 0; i < m; i++)
        std::cout <<ST.RMQ_2(intervals[i].first - 1, intervals[i].second - 1) << '\n';

    return 0;
}