#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 17;
int par[100001], ans[1000001], n, a[100001], l[100001], q;
vector<int> qu[100001];

int root(int v){
    return par[v] == -1 ? v : par[v] = root(par[v]);
}

int main(){
  ifstream in;
  ofstream out;
  in.open("rmq.in");
  out.open("rmq.out");
    memset(par, -1, sizeof par);
    in >> n >> q;
    for(int i = 0; i < n; i++)
      in >> a[i];
    for(int i = 0, r; i < q; i++){
	       in >> l[i] >> r;
         r--;
         l[i]--;
	       qu[r].push_back(i);
    }

    stack<int> st;
    for(int i = 0; i < n; i++){
	     while(st.size() && a[st.top()] >= a[i]) {
	      par[st.top()] = i;
        st.pop();
       }
	     st.push(i);
	     for(auto qi : qu[i])
	      ans[qi] = a[root(l[qi])];
    }
    for(int i = 0; i < q; i++)
	     out << ans[i] << '\n';
    return 0;
}