#include <bits/stdc++.h>

using namespace std;

ifstream fin("rmq.in");
ofstream fout("rmq.out");

int rmq[100100][19];
int logaritm[100100];

int n, m;

void build(){
    for(int bit = 1; bit <= 18; bit ++){
        for(int i = 1; i + (1 << bit) - 1 <= n; i ++){
            rmq[i][bit] = min(rmq[i][bit - 1], rmq[i + (1 << (bit - 1))][bit - 1]);
        }
    }
}

int query(int l, int r)
{
    int bit = logaritm[r - l + 1];
    return min(rmq[l][bit], rmq[r - (1 << bit) + 1][bit]);
}

int main()
{
    fin >> n >> m;
    logaritm[2] = 1;
    for(int i = 3; i <= 100000; i ++)
    {
        logaritm[i] = logaritm[i / 2] + 1;
    }

    for(int i = 1; i <= n; i ++){
        fin >> rmq[i][0];
    }
    build();
    while(m--)
    {
        int l, r;
        fin >> l >> r;
        fout << query(l, r);
    }
}