WA #3

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;

int BlockId[N];

struct Query {
	int l, r, id;
	
	inline bool operator < (const Query &b) const  {
		return BlockId[l] == BlockId[b.l] ? r < b.r : l < b.l;
	}
}q[N];

pair<int, int> tag[N], BFtag[N];

int L[N], R[N], ans[N];
int a[N], tmp[N];

int n, m, tot;
int block, BlockSum, res;

inline int read() {
    char c = getchar();

    while (isspace(c) && c)
        c = getchar();

    int x = 0;
    
    while (isdigit(c))
        x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    
    return x;
}

inline void Reset(pair<int, int> *f) {
	for (int i = 1; i <= tot; ++i)
		f[i] = make_pair(n + 1, 0);
}

inline int BruteForce(int l, int r) {
	Reset(BFtag);
	int BFres = 0;
	
	for (int i = l; i <= r; ++i) {
		BFtag[a[i]].first = min(BFtag[a[i]].first, i);
		BFtag[a[i]].second = max(BFtag[a[i]].second, i);
		BFres = max(BFres, BFtag[a[i]].second - BFtag[a[i]].first);
	}
	
	return BFres;
}

inline void AddL(int x) {
	res = max(res, tag[a[x]].second - x);
}

inline void AddR(int x) {
	tag[a[x]].first = min(tag[a[x]].first, x);
	tag[a[x]].second = max(tag[a[x]].second, x);
	res = max(res, tag[a[x]].second - tag[a[x]].first);
}

signed main() {
	scanf("%d", &n);
	block = pow(n, 0.666), BlockSum = n / block;
	
	for (int i = 1; i <= n; ++i) {
		scanf("%d", a + i);
		tmp[i] = a[i];
		BlockId[i] = (i - 1) / block + 1;
	}
		
	sort(tmp + 1, tmp + 1 + n);
	tot = unique(tmp + 1, tmp + 1 + n) - tmp - 1;
	
	for (int i = 1; i <= n; ++i)
		a[i] = lower_bound(tmp + 1, tmp + 1 + tot, a[i]) - tmp;
	
	for (int i = 1; i <= BlockSum; ++i)
		L[i] = R[i - 1] + 1, R[i] = L[i] + block - 1;
	
	if (R[BlockSum] < n)
		L[BlockSum + 1] = R[BlockSum] + 1, R[++BlockSum] = n;
	
	scanf("%d", &m);
	
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d", &q[i].l, &q[i].r);
		q[i].id = i;
	}
	
	sort(q + 1, q + 1 + m);
	
	for (int i = 1, pos = 1; i <= BlockSum; ++i) {
		Reset(tag);
		res = 0;
		
		for (int r = R[i], l = R[i] + 1; BlockId[q[pos].l] == i; ++pos) {
			if (q[pos].r - q[pos].l <= block) {
				ans[q[pos].id] = BruteForce(q[pos].l, q[pos].r);
				continue;
			}
			
			while (r < q[pos].r)
				AddR(++r);
			
			int BeforeResult = res;
			
			while (l > q[pos].l)
				AddL(--l);
			
			ans[q[pos].id] = res;
			res = BeforeResult;
			l = R[i] + 1;
		}
	}
	
	for (int i = 1; i <= m; ++i)
		printf("%d\n", ans[i]);
	
	return 0;
}