过了 #1 #2 #3 #17，完全不知道是哪里错了，也不会构造数据 /ll

#include <bits/stdc++.h>
#define debug() cerr<<__LINE__<<endl
using namespace std;

inline int read() {
	int tmp = 0, f = 1;
	char c = getchar();
	while(!isdigit(c)) {
		if(c == '-') f = -f;
		c = getchar(); 
	}
	while(isdigit(c)) tmp = (tmp << 1) + (tmp << 3) + (c ^ 48), c = getchar();
	return tmp * f;
}

void write(int x) {
	if(x < 0) x = -x, putchar('-');
	if(x > 9) write(x / 10);
	putchar((x % 10) ^ 48);
}

int n, a[200010], id[200010], m, N, minpos[200010], recmin[200010], maxpos[200010], blk[200010], block_size;
int tmp[200010], b[200010], recmax[200010];

struct query {
	int l, r, ans, id;
} q[200010];

inline bool cmp0(int x, int y) {
	return a[x] < a[y];
}

inline bool cmp1(query a, query b) {
	return blk[a.l] != blk[b.l] ? blk[a.l] < blk[b.l] : a.r < b.r;
}

inline bool cmp2(query a, query b) {
	return a.id < b.id;
}

inline void add(int id, int x) {
	minpos[b[x]] = min(minpos[b[x]], x);
	maxpos[b[x]] = max(maxpos[b[x]], x);
	q[id].ans = max(q[id].ans, maxpos[b[x]] - minpos[b[x]]);
}

inline void del(int x) {
	minpos[b[x]] = recmin[b[x]];
	maxpos[b[x]] = recmax[b[x]];
}

int main() {
	n = read();
	for(int i = 1; i <= n; i++) a[i] = read(), id[i] = i;
	sort(id + 1, id + n + 1, cmp0);
	// debug();
	int N = 0;
	a[0] = -1;
	for(int i = 1; i <= n; i++) {
		if(a[id[i]] != a[id[i - 1]]) N++;
		b[id[i]] = N;
	}
	// debug();
	memset(minpos, 0x7f, sizeof(minpos));
	memset(recmin, 0x7f, sizeof(recmin));
	m = read();
	block_size = n / sqrt(m) + 1;
	for(int i = 1; i <= n; i++) {
		blk[i] = (i - 1) / block_size + 1;
	}
	for(int i = 1; i <= m; i++) {
		q[i].id = i;
		q[i].l = read(), q[i].r = read();
	}
	// debug();
	sort(q + 1, q + m + 1, cmp1);
	int l = 0, r = -1;
	for(int i = 1; i <= m; i++) {
		// debug();
		if(blk[q[i].l] == blk[q[i].r]) {
			for(int j = q[i].l; j <= q[i].r; j++) {
				recmax[b[j]] = max(recmax[b[j]], j);
				recmin[b[j]] = min(recmin[b[j]], j);
				q[i].ans = max(q[i].ans, recmax[b[j]] - recmin[b[j]]);
			}
			for(int j = q[i].l; j <= q[i].r; j++) {
				recmin[b[j]] = 0x7f7f7f7f;
				recmax[b[j]] = 0;
			}
		} else {
			if(blk[l] != blk[q[i].l]) {
				for(int j = 1; j <= N; j++) {
					recmax[b[j]] = maxpos[b[j]] = 0;
					recmin[b[j]] = minpos[b[j]] = 0x7f7f7f7f;
				}
				l = min(blk[q[i].l] * block_size, n);
				r = l - 1;
			}
			while(r < q[i].r) add(i, ++r);
			for(int j = q[i].l; j <= l; j++) recmax[b[j]] = maxpos[b[j]], recmin[b[j]] = minpos[b[j]];
			while(l > q[i].l) add(i, --l);
			while(l < min(blk[q[i].l] * block_size, n)) del(l++);
		}
	}
	// debug();
	sort(q + 1, q + m + 1, cmp2);
	for(int i = 1; i <= m; i++) {
		write(q[i].ans), puts("");
	}
	return 0;
}