// Author: Adrian Kuegel
// Date: 20. 10. 2006
// Complexity: O(n + q) where q is number of queries

#include <stdio.h>
#include <assert.h>
#include <algorithm>
#include <vector>
using namespace std;

typedef vector<int> VI;

#define MAXN 100000

int a[MAXN],ps[MAXN+1];
int next_i[MAXN],prev_j[MAXN];

// #define ASSERT

class prefixtree {
public:
	static int **get_table_pointer(int *v, int n, bool &isnew) {
		if (ROOT == NULL)
			ROOT = new prefixtree();
		prefixtree *cur = ROOT;
		for (int i=0; i<n; i++)
			if (v[i] == 1) {
				if (cur->right == NULL)
					cur->right = new prefixtree();
				cur = cur->right;
			}
			else if (v[i] == -1) {
				if (cur->left == NULL)
					cur->left = new prefixtree();
				cur = cur->left;
			}
			else {
				if (cur->mid == NULL)
					cur->mid = new prefixtree();
				cur = cur->mid;
			}
		if (cur->tpointer == NULL) {
			isnew = true;
			cur->d = n;
			cur->tpointer = new int*[n];
			for (int i=0; i<n; i++)
				cur->tpointer[i] = new int[n];
		}
		else
			isnew = false;
		return cur->tpointer;
	}
	static void clear() {
		delete ROOT;
		ROOT = NULL;
	}
private:
	int **tpointer;
	char d;
	prefixtree *left,*right,*mid;
	static prefixtree *ROOT;
	prefixtree() {
		d = 0;
		tpointer = NULL;
		left = right = mid = NULL;
	}
	~prefixtree() {
		delete left;
		delete right;
		delete mid;
		for (int i=0; i<d; i++) {
			delete [] tpointer[i];
			tpointer[i] = NULL;
		}
		delete [] tpointer;
		tpointer = NULL;
	}
};

prefixtree *prefixtree::ROOT = NULL;

class rmq_restricted {
public:
	rmq_restricted(int *L, int n2) {

#ifdef ASSERT
		assert(n2>1);
#endif

		A = L;
		n = n2;
		prefixtree::clear();
		k = 2*n/(1+get_highest_bit(n));

#ifdef ASSERT
		assert(k<=n);
#endif

		gsize = n/k;
		k += (n-k*gsize+gsize-1)/gsize;

#ifdef ASSERT
		assert(k*gsize>=n);
		assert((k-1)*gsize<n);
#endif

		A2 = new int[k];
		B = new int[k];
		table = new int **[k];

#ifdef ASSERT
		assert(gsize>0);
#endif

		int *v = new int[gsize];
		k = 0;
		for (int i=0; i<n; k++) {
			int j;
			for (j=0; j<gsize && i<n; i++,j++) {
				if (j) {
					v[j] = A[i]-A[i-1];
					if (A[i]<A2[k]) {
						B[k] = i;
						A2[k] = A[i];
					}
				}
				else {
					v[j] = 0;
					B[k] = i;
					A2[k] = A[i];
				}
			}
			bool isnew;
			table[k] = prefixtree::get_table_pointer(v,j,isnew);
			if (isnew) {
				for (int i=2; i<j; i++)
					v[i] += v[i-1];
				for (int from=0; from<j; from++) {
					int best_ind = from;
					for (int to=from; to<j; to++) {
						if (v[best_ind]>v[to])
							best_ind = to;
						(*(*(table+k)+from))[to] = best_ind;
					}
				}
			}
		}
		delete [] v;
		log_k = get_highest_bit(k)+1;
		M = new int*[k];
		for (int i=0; i<k; i++)
			M[i] = new int[log_k];
		for (int j=0; j<log_k; j++) {
			for (int i=0; i<k; i++) {
				if (!j)
					(*(M+i))[j] = i;
				else if (i+(1<<(j-1))>=k || A2[(*(M+i))[j-1]]<A2[(*(M+i+(1<<(j-1))))[j-1]]) {
					(*(M+i))[j] = (*(M+i))[j-1];
				}
				else {
					(*(M+i))[j] = (*(M+i+(1<<(j-1))))[j-1];
				}
			}
		}
	}
	~rmq_restricted() {
		delete [] A2;
		delete [] B;
		for (int i=0; i<k; i++) {
			delete [] M[i];
			M[i] = NULL;
		}
		delete [] table;
		delete [] M;
		prefixtree::clear();
	}
	int RMQ(int from, int to) {
		if (from>to)
			swap(from,to);
		int b1 = from/gsize;
		int b2 = to/gsize;
		int best;
		if (b1 == b2) {
			best = (*(*(table+b1)+(from%gsize)))[to%gsize];
			return best+b1*gsize;
		}
		best = (*(*(table+b1)+(from%gsize)))[gsize-1]+b1*gsize;
		int t = (*(*(table+b2)))[to%gsize]+b2*gsize;
		if (A[t]<A[best])
			best = t;
		if (b2-b1>1) {
			t = ST_RMQ(b1+1,b2-1);
#ifdef ASSERT
			assert(A[B[t]] == A2[t]);
#endif

			t = B[t];
			if (A[t]<A[best])
				best = t;
		}
		return best;
	}
private:
	int **M;
	int *A,*A2,*B,***table;
	int n,k,log_k,gsize;
	int ST_RMQ(int from, int to) {
		int k = get_highest_bit(to-from);
		if (A2[(*(M+from))[k]]<A2[(*(M+to-(1<<k)+1))[k]])
			return (*(M+from))[k];
		return (*(M+to-(1<<k)+1))[k];
	}
	int get_highest_bit(int n) {
		for (int i=30; i>0; i--)
			if (n&(1<<i))
				return i;
		return 0;
	}
};

typedef vector<int> VI;

class lca {
public:
	int *labels,*L,*E,*R,*par;
	VI *childs;
	int n;
	bool precalc;
	lca(int n2) {
		n = n2;
		labels = new int[n];
		L = new int[2*n-1];
		E = new int[2*n-1];
		R = new int[n];
		par = new int[n];
		for (int i=0; i<n; i++)
			par[i] = -1;
		childs = new VI[n];
		precalc = false;
		rmq = NULL;
	}
	~lca() {
		delete [] labels;
		delete [] L;
		delete [] E;
		delete [] R;
		delete [] childs;
		delete [] par;
		delete rmq;
	}
	int get_lca(int node1, int node2) {
		if (!precalc) {
			precalc = true;
			do_precalc();
		}
		return E[rmq->RMQ(R[node1],R[node2])];
	}
private:
	rmq_restricted *rmq;
	void do_precalc() {
		int root = -1;
		for (int i=0; i<n; i++)
			if (par[i]<0) {

#ifdef ASSERT
				assert(root<0);
#endif

				root = i;
			}

#ifdef ASSERT
		assert(root>=0);
#endif

		int *S = new int[n];
		S[0] = root;
		int l = 0,d = 0;
		while(d>=0) {

#ifdef ASSERT
			assert(l<2*n-1);
#endif

			int act = S[d];
			E[l] = act;
			R[act] = l;
			L[l++] = d;
			if (childs[act].empty()) {
				d--;
				continue;
			}
			++d;
			while(d >= n);
			S[d] = childs[act].back();
			childs[act].pop_back();
		}
		delete [] S;

#ifdef ASSERT
		assert(l == 2*n-1);
#endif
		rmq = new rmq_restricted(L,2*n-1);
	}
};

class rmq {
private:
	int n;
	lca *C;
public:
	rmq(int *A, int n2);
	int RMQ(int from, int to);
	~rmq();
};

rmq::rmq(int *A, int n2) {
	n = n2;
	C = new lca(n);
	// build the cartesian tree
	int cur = 0;
	for (int i=1; i<n; i++) {
		while(C->par[cur]>=0) {
			if (A[cur]<=A[i])
				break;
			cur = C->par[cur];
		}
		if (A[cur]<=A[i]) {
			C->par[i] = cur;
			int right = -1;
			if (!C->childs[cur].empty())
				right = C->childs[cur].back();
			if (right<cur)
				C->childs[cur].push_back(i);
			else {
				C->childs[i].push_back(right);
				C->par[right] = i;
				C->childs[cur].back() = i;
			}
		}
		else {
			C->par[cur] = i;
			C->childs[i].push_back(cur);
		}
		cur = i;
	}
}

int rmq::RMQ(int from, int to) {

#ifdef ASSERT
	assert(from>=0 && from<n);
	assert(to>=0 && to<n);
#endif

	return C->get_lca(from, to);
}

rmq::~rmq() {
	delete C;
}

int f[MAXN];

int main() {
	int n,q;
	while(scanf("%d %d",&n,&q) == 2 && n) {
		int l = 0;
		for (int i=0; i<n; i++) {
			int t;
			scanf("%d",&t);
			if (!l || a[l-1] != t) {
				a[l] = t;
				l++;
				ps[l] = ps[l-1];
			}
			++ps[l];
		}
		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 in ps with ps[j+1] <= i+1
			if (ps[j] == i+1)
				--j;
		}
		int i,j;
		for (int i=0; i<l; i++) {
			assert(ps[i] < ps[i+1]);
			f[i] = -(ps[i+1]-ps[i]);
		}
		assert(ps[l] == n);
		rmq Q(f,l);
		while(q--) {
			scanf("%d %d",&i,&j);
			--i;
			--j;
			assert(i >= 0 && i <= j && j < n);
			// element k in OST represents indizes ps[k] .. ps[k+1]-1
			int p1 = next_i[i];
			assert(p1 >= 0 && ps[p1] >= i && (!p1 || ps[p1-1] < i));
			int p2 = prev_j[j];
			assert(p2 >= -1 && ps[p2+1] <= j+1 && (p2+1 == l || ps[p2+2] > j+1));
			if (p2+1 < p1) { // no complete interval
				assert(p2+2 == p1);
				// element a[p1-1] occurs j-i+1 times
				printf("%d\n",j-i+1);
				continue;
			}
			int best = ps[p1]-i,sol;
			if (best) sol = a[p1-1];
			if (j-ps[p2+1]+1>best) {
				best = j-ps[p2+1]+1;
				sol = a[p2+1];
			}
			if (p2 < p1) {
				printf("%d\n",best);
				continue;
			}
			int res = Q.RMQ(p1,p2); // query takes O(1) time
			if (-f[res] > best || -f[res] == best && a[res] < sol) {
				sol = a[res];
				best = -f[res];
			}
			printf("%d\n",best);
		}
	}
	return 0;
}
