#include<stdio.h>
long max,pmax,x,y,i,n,m,j,n2,n3,n1,p,k,t,a[1001],s[1001],st[1001],h[10001];
int main()
{
    freopen("cuburi2.in","r",stdin);
    freopen("cuburi2.out","w",stdout);
    scanf("%ld%ld",&n,&m);
    for(i=1;i<=n;i++)
                     scanf("%ld",&h[i]);
    for(i=1;i<=m;i++)
    {
                     scanf("%ld%ld",&x,&y);
                     for(j=1;j<=n3;j++) st[j]=0;
                     for(j=1;j<=n2;j++) s[j]=0;
                     max=0;
                     for(j=x;j<=y;j++)
                     {
                                      if(h[j]>max)
                                      {
                                                  max=h[j];
                                                  pmax=j;
                                      }
                     }
                     if(pmax!=x && pmax!=y)
                     {
                           n2=n3=0;
                           p=h[x];
                           do
                           {     
                                 st[++n3]=p%10;
                                 s[++n2]=p%10;
                                 p/=10;
                           }          
                           while(p);
                           for(j=x+1;j<=pmax-1;j++)
                           {
                                        p=h[j];
                                        n1=0;
                                        do
                                        {
                                            a[++n1]=p%10;
                                            p/=10;
                                        }
                                        while(p);
                                          t=0;
                                        if(n2>n1)
                                        {
                                                 for(k=n1+1;k<=n2;k++)
                                                                      a[k]=0;
                                                 n1=n2;
                                        }
                                        else
                                        {
                                            for(k=n2+1;k<=n1;k++)
                                                                 s[k]=0;
                                        }
                                        for(k=1;k<=n1;k++)
                                        {
                                                          s[k]+=a[k]+t;
                                                          t=s[k]/10;
                                                          s[k]=s[k]%10;
                                        }
                                        if(t>0) s[++n2]=t;
                                          t=0;
                                        if(n3>n2)
                                        {
                                                 for(k=n2+1;k<=n3;k++)
                                                                      s[k]=0;
                                                 n2=n3;
                                        }
                                        else
                                        {
                                            for(k=n3+1;k<=n2;k++)
                                                                 st[k]=0;
                                        }
                                        for(k=1;k<=n2;k++)
                                        {                
                                                         st[k]+=s[k]+t;
                                                         t=st[k]/10;
                                                         st[k]=st[k]%10;
                                        }
                                        if(t>0) st[++n3]=t;
                           }    
                           for(j=1;j<=n2;j++) s[j]=0;
                           for(j=y;j>=pmax+1;j--)
                           {
                                        p=h[j];
                                        n1=0;
                                        do
                                        {
                                            a[++n1]=p%10;
                                            p/=10;
                                        }
                                        while(p);
                                        t=0;
                                        if(n2>n1)
                                        {
                                                 for(k=n1+1;k<=n2;k++)
                                                                      a[k]=0;
                                                 n1=n2;
                                        }
                                        else
                                        {
                                            for(k=n2+1;k<=n1;k++)
                                                                 s[k]=0;
                                        }
                                        for(k=1;k<=n1;k++)
                                        {
                                                          s[k]+=a[k]+t;
                                                          t=s[k]/10;
                                                          s[k]=s[k]%10;
                                        }
                                        if(t>0) s[++n2]=t;
                                          t=0;
                                        if(n3>n2)
                                        {
                                                 for(k=n2+1;k<=n3;k++)
                                                                      s[k]=0;
                                                 n2=n3;
                                        }
                                        else
                                        {
                                            for(k=n3+1;k<=n2;k++)
                                                                 st[k]=0;
                                        }
                                        for(k=1;k<=n2;k++)
                                        {                
                                                         st[k]+=s[k]+t;
                                                         t=st[k]/10;
                                                         st[k]=st[k]%10;
                                        }
                                        if(t>0) st[++n3]=t;
                           }  
                                   
                     }
                     else if(pmax==x)
                     {
                           n2=n3=0;
                           p=h[y];
                           do
                           {     
                                 st[++n3]=p%10;
                                 s[++n2]=p%10;
                                 p/=10;
                           }          
                           while(p);
                           for(j=y-1;j>=x+1;j--)
                           {
                                        p=h[j];
                                        n1=0;
                                        do
                                        {
                                            a[++n1]=p%10;
                                            p/=10;
                                        }
                                        while(p);
                                        t=0;
                                        if(n2>n1)
                                        {
                                                 for(k=n1+1;k<=n2;k++)
                                                                      a[k]=0;
                                                 n1=n2;
                                        }
                                        else
                                        {
                                            for(k=n2+1;k<=n1;k++)
                                                                 s[k]=0;
                                        }
                                        for(k=1;k<=n1;k++)
                                        {
                                                          s[k]+=a[k]+t;
                                                          t=s[k]/10;
                                                          s[k]=s[k]%10;
                                        }
                                        if(t>0) s[++n2]=t;
                                        t=0;
                                        if(n3>n2)
                                        {
                                                 for(k=n2+1;k<=n3;k++)
                                                                      s[k]=0;
                                                 n2=n3;
                                        }
                                        else
                                        {
                                            for(k=n3+1;k<=n2;k++)
                                                                 st[k]=0;
                                        }
                                        for(k=1;k<=n2;k++)
                                        {                
                                                         st[k]+=s[k]+t;
                                                         t=st[k]/10;
                                                         st[k]=st[k]%10;
                                        }
                                        if(t>0) st[++n3]=t;
                           }    
                          
                     }
                     else if(pmax==y)
                     {
                           n2=n3=0;
                           p=h[x];
                           do
                           {     
                                 st[++n3]=p%10;
                                 s[++n2]=p%10;
                                 p/=10;
                           }          
                           while(p);
                           for(j=x+1;j<y;j++)
                           {
                                        p=h[j];
                                        n1=0;
                                        do
                                        {
                                            a[++n1]=p%10;
                                            p/=10;
                                        }
                                        while(p);
                                        t=0;
                                        if(n2>n1)
                                        {
                                                 for(k=n1+1;k<=n2;k++)
                                                                      a[k]=0;
                                                 n1=n2;
                                        }
                                        else
                                        {
                                            for(k=n2+1;k<=n1;k++)
                                                                 s[k]=0;
                                        }
                                        for(k=1;k<=n1;k++)
                                        {
                                                          s[k]+=a[k]+t;
                                                          t=s[k]/10;
                                                          s[k]=s[k]%10;
                                        }
                                        if(t>0) s[++n2]=t;
                                        t=0;
                                        if(n3>n2)
                                        {
                                                 for(k=n2+1;k<=n3;k++)
                                                                      s[k]=0;
                                                 n2=n3;
                                        }
                                        else
                                        {
                                            for(k=n3+1;k<=n2;k++)
                                                                 st[k]=0;
                                        }
                                        for(k=1;k<=n2;k++)
                                        {                
                                                         st[k]+=s[k]+t;
                                                         t=st[k]/10;
                                                         st[k]=st[k]%10;
                                        }
                                        if(t>0) st[++n3]=t;
                           }       
                       
                     }
                     printf("%ld ",pmax);
                     for(j=n3;j>=1;j--)
                                       printf("%ld",st[j]);
                     printf("\n");
    }
    return 0;
}