#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>

#define x first
#define y second

#define int long long

using namespace std;

const int N = 100010;

int n, m, len;
int w[N], cnt[N];
int ans[N];
map<int, int> hash1;
map<int, int> hash3;
map<int, int> hash4;
struct Query
{
    int id, l, r;
}q[N];
vector<int> nums;

int get(int x)
{
    return x / len;
}

bool cmp(const Query& a, const Query& b)
{
    int i = get(a.l), j = get(b.l);
    if (i != j) return i < j;
    return a.r < b.r;
}

signed main()
{
    scanf("%lld", &n);
    len = sqrt(n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]), nums.push_back(w[i]);
    scanf("%lld", &m);
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    for (int i = 1; i <= n; i ++ )
        w[i] = lower_bound(nums.begin(), nums.end(), w[i]) - nums.begin();
    for (int i = 1; i <= m; i ++ )
    {
        int l, r;
        scanf("%lld%lld", &l, &r);
        q[i] = {i, l, r};
    }
    sort(q + 1, q + m + 1, cmp);

    for (int x = 1; x <= m;)
    {
        int y = x;
        while (y <= m && get(q[y].l) == get(q[x].l)) y ++ ;
        int right = ((q[x].l - 1) / len + 1) * len;
        // 暴力求块内的询问
        while (x < y && q[x].r <= right)
        {
            int res = 0;
            hash1.clear();
            int id = q[x].id, l = q[x].l, r = q[x].r;
            for(int k = l; k <= r; k ++ )
            {
                if(hash1.count(w[k]) == false) hash1[w[k]] = k;
                res = max(res, abs(hash1[w[k]] - k));
            }
            ans[id] = res;
            x ++ ;
        }
        // 求块外的询问
        int res = 0;
        hash1.clear();
        hash3.clear();
        int i = right - 1, j = right;
        while (x < y)
        {
            int id = q[x].id, l = q[x].l, r = q[x].r;
            while (i < r) 
            {
                i ++ ;
                hash3[w[i]] = i;
                if(hash1.count(w[i]) == false) hash1[w[i]] = i;
                res = max(res, abs(i - hash1[w[i]]));
            }
            int backup = res;
            map<int, int> hash2 = hash1;
            int j = right;
            while (j > l)
            {
                j -- ;
                if(hash4.count(w[j]) == false) hash4[w[j]] = j;
                res = max(res, abs(j - hash4[w[j]]));
                res = max(res, abs(j - hash3[w[j]]));
            }
            ans[id] = res;
            res = backup;
            hash1 = hash2;
            hash4.clear();
            x ++ ;
        }
        memset(cnt, 0, sizeof cnt);
        hash1.clear();
    }

    for (int i = 1; i <= m; i ++ ) printf("%lld\n", ans[i]);
    return 0;
}

附上记录详情