#include <stdio.h>

#define maxn 100010
#define min(a, b) a<b ? a:b

int m[maxn][18];

int logaritm(int );
int count(int );
int main()
{
	int n, m1, x, y, i, j;
	freopen("rmq.in", "r", stdin);
	freopen("rmq.out", "w", stdout);

	scanf("%d %d", &n, &m1);
	for(i=1; i<=n; ++i)
	{
		scanf("%d", &m[i][0]);
	}
/*
	lo[1]=0;
	for(i=2; i<=n; i++)
		lo[i]=lo[i/2]+1;*/

//	for(i=1; i<=n; i++)
  //		m[i][0]=a[i];

	for(j=1; (1<<j) <= n; j++)
		for(i=1; i+ (1 << (j-1)) <=n; i++)
			m[i][j]=min(m[i][j-1], m[i+(1<<(j-1))][j-1]);

	for(i=1; i<=m1; i++)
	{
		scanf("%d %d", &x, &y);
		int k=logaritm(y-x);
		printf("%d\n", min(m[x][k], m[y-(1<<k)+1][k]));
	}

	return 0;
}                     
int logaritm(int n)
{
	n=n|(n>>1);
	n=n|(n>>2);
	n=n|(n>>4);
	n=n|(n>>8);
//	n=n|(n>>16);
	return count(n);
}
int count(int n)
{
	int nr=0;

	if(n)
	while(n&=n-1) nr++;

	return nr;
}