#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#include<deque>
#define itn int
#define coder goodboy
using namespace std;
typedef long long LL;typedef unsigned long long ULL;
struct RMQ{
	int n,m;
	static const int MAXN=100010;
	static const int MAXLOG=100;
	int A[MAXN][MAXLOG];//min
	int B[MAXN][MAXLOG];//max
	void init(){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) scanf("%d",&A[i][0]);
		memcpy(B,A,sizeof(A));
		
    	for(int j=1;(1<<j)<=n;j++)
			for(int i=1;i+(1<<j)-1<=n;i++){
				A[i][j]=min(A[i+(1<<(j-1))][j-1],A[i][j-1]);
				B[i][j]=max(B[i+(1<<(j-1))][j-1],B[i][j-1]);
			}
      }
	int Max_num,Min_num;
	void Query(int L,int R){
		int k=0;
		while((1<<(k+1))<=R-L+1) k++;
		Max_num=max(B[L][k],B[R-(1<<k)+1][k]);
		Min_num=min(A[L][k],A[R-(1<<k)+1][k]);
		printf("%d ",Min_num);
	}
	void work(){
		for (int i=1;i<=m;i++){
			int temp1,temp2;
			scanf("%d%d",&temp1,&temp2);
			Query(temp1,temp2);
		}
	}
}RMQ1;
int Main(){
	freopen("faithful.in","r",stdin);
	freopen("faithful.out","w",stdout);
	RMQ1.init();
	RMQ1.work();
	return 0;
}
int main(){;}
int goodboy=Main();