#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>

using namespace std;

int main()
{
	int N;
	int Q;
	while(scanf("%d%d", &N, &Q) != EOF)
	{
    	vector<int> Height(N);
		int K = int(sqrt(N + 0.0));
		if(K*K != N)
		{
			++ K;
		}
		vector<int> LocalMax(K);
		vector<int> LocalMin(K);
		int j = 0;
		int M = N / K;
		int TmpMax = 0;
		int TmpMin = 1000000;
	    for(int i = 0; i < K; ++ i)
	    {
			int TmpMax = 0;
		    int TmpMin = 1000000;
			for(int j = 0; j < M; ++ j)
			{
				cin >> Height[i*M + j];
				if(TmpMax < Height[i*M + j])
				{
					TmpMax = Height[i*M + j];
				}
				if(TmpMin > Height[i*M + j])
				{
					TmpMin = Height[i*M + j];
				}
			}
			LocalMax[i] = TmpMax;
			LocalMin[i] = TmpMin;
	    }
		//copy(LocalMax.begin(), LocalMax.end(), ostream_iterator<int>(cout, " ")), cout << endl;
		//copy(LocalMin.begin(), LocalMin.end(), ostream_iterator<int>(cout, " ")), cout << endl;
	    for(int i = 0; i < Q; ++ i)
    	{
	    	int A;
		    int B;
	    	scanf("%d%d", &A, &B);
		    if(A == B)
	    	{
		    	printf("0\n");
		    }
		    else
	    	{
		    	int m = (A - 1) / M;
				int n = (B - 1) / M ;
				TmpMax = 0;
				TmpMin = 1000000;
                if(n == m)
				{
					for(int j = A - 1; j < B; ++ j)
					{
						if(TmpMax < Height[j])
						{
							TmpMax = Height[j];
						}
						if(TmpMin > Height[j])
						{
							TmpMin = Height[j];
						}
					}
				}
				else
				{
					for(int j = A - 1; j < (m + 1)*M && j < N; ++ j)
					{
						if(TmpMax < Height[j])
						{
							TmpMax = Height[j];
						}
						if(TmpMin > Height[j])
						{
							TmpMin = Height[j];
						}
					}
					for(int j = n*M; j < B && j < N; ++ j)
					{
						if(TmpMax < Height[j])
						{
							TmpMax = Height[j];
						}
						if(TmpMin > Height[j])
						{
							TmpMin = Height[j];
						}
					}
					if(n - m >= 2)
					{
						TmpMax = max(TmpMax, *max_element(LocalMax.begin() + (m + 1), LocalMax.begin() + n));
						TmpMin = min(TmpMin, *min_element(LocalMin.begin() + (m + 1), LocalMin.begin() + n));
					}
				}
				int Max = TmpMax;
				int Min = TmpMin;
		        printf("%d\n", Max - Min);
		    }
	    }
	}
}