#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int N = 50010;const int INF = 0x3f3f3f3f;int rmin = INF, rmax = -INF;//用全局变量来储存查询区域的最值struct Node{    int left, right;    int maxi, mini;    int mid()    {        return (left+right)>>1;    }} tree[4*N];void build(int root, int l, int r)//建树过程{    tree[root].left = l;    tree[root].right = r;    tree[root].mini = INF;    tree[root].maxi = -INF;    if(l == r)    {        return;    }    else    {        build(2*root, l, tree[root].mid());        build(2*root+1, tree[root].mid()+1, r);    }}void minsert(int root, int pose, int value){    if( tree[root].left == tree[root].right )//找到位置插入    {       tree[root].mini = tree[root].maxi = value;        return;    }    tree[root].mini = min(tree[root].mini, value);    tree[root].maxi = max(tree[root].maxi, value);    if(pose <= tree[root].mid())        minsert(root*2, pose, value);    else        minsert(root*2 + 1, pose, value);}void query(int root, int s, int e){    if(tree[root].mini > rmin && tree[root].maxi < rmax)/*若某树的最小值大于所求的最小值，则它的子树的最小值必定大于所求最小值，最大值同理*/        return;    if(tree[root].left == s && tree[root].right == e)    {        rmin = min(rmin, tree[root].mini);        rmax = max(rmax, tree[root].maxi);        return;    }    if(e <= tree[root].mid())    {        query(root*2, s,e);    }    else if(s > tree[root].mid())    {        query(root*2+1, s, e);    }    else    {        query(root*2, s, tree[root].mid());        query(root*2+1, tree[root].mid() + 1, e);    }}int main(){    int n, q, he, a, b;    scanf("%d %d", &n, &q);    {        build(1,1,n);        for(int i = 1; i <= n; i++)        {            scanf("%d", &he);            minsert(1, i, he);        }        while(q--)        {            scanf("%d %d", &a, &b);            rmin = INF;            rmax = -INF;            query(0, a, b);            printf("%d\n",rmax-rmin);        }    }    return 0;}