gistfile1.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {

	static ArrayList<Integer> ci;
	static int[] max;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		StringBuilder output = new StringBuilder();
		while (n > 0) {
			int q = sc.nextInt();
			max = new int[4 * n];
			sc.nextLine();
			String[] as = sc.nextLine().split(" ");
			int prev = Integer.MIN_VALUE;
			ci = new ArrayList<Integer>();
			for (int i = 0; i < n; ++i) {
				int cur = Integer.parseInt(as[i]);
				if (cur != prev) {
					ci.add(i);
					prev = cur;
				}
			}
			ci.add(n);
			init(1, 0, ci.size() - 2);
			for (int i = 0; i < q; ++i) {
				String[] range = sc.nextLine().split(" ");
				int start = Integer.parseInt(range[0]) - 1;
				int end = Integer.parseInt(range[1]) - 1;
				int ans = solve(start, end);
				//				System.out.println(ans);
				output.append(ans + "\n");
			}
			n = sc.nextInt();
		}
		System.out.println(output);
	}

	static int solve(int start, int end) {
		int si = Collections.binarySearch(ci, start);
		int ei = Collections.binarySearch(ci, end);
		if (si < 0) {
			si = -si - 2;
		}
		if (ei < 0) {
			ei = -ei - 2;
		}
		if (si == ei) {
			return end - start + 1;
		}
		int max = ci.get(si + 1) - start;
		max = Math.max(max, end - ci.get(ei) + 1);
		if (si + 1 < ei) {
			max = Math.max(max, query(1, 0, ci.size() - 2, si + 1, ei - 1));
		}
		return max;
	}

	static void init(int node, int s, int e) {
		if (s == e) {
			max[node] = ci.get(s + 1) - ci.get(s);
			return;
		}
		init(2 * node, s, (s + e) / 2);
		init(2 * node + 1, (s + e) / 2 + 1, e);
		max[node] = Math.max(max[2 * node], max[2 * node + 1]);
	}

	static 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 max[node];
		}
		int v1 = query(node * 2, s, (s + e) / 2, i, j);
		int v2 = query(node * 2 + 1, (s + e) / 2 + 1, e, i, j);
		return Math.max(v1, v2);
	}

}