/*#include <fstream>
#define NMAX 100005

using namespace std;
ifstream fin("a.in");
ofstream fout("a.out");

long long int L[NMAX], H[NMAX], dp[NMAX][25], lg[NMAX], n, s[NMAX], q, x, y, m;
long long int minim(int x, int y)
{
    int len=y-x+1;
    len = lg[len];
    return min(dp[x][len], dp[y - (1 << len) + 1][len]);
}
long long int solutie (int x, int y)
{
    int lungime, inaltime;
    lungime=s[y]-s[x-1];
    inaltime=minim(x,y);
    return lungime*inaltime;
}

int main()
{
    int i, j;
    fin>>n;
    for (i=1; i<=n; i++)
        {fin>>L[i]>>H[i]; s[i]=s[i-1]+L[i];}
    lg[1]=0;
    for (i=2; i<=NMAX-5; i++)
        lg[i]=lg[i/2]+1;
    for (i=1; i<=n; i++)
        dp[i][0] = H[i];
    for (j=1; (1<<j)<=n; j++)
        for (i=1; i<=n-(1<<j)+1; i++)
            dp[i][j]=min(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);



    fin>>q;
    for (i=1; i<=q; i++)
    {
        fin>>x>>y;
        fout<<solutie(x, y)<<'\n';
    }
    return 0;
}*/
#include <fstream>
#define NMAX 100005

using namespace std;
ifstream fin("rmq.in");
ofstream fout("rmq.out");

long long int L[NMAX], H[NMAX], dp[NMAX][25], lg[NMAX], n, s[NMAX], q, x, y, m;
long long int minim(int x, int y)
{
    int len=y-x+1;
    len = lg[len];
    return min(dp[x][len], dp[y - (1 << len) + 1][len]);
}
long long int solutie (int x, int y)
{
    int lungime, inaltime;
    lungime=s[y]-s[x-1];
    inaltime=minim(x,y);
    return lungime*inaltime;
}

int main()
{
    int i, j;
    fin>>n>>q;
    for (i=1; i<=n; i++)
        fin>>H[i];
    lg[1]=0;
    for (i=2; i<=NMAX-5; i++)
        lg[i]=lg[i/2]+1;
    for (i=1; i<=n; i++)
        dp[i][0] = H[i];
    for (j=1; (1<<j)<=n; j++)
        for (i=1; i<=n-(1<<j)+1; i++)
            dp[i][j]=min(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);


    for (i=1; i<=q; i++)
    {
        fin>>x>>y;
        fout<<minim(x, y)<<'\n';
    }
    return 0;
}