#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cstdlib>#include <cmath>#include <utility>#include <vector>#include <queue>#include <map>#include <set>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))using namespace std;int a[50005],N,Q,l,r,f[50005][20],g[50005][20];void RMQ_ST(int n, int a[])//f[i][j]=max(a[i..i+2^j-1]){    for(int i=1; i<=n; i++)    {        f[i][0]=a[i];        g[i][0]=a[i];    }    int m=floor(log(n*1.0)/log(2.0));    for(int j=1; j<=m; j++)        for(int i=1; i<=n-(1<<j)+1; i++)        {            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);            g[i][j]=min(g[i][j-1],g[i+(1<<(j-1))][j-1]);        }}int main(){    scanf("%d%d",&N,&Q);    for(int i=1; i<=N; i++)        scanf("%d",&a[i]);    RMQ_ST(N,a);    for(int i=0; i<Q; i++)    {        scanf("%d%d",&l,&r);        int k=floor(log((r-l+1)*1.0)/log(2.0));        printf("%d\n",max(f[l][k],f[r-(1<<k)+1][k])-min(g[l][k],g[r-(1<<k)+1][k]));    }    return 0;}