#include <bits/stdc++.h>
using namespace std;
#define N 1000010
#define ll long long
ll n, m, x, y;
ll a[N], lg[N], f[N][20], f1[N][20];
signed main() 
{
	cin >> n >> m;
	lg[1] = 0;
	for (int i = 2; i <= n; i++) 
	lg[i] = lg[i >> 1] + 1;
	for (int i = 1; i <= n; i++) 
	cin >> f[i][0];
	for (int j = 1; j <= lg[n]; j++)
		for (int i = 1; i + (1 << j) - 1 <= n; i++) 
		{
			f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
			f1[i][j]=max(f1[i][j - 1], f1[i + (1 << (j - 1))][j - 1]);
		}
	for (int i = 1; i <= m; i++) 
	{
		cin >> x >> y;
		int l = lg[y - x + 1];
		cout << max(f1[x][l], f1[y - (1 << l) + 1][l]) - min(f[x][l], f[y - (1 << l) + 1][l]) << " ";
	}
	
	return 0;
	}

输出负数