//#define __DEBUG
#include <stdio.h>
#include <queue>
#include <stack>
#include <deque>
#include <vector>
using namespace std;
const int MAX = 65536;
const int MAX_VALUE = (1 << 30);
#define ASSERT(X, S) { if(!(X)) { S; int i = 0; i /= i; } }

int min(int a, int b)
{
    return a < b ? a : b;
}

int max(int a, int b)
{
    return a < b ? b : a;
}

class line_tree
{
private:
    const static int SIZE = (((MAX - 1) << 2) - 1);
    class node
    {
    public:
        int lower_bound;
        int upper_bound;
        int max;
        int min;
    } n[SIZE];

    int node_size;

    static inline int lc(int i) { return rc(i) - 1; }
    static inline int rc(int i) { return ((i + 1) << 1); }
    static inline int pc(int i) { return ((i - 1) >> 1); }
    static inline bool leaf(const node& i) { return i.lower_bound == i.upper_bound; }
    inline bool leaf(int i) { return leaf(n[i]); }
    static inline int mid(const node& i) { return ((i.lower_bound + i.upper_bound) >> 1); }
    inline int mid(int i) { return mid(n[i]); }
    static inline bool g_l(const node& i, int pos) { return mid(i) >= pos; }
    inline bool g_l(int i, int pos) { return g_l(n[i], pos); }
    static inline bool g_r(const node& i, int pos) { return !g_l(i, pos); }
    inline bool g_r(int i, int pos) { return g_r(n[i], pos); }

    static inline void push(queue<int>& q, int i, int l, int u)
    {
        ASSERT(l <= u, printf("insert %d with lower_bound = %d, upper_bound = %d\n", i, l, u));
        q.push(i);
        q.push(l);
        q.push(u);
    }

    static inline void pop(queue<int>& q, int& i, int& l, int& u)
    {
        i = q.front();
        q.pop();
        l = q.front();
        q.pop();
        u = q.front();
        q.pop();
    }

public:
    void clear()
    {
        for(int i = 0; i < node_size; i++)
        {
            n[i].min = MAX_VALUE;
            n[i].max = -MAX_VALUE;
        }
    }

    void create(int MAX)
    {
        node_size = 0;
        queue<int> q;
        push(q, 0, 0, MAX - 1);
        while(!q.empty())
        {
            int i, l, u;
            pop(q, i, l, u);
            n[i].lower_bound = l;
            n[i].upper_bound = u;
            if(i >= node_size) node_size = i + 1;
            if(!leaf(i))
            {
#ifdef __DEBUG
                printf("adding node %d, [%d, %d]\n", lc(i), l, mid(i));
                printf("adding node %d, [%d, %d]\n", rc(i), mid(i) + 1, u);
#endif
                push(q, lc(i), l, mid(i));
                push(q, rc(i), mid(i) + 1, u);
            }
        }
        clear();
#ifdef __DEBUG
        for(int i = 0; i < node_size; i++)
        {
            if(!leaf(n[pc(i)]))
            {
                if(i + 1 < node_size && pc(i) == pc(i + 1))
                {
                    ASSERT(n[i].upper_bound == n[i + 1].lower_bound - 1,
                           printf("n[%d].upper_bound{%d} != n[%d].lower_bound{%d} - 1", i, n[i].upper_bound, i + 1, n[i + 1].lower_bound));
                }
                if(i > 0)
                {
                    ASSERT(n[i].lower_bound == n[pc(i)].lower_bound || n[i].upper_bound == n[pc(i)].upper_bound,
                           printf("%d", i));
                }
            }
        }
#endif
    }

    void dump(int start, int end)
    {
        for(int i = 0; i < node_size; i++)
        {
            if((i == 0 || !leaf(pc(i))) &&
               ((n[i].lower_bound >= start && n[i].lower_bound <= end) ||
                (n[i].upper_bound >= start && n[i].upper_bound <= end)))
                printf("node[%d] [%d, %d] min = %d, max = %d\n", i, n[i].lower_bound, n[i].upper_bound, n[i].min, n[i].max);
        }
    }

    void insert(int pos, int v)
    {
        int i = 0;
        while(1)
        {
            if(n[i].min > v) n[i].min = v;
            if(n[i].max < v) n[i].max = v;
            if(leaf(n[i])) break;
            else if(g_l(n[i], pos)) i = lc(i);
            else i = rc(i);
        }
    }

    void insert(const vector<int>& values)
    {
        node_size = 0;
        queue<int> q;
        stack<int> s;
        push(q, 0, 0, values.size() - 1);
        while(!q.empty())
        {
            int i, l, u;
            pop(q, i, l, u);
            n[i].lower_bound = l;
            n[i].upper_bound = u;
            if(leaf(i))
            {
                n[i].min = values[l];
                n[i].max = values[l];
                if(i >= node_size) node_size = i + 1;
            }
            else
            {
                s.push(i);
                push(q, lc(i), l, mid(i));
                push(q, rc(i), mid(i) + 1, u);
            }
        }
        while(!s.empty())
        {
            int p = s.top();
            s.pop();
            n[p].min = min(n[lc(p)].min, n[rc(p)].min);
            n[p].max = max(n[lc(p)].max, n[rc(p)].max);
        }
    }

    void query(const int is, const int ie, int& min, int& max)
    {
        min = MAX_VALUE;
        max = -MAX_VALUE;
        queue<int> q;
        push(q, 0, is, ie);
        while(!q.empty())
        {
            ASSERT(q.size() <= 5 * 3, printf("q.size() == %d\n", q.size()));
            int i;
            int start;
            int end;
            pop(q, i, start, end);
#ifdef __DEBUG
            printf("query n[%d]{lower_bound == %d, upper_bound == %d, min == %d, max == %d} for range [%d, %d]\n",
                   i, n[i].lower_bound, n[i].upper_bound, n[i].min, n[i].max, start, end);
#endif
            if(n[i].lower_bound >= start &&
               n[i].upper_bound <= end)
            {
                if(min > n[i].min) min = n[i].min;
                if(max < n[i].max) max = n[i].max;
            }
            else if(n[i].min < min || n[i].max > max)
            {
                if(g_l(n[i], end))
                    push(q, lc(i), start, end);
                else if(g_r(n[i], start))
                    push(q, rc(i), start, end);
                else
                {
                    push(q, lc(i), start, mid(i));
                    push(q, rc(i), mid(i) + 1, end);
                }
            }
        }
    }
};

int main()
{
    int n, m;
    line_tree* ptree = new line_tree();
    line_tree& tree = *ptree;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        // line_tree* ptree = new line_tree();
        // line_tree& tree = *ptree;
        // tree.create(n);
        vector<int> values;
        for(int i = 0; i < n; i++)
        {
            int t;
            scanf("%d", &t);
            // tree.insert(i, t);
            values.push_back(t);
        }
        tree.insert(values);
#ifdef __DEBUG
        tree.dump(0, n - 1);
#endif

        for(int i = 0; i < m; i++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            int min, max;
            if(a == b)
            {
                min = max;
            }
            else if(b - a < 16)
            {
                min = values[a - 1];
                max = values[a - 1];
                for(int i = a; i < b; i++)
                {
                    if(values[i] < min) min = values[i];
                    if(values[i] > max) max = values[i];
                }
            }
            else tree.query(a - 1, b - 1, min, max);
            printf("%d\n", max - min);
        }
        // delete ptree;
    }
    delete ptree;
}