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

using namespace std;

const int NUMBER_OPERATION = 4e8;
const int SIZE = 4;
const int COUNT = 3;

int main()
{
	freopen("elections.in", "r", stdin);
	freopen("elections.out", "w", stdout);
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b.begin(), b.end());
	vector< pair<int, int> > ch;
	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(NUMBER_OPERATION / 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;
    int l, r;
	for (int i = 0; i < m; i++)
	{
		cin >> l >> r;
		//int ans = 0;
		int kol = 0;
        int cou = 0;
        int tek = l - 2;
        set<int> num;
        while (cou <= COUNT)
        {
            tek++;
            if (num.count(a[tek]) > 0)
                continue;
            else
            {
                num.insert(a[tek]);
                cou++;
            }
            int tmp = 0;
            for (int j = l - 1; j < r; j++)
                if (a[j] == a[tek]) tmp++;
            if (kol < tmp) kol = tmp;
        }  
		if (r - l <= t / SIZE)
		{
			map<int, int> bi;
			vector<int> tek;
			for (int j = l - 1; j < r; j++)
			{
				if (bi.count(a[j]) > 0)
				{
                    int t = bi[a[j]];
					tek[t]++;
					if (tek[t] > kol)
					{
		//				ans = a[j];
						kol = tek[t];
					}
				}
				else
				{
					bi.insert(make_pair(a[j], tek.size()));
					tek.push_back(1);
					if (1 > kol)
					{
		//				ans = a[j];
						kol = 1;
					}

				}
			}
		}
		else
			for (int j = 0; j < t; j++)
				if (kol < ololo[j][r] - ololo[j][l - 1])
				{
					kol = ololo[j][r] - ololo[j][l - 1];
		//			ans = ch[j].second;
				}
		cout << /*ans << " " << */kol << endl;
	}

}

