gistfile1.hpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <stdio.h>

using namespace std;

vector<int> idx;
int tree[400000];

void init(int node, int s, int e){
	if(s == e){
		tree[node] = idx[s+1] - idx[s];
		return;
	}
	init(2*node, s, (s+e)/2);
	init(2*node+1, (s+e)/2 + 1, e);
	tree[node] = std::max(tree[2*node], tree[2*node + 1]);
}

int query(int node, int s, int e, int i, int j){
	if(j < s || e < i){
		return -1;
	}
	if(i <= s && e <= j){
		return tree[node];
	}
	int v1 = query(2*node, s, (s+e)/2, i, j);
	int v2 = query(2*node+1, (s+e)/2+1, e, i, j);
	return std::max(v1, v2);
}

int solve(int s, int e){
	int si = upper_bound(idx.begin(), idx.end(), s) - idx.begin() - 1;
	int ei = upper_bound(idx.begin(), idx.end(), e) - idx.begin() - 1;
	if (si == ei) {
		return e - s + 1;
	}
	int max = idx[si + 1] - s;
	max = std::max(max, e - idx[ei] + 1);
	if (si + 1 < ei) {
		max = std::max(max, query(1, 0, idx.size() - 2, si + 1, ei - 1));
	}
	return max;
}

int main(){
	int n;
	scanf("%d", &n);
	while(n){
		idx.clear();
		int q;
		scanf("%d", &q);
		int prev = -1000000;
		for(int i = 0; i < n; ++i){
			int v;
			scanf("%d", &v);
			if(prev != v){
				idx.push_back(i);
				prev = v;
			}
		}
		idx.push_back(n);
		init(1, 0, idx.size() - 2);
		for(int i = 0; i < q; ++i){
			int start, end;
			scanf("%d %d", &start, &end);
			int ans = solve(start-1, end-1); 
			cout << ans << "\n";
		}
		scanf("%d", &n);
	}
	return 0;
}