/* Christoph Schwirzer */
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 128 * 1024;
int a[N];
int first[2*N], last[2*N], cnt[2*N];
const int oo = 1000000000;

struct triple
{
	int t[3];
	int& operator[](const int &n) { return t[n]; }
	const int& operator[](const int &n) const { return t[n]; }
} b[2*N], zero;
struct cmp
{
	bool operator()(const int &x, const int &y) const
	{
		if (cnt[x] != cnt[y])
			return cnt[x] > cnt[y];
		return x < y;
	}
};
int c[6];
triple p;
inline triple merge(const triple &ch1, const triple &ch2)
{
	for (int i=0; i<3; i++)
	{
		c[i] = ch1[i];
		c[i+3] = ch2[i];
	}
	sort(c, c+6, cmp());
	int next = 0;
	for (int i=0; i<6 && next < 3; i++)
		if (i == 0 || c[i] != c[i-1])
		{
			p[next] = c[i];
			next++;
		}
	for (int i=next; i<3; i++)
		p[i] = c[i];
	return p;
}
// [x, y)
triple query(int x, int y, int node=1, int left=0, int right=N)
{
	if (y <= left || x >= right)
		return zero;
	if (x <= left && right <= y)
		return b[node];
	return merge(query(x, y, 2*node, left, left + (right - left) / 2),
		query(x, y, 2*node+1, left + (right - left) / 2, right));
}
// [x, y]
int getlen(int x, int y, int z)
{
	return max(min(last[z], y) - max(first[z], x) + 1, 0);
}
int main()
{
	for (int i=0; i<3; i++)
		zero[i] = 0;
	int n;
	while (scanf("%d", &n), n)
	{
		int q;
		scanf("%d", &q);
		for (int i=0; i<2*N; i++)
			first[i] = oo;
		memset(cnt, 0, sizeof(cnt));
		for (int i=0; i<n; i++)
		{
			scanf("%d", a+i);
			a[i] += N;
			if (first[a[i]] == oo)
				first[a[i]] = i;
			last[a[i]] = i;
			cnt[a[i]]++;
			b[N + i][0] = b[N + i][1] = b[N + i][2] = a[i];
		}
		for (int i=n; i<N; i++)
			b[N + i][0] = b[N + i][1] = b[N + i][2] = 0;
		cnt[0] = -1;
		for (int i=N-1; i>=1; i--)
			b[i] = merge(b[2*i], b[2*i+1]);
		for (int i=0; i<q; i++)
		{
			int x, y;
			scanf("%d%d", &x, &y);
			triple t = query(x-1, y);
			int best = -1, bestv = 0;
			for (int i=0; i<3; i++)
			{
				if (t[i] == 0)
					continue;
				int len = getlen(x-1, y-1, t[i]);
				if (len > best || (len == best && t[i] < bestv))
				{
					best = len;
					bestv = t[i];
				}
			}
			printf("%d\n", best);
		}
	}
	return 0;
}
