// Author: Adrian Kuegel
// Date: 9. 6. 2007

#include <stdio.h>
#include <assert.h>

#define MAXN 100000
#define MAXQ 100000

int a[MAXN],c[MAXN],ps[MAXN+1];
int next_i[MAXN],prev_j[MAXN];
int from[MAXQ], to[MAXQ], ind[MAXQ];
int num[MAXQ], freq[MAXQ];
int cnt[MAXN], s[MAXN];

int main() {
	int n,q;
	freopen("frequent.in","r",stdin);
	while(scanf("%d %d",&n,&q) == 2 && n) {
		assert(n >= 1 && n <= 100000 && q >= 1 && q <= 100000);
		int l = 0;
		for (int i=0; i<n; i++) {
			int t;
			scanf("%d",&t);
			assert(t >= -100000 && t <= 100000);
			if (!l || a[l-1] != t) {
				assert(!l || a[l-1] < t);
				a[l] = t;
				c[l] = 0;
				l++;
				ps[l] = ps[l-1];
			}
			++ps[l];
			++c[l-1];
			cnt[i] = 0;
		}
		assert(ps[l] == n);
		for (int i=0,j=0; i<n; i++) {
			next_i[i] = j; // next_i[i] points to smallest position in ps with ps[j] >= i
			if (ps[j] == i)
				++j;
		}
		for (int i=n-1,j=l; i>=0; --i) {
			prev_j[i] = j-1; // prev_j[i] points to biggest position j in ps with ps[j+1] <= i+1
			if (ps[j] == i+1)
				--j;
		}
		for (int i=0; i<q; ++i) {
			scanf("%d %d",&from[i],&to[i]);
			--from[i];
			--to[i];
			int p1 = next_i[from[i]];
			int p2 = prev_j[to[i]];
			if (p2+1 < p1) { // no complete interval
				assert(p2+2 == p1);
				// element a[p1-1] occurs j-i+1 times
				num[i] = a[p1-1];
				freq[i] = to[i]-from[i]+1;
				from[i] = -1;
				continue;
			}
			freq[i] = ps[p1]-from[i];
			if (freq[i])
				num[i] = a[p1-1];
			if (to[i]-ps[p2+1]+1>freq[i]) {
				freq[i] = to[i]-ps[p2+1]+1;
				num[i] = a[p2+1];
			}
			if (p2 < p1) {
				from[i] = -1;
				continue;
			}
			from[i] = p1;
			to[i] = p2;
			++cnt[p1];
		}
		// counting sort to sort the queries by left end of range
		int sum = 0;
		for (int i=0; i<n; ++i) {
			sum += cnt[i];
			cnt[i] = sum - cnt[i];
		}
		for (int i=0; i<q; ++i) {
			if (from[i] < 0)
				continue;
			ind[cnt[from[i]]++] = i;
		}
		// answer range maximum queries by using scanline plus binary search
		// keep a stack with the indices of the next improvements;
		// the scanline goes from largest index to smallest index;
		// each query with the current index as left end point of the range
		// can then be answered by using a binary search for the largest
		// index <= right end point of the range
		int j = cnt[n-1]-1;
		int sl = 0;
		for (int i=l-1; i>=0; --i) {
			// update list of indices with improvements
			// remove all indices which are no improvement anymore after we add index i
			while(sl && c[s[sl-1]] <= c[i])
				--sl;
			s[sl++] = i;
			while(j >= 0 && from[ind[j]] == i) {
				int le = 0, ri = sl-1,m;
				while(le < ri) {
					m = (le + ri) / 2;
					if (s[m] > to[ind[j]])
						le = m + 1;
					else
						ri = m;
				}
				int maxv = c[s[ri]];
				if (maxv > freq[ind[j]] || maxv == freq[ind[j]] && a[s[ri]] < num[ind[j]]) {
					freq[ind[j]] = maxv;
					num[ind[j]] = a[s[ri]];
				}
				--j;
			}
		}
		for (int i=0; i<q; ++i)
			printf("%d\n",freq[i]);
	}
	return 0;
}