include [HTML_REMOVED]

define P pair < int, int >

using namespace std;

template < typename T >
inline void read(T &x)
{
x = 0;
char c;
while ((c = getchar()) < 48 || c > 57);
do
x = (x << 1) + (x << 3) + (c ^ 48);
while ((c = getchar()) > 47 && c < 58);
}

char OUTPUT[20];

template < typename T >
inline void write(T x)
{
int SIZE = 0;
do
{
OUTPUT[++SIZE] = x % 10 | 48;
x /= 10;
}while (x);
while (SIZE)
putchar(OUTPUT[SIZE–]);
}

template < typename T >
inline void writeln(T x)
{
write(x);
putchar(10);
}
//树状数组：询问用减，修改用加
int lowbit(int x)
{
return x & (-x);
}

const int L = 50005;
int n, a[L];
P t[L];

int Add(int x, int num)
{
while (x <= n)
{
if (num > t[x].first) t[x].first = num;
if (num < t[x].second) t[x].second = num;
x += lowbit(x);
}
}

P Query(int l, int r)
{
if (r <= l) return make_pair(a[l], a[l]);
P ans;
if (r - lowbit(r) > l)
{
ans = Query(l, r - lowbit(r));
return make_pair(max(t[r].first, ans.first), min(t[r].second, ans.second));
}
ans = Query(l, r - 1);
return make_pair(max(t[r].first, ans.first), min(t[r].second, ans.second));
}

int main()
{
read(n);
fill(t + 1, t + n + 1, make_pair(INT_MIN, INT_MAX));
int m, l, r;
read(m);
for (int i = 1; i <= n; ++i)
{
read(a[i]);
Add(i, a[i]);
}
while (m–)
{
read(l);
read(r);
P ans = Query(l, r);
writeln(ans.first - ans.second);
}
return 0;
}