#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int SIZE = 7e7;

int main()
{
	freopen("elections.in", "r", stdin);
	freopen("elections.out", "w", stdout);
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	int fr = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b.begin(), b.end());
	vector< pair<int, int> > ch;
	int l = 0, r = 0;
	ch.push_back(make_pair(upper_bound(b.begin(), b.end(), b[0]) - lower_bound(b.begin(), b.end(), b[0]), b[0]));

	for (int i = 1; i < n; i++)
		if (b[i] != b[i - 1])
			ch.push_back(make_pair(upper_bound(b.begin(), b.end(), b[i]) - lower_bound(b.begin(), b.end(), b[i]), b[i]));
	sort(ch.begin(), ch.end());
	reverse(ch.begin(), ch.end());
	int t = min(SIZE / n, (int)ch.size());
	vector< vector<int> > ololo(t);
	for (int i = 0; i < t; i++)
		ololo[i].resize(n + 1);
	for (int i = 1; i < n + 1; i++)
	{
		for (int j = 0; j < t; j++)
			if (ch[j].second == a[i-1]) ololo[j][i] = ololo[j][i - 1] + 1;
			else ololo[j][i] = ololo[j][i - 1];
	}
	int m;
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		int ans = 0;
		int kol = 0;
		for (int j = 0; j < t; j++)
			if (kol < ololo[j][b] - ololo[j][a-1])
			{
				kol = ololo[j][b] - ololo[j][a-1];
				ans = ch[j].second;
			}
		cout << /*ans << " " <<*/ kol << endl;
	}

}

