#include<bits/stdc++.h>
using namespace std;
int n, q;
const int N = 2e5 + 10;
int f_min[N][22];
int f_max[N][21]; 
int main()
{
	freopen("P2880_2.in", "r", stdin);
	freopen("P2880_2.out", "w", stdout);
	cin >> n >> q;
	for(int i = 1; i <= n; i++)
	{
		cin >> f_min[i][0];
		f_max[i][0] = f_min[i][0];
	}
	for(int j = 1; j <= 21; j++)
	{
		for(int i = 1; i <= n; i++)
		{
			if(i + (1 << j) - 1 <= n)
			{
				f_max[i][j] = max(f_max[i][j - 1], f_max[i + (1 << j) - 1][j - 1]);
				f_min[i][j] = min(f_min[i][j - 1], f_min[i + (1 << j) - 1][j - 1]);
			}
		}
	}
	for(int i = 1; i <= q; i++)
	{
		int st, ed;
		cin >> st >> ed;
		int k = log2(ed - st + 1);
		cout << max(f_max[st][k], f_max[ed - (1 << k) + 1][k]) - min(f_min[st][k], f_min[ed - (1 << k) + 1][k])<< endl;
	}
	return 0;
}