#include<stdio.h>
#define N 250002
#define M 1000
int v[N];
int n,m,A[M],B[M];
int maxim(int a, int b)
{
	int max=0,poz;
	for (int i=a; i<=b; ++i)
		if (max<v[i]) 
		{
			max=v[i];
			poz=i;
		}
	return poz;
}
void descompun (int x)
{
	int num=0;
	while (x)
	{
		A[++num]=x%10;
		x/=10;
	}
	A[0]=num;
}
void descompun1 (int x)
{
	int num=0;
	while (x)
	{
		B[++num]=x%10;
		x/=10;
	}
	B[0]=num;
}
void mul(int A[], int B)   
{   
      int i, t = 0;   
      for (i = 1; i <= A[0] || t; i++, t /= 10)   
              A[i] = (t += A[i] * B) % 10;   
      A[0] = i - 1;   
}  
/*void add(int s[], int t[])   
{   
      int i,minte,lim;   
      if (s[0]>=t[0]) lim=s[0]; else lim=t[0];
	for (int i=1; i<=lim; ++i)
	{
		ibt c=s[i]+t[i]+minte;
		s[i]=c%10;
		minte=c/10;
	}		
	if (minte) s[++s[0]]=minte; 
}  */
void add(int A[], int B[])   
{   
      int i, t = 0;   
      for (i=1; i<=A[0] || i<=B[0] || t; i++, t/=10)   
              A[i] = (t += A[i] + B[i]) % 10;   
      A[0] = i - 1;   
}  

void calcul(int a,int b,int x)
{
	for (int i=a; i<=b; ++i)
	{
		descompun(v[i]);
		if (i!=x)
		{
		if (x-i>0)
		mul(A,x-i);
		if (i-x>0)
			mul(A,i-x);
		add(B,A);
		}
	}
	for (int i=B[0]; i>0; --i) printf("%d",B[i]);
	printf("\n");
}
void citire()
{
	freopen("cuburi2.in","r",stdin);
	freopen("cuburi2.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1; i<=n; ++i)
	{
		int r;
		scanf("%d",&r);
		v[i]=r;
	}
	for (int i=1; i<=m; ++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		int p=maxim(x,y);
		printf("%d ",p);
		calcul(x,y,p);
		for (int j=1; j<=B[0]; ++j) A[j]=B[j]=0;
		A[0]=B[0]=0;
	}
}
int main()
{
	citire();
	return 0;
}