/*program by mangoyang*/
#pragma GCC optimize("Ofast", "inline")
#include<bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
template <class T>
inline void read(T &x){
    int ch = 0, f = 0; x = 0;
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    if(f) x = -x;
}
const int N = 2000005;
#define fi first
#define se second
vector<pair<int, int> > p[N], q[N];
int pre[N], nxt[N], a[N], b[N], ans[N], n, m;
namespace Seg{
    #define lson (u << 1)
    #define rson (u << 1 | 1)
    #define mid ((l + r) >> 1)
    int mx[N<<2], tag[N<<2];
    inline void init(int u, int l, int r){
        mx[u] = tag[u] = 0;
        if(l == r) return;
        init(lson, l, mid), init(rson, mid + 1, r);
    }
    inline void pushdown(int u){
        if(!tag[u]) return;
        mx[lson] = max(mx[lson], tag[u]), tag[lson] = max(tag[lson], tag[u]);
        mx[rson] = max(mx[rson], tag[u]), tag[rson] = max(tag[rson], tag[u]);
        tag[u] = 0;
    }
    inline void change(int u, int l, int r, int L, int R, int x){
        if(l >= L && r <= R)
            return (void) (mx[u] = max(mx[u], x), tag[u] = max(tag[u], x));
        pushdown(u);
        if(L <= mid) change(lson, l, mid, L, R, x);
        if(mid < R) change(rson, mid + 1, r, L, R, x);
        mx[u] = max(mx[lson], mx[rson]);
    }
    inline int query(int u, int l, int r, int L, int R){
        if(l >= L && r <= R) return mx[u];
        pushdown(u); int res = 0;
        if(L <= mid) res = max(res, query(lson, l, mid, L, R));
        if(mid < R) res = max(res, query(rson, mid + 1, r, L, R));
        return res;
    }
}
int main(){
    read(n);
    for(int i = 1; i <= n; i++) read(a[i]);
    for(int i = 1; i <= n; i++)
        pre[i] = b[a[i]], b[a[i]] = i;
    for(int i = 1; i <= n; i++) b[a[i]] = n + 1;
    for(int i = n; i >= 1; i--) 
        nxt[i] = b[a[i]], b[a[i]] = i;
    read(m);
    for(int i = 1, l, r; i <= m; i++){
        read(l), read(r);
        q[r].push_back(make_pair(l, i));
        p[l].push_back(make_pair(r, i));
    }
    for(int i = 1; i <= n; i++){
        if(pre[i]) Seg::change(1, 1, n, pre[i], pre[i], i - pre[i] - 1);
        for(auto now : q[i]) 
            ans[now.se] = max(ans[now.se], Seg::query(1, 1, n, now.fi, i));
    }
    //for(int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    Seg::init(1, 1, n);
    for(int i = 1; i <= n; i++){
        Seg::change(1, 1, n, pre[i] + 1, i, i);
        //cout << "#" << pre[i] + 1 << " " << i << " " << i << endl;
        for(auto now : q[i])
            ans[now.se] = max(ans[now.se], Seg::query(1, 1, n, now.fi, now.fi) - now.fi);
    }
    //for(int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    Seg::init(1, 1, n);
    for(int i = n; i >= 1; i--){
        Seg::change(1, 1, n, i, nxt[i] - 1, n - i);
        for(auto now : p[i]){
            int tmp = Seg::query(1, 1, n, now.fi, now.fi);
            //cout << "*" << now.se << " " << tmp << endl;
            ans[now.se] = max(ans[now.se], now.fi + tmp - n);
        }
    }
    for(int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}