#include <bits/stdc++.h>

typedef long long ll;

#define sc second
#define fs first
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

struct z{
    ll l, r, p;
    z(ll nl, ll nr, ll np){
        p = np;
        l = nl;
        r = nr;
    }
};

bool comp(z a, z b){
    return a.r < b.r;
}

int main()
{
    ifstream cin("input.txt");
    ofstream cout("output.txt");
    ll n, m;
    cin >> n;
    vector<pair<ll, ll> >mas(n);
    vector<ll>b(n), ma1(n, 0), ma2(n, 0);

    for(int i = 0; i < n; i++){
        cin >> mas[i].fs;
        mas[i].sc = i;
    }

    sort(all(mas));

    int k = 0;
    b[mas[0].sc] = 0;
    for(int i = 1; i < n; i++){
        if(mas[i].fs != mas[i-1].fs)
            k++;
        b[mas[i].sc] = k;
    }

    ll p = sqrt(n+2);
    p++;
    cin >> m;
    vector<vector<z> > a(p);
    vector<ll>ans(m);

    for(int i = 0; i < m; i++){
        ll l, r;
        cin >> l >> r;
        l--; r--;
        if(r-l+1 <= p){
            ll an = 0;
            for(int j = l; j <= r; j++){
                ma1[b[j]]++;
                an = max(ma1[b[j]], an);
            }
            ans[i] = an;
            for(int j = l; j <= r; j++){
                --ma1[b[j]];
            }
        }
        else{
            a[l/p].pb(z(l, r, i));
        }
    }

    for(int i = 0; i < p; i++){
        sort(all(a[i]), comp);
        ll pp = p * (i+1);
        if(a[i].size() == 0)
            continue;
        ll max1 = 0, max2 = 0;
        ll z = pp - 1;

        for(int o = 0; o < a[i].size(); o++){
            for(int j = z + 1; j <= a[i][o].r; j++){
                max1 = max(++ma1[b[j]], max1);
                ma2[b[j]]++;
            }
            max2 = max1;
            z = a[i][o].r;
            for(int j = a[i][o].l; j < pp; j++){
                max2 = max(++ma2[b[j]], max2);
            }
            for(int j = a[i][o].l; j < pp; j++){
                --ma2[b[j]];
            }
            ans[a[i][o].p] = max2;
            max2 = max1;
        }

        for(int j = pp; j <= a[i][a[i].size()-1].r; j++){
            ma1[b[j]] = 0;
            ma2[b[j]] = 0;
        }

    }

    for(int i = 0; i < m; i++)
        cout << ans[i] << "\n";
}