#include <fstream>

using namespace std;

const char InFile[]="rmq.in";
const char OutFile[]="rmq.out";
const int MaxN=100111;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,M,x,y,V[MaxN],g[MaxN],lant[MaxN],tata_lant[MaxN],niv[MaxN];

struct Node
{
	Node(int ind=0):ind(ind),left(NULL),right(NULL),parent(NULL){}
	
	int ind;
	
	Node *left,*right,*parent;
};

Node *root,*ptr;

void DFS(Node *node)
{
	int &nod=node->ind;
	g[nod]=1;
	if(!node->left && !node->right)
	{
		lant[nod]=++lant[0];
		return;
	}
	
	int gmax=0;
	if(node->left)
	{
		int &vcn=node->left->ind;
		niv[vcn]=niv[node->ind]+1;
		DFS(node->left);
		g[nod]+=g[vcn];
		tata_lant[vcn]=nod;
		if(g[vcn]>g[gmax])
		{
			gmax=vcn;
		}
	}
	
	if(node->right)
	{
		int &vcn=node->right->ind;
		niv[vcn]=niv[node->ind]+1;
		DFS(node->right);
		g[nod]+=g[vcn];
		tata_lant[vcn]=nod;
		if(g[vcn]>g[gmax])
		{
			gmax=vcn;
		}
	}
	lant[nod]=lant[gmax];
}

inline int LCA(int x, int y)
{
	while(lant[x]!=lant[y])
	{
		if(niv[tata_lant[lant[x]]]>niv[tata_lant[lant[y]]])
		{
			x=tata_lant[x];
		}
		else
		{
			y=tata_lant[y];
		}
	}
	if(niv[x]<niv[y])
	{
		return x;
	}
	return y;
}

int main()
{
	fin>>N>>M;
	fin>>V[1];
	root=new Node(1);
	ptr=root;
	for(register int i=2;i<=N;++i)
	{
		fin>>V[i];
		Node *node=new Node(i);
		while(ptr && V[i]<V[ptr->ind])
		{
			ptr=ptr->parent;
		}
		
		if(!ptr)
		{
			node->left=root;
			root->parent=node;
			root=node;
		}	
		else if(!ptr->right)
		{
			ptr->right=node;
			node->parent=ptr;
		}
		else
		{
			node->left=ptr->right;
			ptr->right->parent=node;
			ptr->right=node;
			node->parent=ptr;
		}
		ptr=node;
	}
	niv[root->ind]=1;
	DFS(root);
	tata_lant[lant[root->ind]]=0;
	for(register int i=1;i<=M;++i)
	{
		fin>>x>>y;
		fout<<V[LCA(x,y)]<<"\n";
	}
	fin.close();
	fout.close();
	return 0;
}