#include <bits/stdc++.h>
using namespace std;
int n,q;
vector<int> a;
vector< pair<int,int> > node;
int resmax, resmin;
void Init_Tree(int k, int l, int r, int i)
{
if(l>i || r<i) return;
if(l==r)
{
node[k]=make_pair(a[i],a[i]);
return;
}
int m=(l+r)/2;
Init_Tree(2*k,l,m,i);
Init_Tree(2*k+1,m+1,r,i);
node[k]=make_pair(max(node[2*k].first, node[2*k+1].first),min(node[2*k].second, node[2*k+1].second));
}
void Init()
{
scanf("%d%d",&n,&q);
a.resize(n+2);
node.resize(4*n);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
Init_Tree(1,1,n,i);
}
}
void Query(int k, int l, int r, int A, int B)
{
if(l>B || r<A) return;
if(A<=l && B>=r)
{
resmax=max(resmax,node[k].first);
resmin=min(resmin,node[k].second);
return;
}
int m=(l+r)/2;
Query(2*k,l,m,A,B);
Query(2*k+1,m+1,r,A,B);
}
void Solve()
{
for (int i=1;i<=q;i++)
{
int A, B;
scanf("%d%d",&A,&B);
resmax=0;
resmin=10000000;
Query(1,1,n,A,B);
printf("%dn",resmax-resmin);
}
}
int main()
{
Init();
Solve();
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKaW50IG4scTsKdmVjdG9yPGludD4gYTsKdmVjdG9yPCBwYWlyPGludCxpbnQ+ID4gbm9kZTsKaW50IHJlc21heCwgcmVzbWluOwogCnZvaWQgSW5pdF9UcmVlKGludCBrLCBpbnQgbCwgaW50IHIsIGludCBpKQp7CiAgICBpZihsPmkgfHwgcjxpKSByZXR1cm47CiAgICBpZihsPT1yKQogICAgewogICAgICAgIG5vZGVba109bWFrZV9wYWlyKGFbaV0sYVtpXSk7CiAgICAgICAgcmV0dXJuOwogICAgfQogICAgaW50IG09KGwrcikvMjsKICAgIEluaXRfVHJlZSgyKmssbCxtLGkpOwogICAgSW5pdF9UcmVlKDIqaysxLG0rMSxyLGkpOwogICAgbm9kZVtrXT1tYWtlX3BhaXIobWF4KG5vZGVbMiprXS5maXJzdCwgbm9kZVsyKmsrMV0uZmlyc3QpLG1pbihub2RlWzIqa10uc2Vjb25kLCBub2RlWzIqaysxXS5zZWNvbmQpKTsKfQogCnZvaWQgSW5pdCgpCnsKICAgIHNjYW5mKCIlZCVkIiwmbiwmcSk7CiAgICBhLnJlc2l6ZShuKzIpOwogICAgbm9kZS5yZXNpemUoNCpuKTsKICAgIGZvciAoaW50IGk9MTtpPD1uO2krKykKICAgIHsKICAgICAgICBzY2FuZigiJWQiLCZhW2ldKTsKICAgICAgICBJbml0X1RyZWUoMSwxLG4saSk7CiAgICB9Cn0KIAp2b2lkIFF1ZXJ5KGludCBrLCBpbnQgbCwgaW50IHIsIGludCBBLCBpbnQgQikKewogICAgaWYobD5CIHx8IHI8QSkgcmV0dXJuOwogICAgaWYoQTw9bCAmJiBCPj1yKQogICAgewogICAgICAgIHJlc21heD1tYXgocmVzbWF4LG5vZGVba10uZmlyc3QpOwogICAgICAgIHJlc21pbj1taW4ocmVzbWluLG5vZGVba10uc2Vjb25kKTsKICAgICAgICByZXR1cm47CiAgICB9CiAgICBpbnQgbT0obCtyKS8yOwogICAgUXVlcnkoMiprLGwsbSxBLEIpOwogICAgUXVlcnkoMiprKzEsbSsxLHIsQSxCKTsKfQogCnZvaWQgU29sdmUoKQp7CiAgICBmb3IgKGludCBpPTE7aTw9cTtpKyspCiAgICB7CiAgICAgICAgaW50IEEsIEI7CiAgICAgICAgc2NhbmYoIiVkJWQiLCZBLCZCKTsKICAgICAgICByZXNtYXg9MDsKICAgICAgICByZXNtaW49MTAwMDAwMDA7CiAgICAgICAgUXVlcnkoMSwxLG4sQSxCKTsKICAgICAgICBwcmludGYoIiVkbiIscmVzbWF4LXJlc21pbik7CiAgICB9Cn0KIAppbnQgbWFpbigpCnsKICAgIEluaXQoKTsKICAgIFNvbHZlKCk7Cn0=