/* Robin Nittka */
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <map>

#define chld1(x)	(2*(x))
#define chld2(x)	(2*(x)+1)

using namespace std;

typedef pair<int,int>	PII;

int ost[256 * 1024];
int mp[256 * 1024];
int val[256 * 1024];
const int LOWEST = 128 * 1024;

PII qbest(int pos, int rangel, int rangeu, int ql, int qu)
{
//	cout << pos << " " << rangel << " " << rangeu << " " << ql << " " << qu << endl;
	if (ql <= rangel && qu >= rangeu)
		return PII(mp[pos], ost[pos]);
	if (rangel >= qu || rangeu <= ql)
		return PII(-1, -1);
	int mid = (rangel + rangeu) / 2;
	PII l = qbest(chld1(pos), rangel, mid, ql, qu);
	PII u = qbest(chld2(pos), mid, rangeu, ql, qu);
	if (l.second >= u.second)
		return l;
	else
		return u;
}

int main()
{
	int n, q;
	while (cin >> n >> q)
	{
		for (int i = 0; i < n; i++)
			cin >> val[LOWEST+i];
		for (int i = n; i < LOWEST; i++)
		{
			val[LOWEST+i] = LOWEST+i;
			ost[LOWEST+i] = -1;
		}
		for (int i = 0; i < LOWEST; i++)
			mp[LOWEST+i] = val[LOWEST+i];

		int pos = LOWEST;
		while (pos < 2*LOWEST-10)
		{
			int old = pos;
			while (val[pos] == val[old])
				pos++;
			for (int i = old; i < pos; i++)
				ost[i] = pos - old;
		}

//		for (int i = 0; i < n; i++)
//			cout << val[LOWEST+i] << ": " << ost[LOWEST+i] << endl;

		for (int i = LOWEST-1; i > 0; i--)
		{
			if (ost[chld1(i)] >= ost[chld2(i)])
			{
				ost[i] = ost[chld1(i)];
				mp[i] = mp[chld1(i)];
			}
			else
			{
				ost[i] = ost[chld2(i)];
				mp[i] = mp[chld2(i)];
			}
		}

		while (q--)
		{
			int left, right;
			int best = 0;
			int what = -1;
			int rbest = 0;
			int rwhat = -1;
			cin >> left >> right;
			left--;
			right--;
			if (val[LOWEST+left] == val[LOWEST+right])
			{
				cout << (right - left + 1) << endl;
				goto done;
			}
			if (left && val[LOWEST+left] == val[LOWEST+left-1])
			{
				int pos = left;
				while (val[LOWEST+pos] == val[LOWEST+left])
					pos++;

				best = pos - left;
				what = val[LOWEST+left];
				left = pos;
			}
			if (right < n-1 && val[LOWEST+right] == val[LOWEST+right+1])
			{
				int pos = right;
				while (val[LOWEST+pos] == val[LOWEST+right])
					pos--;

				rbest = right - pos;
				rwhat = val[LOWEST+right];
				right = pos;
			}
			right++;

			if (left < right)
			{
				PII qu = qbest(1, 0, LOWEST, left, right);
				if (qu.second > best)
				{
					best = qu.second;
					what = qu.first;
				}
			}

			if (rbest > best)
			{
				best = rbest;
				what = rwhat;
			}

			cout << best << endl;

done:		;
		}
	}
	return 0;
}
