import java.io.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class elections_vd {
	BufferedReader in;
	StringTokenizer str;
	PrintWriter out;
	String SK;

	String next() throws IOException {
		while ((str == null) || (!str.hasMoreTokens())) {
			SK = in.readLine();
			if (SK == null)
				return null;
			str = new StringTokenizer(SK);
		}
		return str.nextToken();
	}

	int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}

	long nextLong() throws IOException {
		return Long.parseLong(next());
	}

	int[] realnum;
	int[] a;
	HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();

	int[] queryList;
	int[] pos;

	int[] count;

	int[] res;
	int[] num;

	int mid;

	int n, m, t = 0;

	int[][] b;
	int[] take;
	int[] l;
	int[] r;
	int[][] quer;

	int middle = 0;

	void checkans(int mid) {
		Arrays.fill(l, 0);
		Arrays.fill(r, -1);
		int opt = -500;
		int optnum = 0;
		for (int i = 0; i < n; i++) {
			r[a[i]]++;
			if (r[a[i]] - l[a[i]] + 1 > mid) {
				l[a[i]]++;
			}
			if (r[a[i]] - l[a[i]] + 1 == mid && opt < b[a[i]][l[a[i]]]) {
				opt = b[a[i]][l[a[i]]];
				optnum = a[i];
			}
			for (int j = pos[i]; j >= 0; j = queryList[j]) {
				if (quer[0][j] <= opt) {
					res[j] = mid;
					num[j] = realnum[optnum];
				}
			}
		}
	}

	int[] sum;

	void checkcand(int number) {
		for (int i = 1; i <= n; i++) {
			sum[i] = sum[i - 1];
			if (a[i - 1] == number) {
				sum[i]++;
			}
		}
		for (int i = 0; i < m; i++) {
			if (res[i] < sum[quer[1][i] + 1] - sum[quer[0][i]]) {
				res[i] = sum[quer[1][i] + 1] - sum[quer[0][i]];
				num[i] = realnum[number];
			}
		}
	}

	void solve() throws IOException {
		n = nextInt();
		assert n >= 1;
		assert n <= 100000;
		mid = (int) (Math.sqrt(n) + 1);
		a = new int[n];
		sum = new int[n + 1];
		realnum = new int[n];
		count = new int[n];
		for (int i = 0; i < n; i++) {
			int help = nextInt();
			int cur = mp.containsKey(help) ? mp.get(help) : t++;
			a[i] = cur;
			realnum[cur] = help;
			mp.put(help, a[i]);
			count[a[i]]++;
		}
		m = nextInt();
		assert m >= 1;
		assert m <= 100000;
		res = new int[m];
		num = new int[m];
		quer = new int[2][m];
		pos = new int[n];
		queryList = new int[m];
		Arrays.fill(pos, -1);
		Arrays.fill(queryList, -1);
		for (int i = 0; i < m; i++) {
			quer[0][i] = nextInt() - 1;
			quer[1][i] = nextInt() - 1;
			assert quer[0][i] >= 0;
			assert quer[0][i] <= quer[1][i];
			assert quer[1][i] < n;
			queryList[i] = pos[quer[1][i]];
			pos[quer[1][i]] = i;
		}
		middle = mid + 1;

		b = new int[t][];
		for (int i = 0; i < t; i++) {
			b[i] = new int[count[i]];
		}
		take = new int[t];
		for (int i = 0; i < n; i++) {
			if (count[a[i]] <= mid) {
				b[a[i]][take[a[i]]++] = i;
			}
		}

		l = new int[t];
		r = new int[t];
		checkans(3);
		for (int i = 1; i <= mid; i++) {
			checkans(i);
		}

		for (int i = 0; i < t; i++) {
			if (count[i] > mid) {
				checkcand(i);
			}
		}
		for (int i = 0; i < m; i++) {
			out.println(res[i]);
		}

	}

	void run() throws IOException {
		in = new BufferedReader(new FileReader("elections.in"));
		out = new PrintWriter("elections.out");
		solve();
		out.close();
	}

	public static void main(String[] args) throws IOException {
		new elections_vd().run();
	}

}