#include <iostream>		//离散化+线段树
#define MAX(a, b)  ((a) > (b) ? (a) : (b))
#define MAXN 100010
#define INF 9999999
using namespace std;
struct tree
{
	int begin, end, count;
	tree *left, *right;
};
tree Tree[MAXN * 2];
int pos[MAXN];
int num[MAXN];
int p1, p2;

tree* CreateTree (int a, int b)
{
	tree *node = &Tree[p1++];
	node->begin = a;
	node->end = b;
	if (a == b)
	{
		node->count = num[a];
	}
	else
	{
		int mid = (a + b) / 2;
		node->left = CreateTree (a, mid);
		node->right = CreateTree (mid + 1, b);
		node->count = MAX(node->left->count, node->right->count);
	}
	return node;
}

int Query (int a, int b, tree *tr)
{
	if (a == tr->begin && b == tr->end)
	{
		return tr->count;
	}
	int mid = (tr->begin + tr->end) / 2;
	if (b <= mid)
	{
		return Query (a, b, tr->left);
	}
	else if (a > mid)
	{
		return Query (a, b, tr->right);
	}
	else
	{
		int tmp1 = Query (a, mid, tr->left);
		int tmp2 = Query (mid + 1, b, tr->right);
		return MAX(tmp1, tmp2);
	}
}

int Calc (int x)
{
	int a = 1, b = p2, mid;
	if (a == b)
	{
		return a;
	}
	else if (b - a == 1)
	{
		return (x < pos[b] ? a : b);
	}
	else
	{
		while (1)
		{
			mid = (a + b) / 2;
			if (x >= pos[mid] && x < pos[mid + 1])
			{
				return mid;
			}
			else if (x < pos[mid])
			{
				b = mid - 1;
				continue;
			}
			else
			{
				a = mid + 1;
				continue;
			}
		}
	}
}

int main()
{
	int n, q, i, x, y;
	int a, b, res;
	int tmp = INF;
	tree *root;
	while (scanf("%d", &n) != EOF && n != 0)
	{
		scanf ("%d", &q);
		p2 = 1;
		for (i = 1; i <= n; i++)		//离散化
		{
			scanf ("%d", &x);
			if (x != tmp)
			{
				pos[p2] = i;
				if (p2 > 1)
				{
					num[p2 - 1] = pos[p2] - pos[p2 - 1];
				}
				p2++;
				tmp = x;
			}
		}
		pos[p2--] = n + 1;
		num[p2] = pos[p2 + 1] - pos[p2];
		p1 = 0;
		root = CreateTree (1, p2);
		while (q--)
		{
			scanf ("%d%d", &x, &y);
			a = Calc(x);
			b = Calc(y);
			if (a == b)
			{
				res = y - x + 1;
			}
			else
			{
				res = MAX (pos[a + 1] - x, y - pos[b] + 1);
				if (b - a == 2)
				{
					res = MAX (res, num[a + 1]);
				}
				else if (b - a > 2)
				{
					tmp = Query (a + 1, b - 1, root);
					res = MAX (res, tmp);
				}
			}
			printf("%d\n", res);
		}
	}
	return 0;
}