#2 #3 一直过不去，显示WA输出0 下到本地使用 fc 命令对比是无误的。开不开 O2 都过不去

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
#define MAX_N 200010
const int INF = 1e7;
int arr[MAX_N] = { 0 };
int brr[MAX_N] = { 0 };
// 1 最小下标     2 最大坐标
int dis1[MAX_N] = { 0 }, dis2[MAX_N] = { 0 };
int cnt[MAX_N] = { 0 };
int unique(int n) {
	int ret = 0, las = -1;
	for (int x = 1; x <= n; x++) {
		if (las != brr[x])
			brr[++ret] = brr[x];
		las = brr[x];
	}
	return ret;
}
int len;
inline int get_blo(int i) { return (i - 1) / len + 1; }
struct Query {
	int l, r, id;
	bool operator< (const Query& other) const {
		int bl = get_blo(l), br = get_blo(other.l);
		if (bl != br) return bl < br;
		return r < other.r;
	}
} query[MAX_N];
int ans[MAX_N] = { 0 };
int dis3[MAX_N] = { 0 };
bool vis[MAX_N] = { 0 };
int brute(int l, int r) {
	int ret = 0;
	for (int x = l; x <= r; x++) {
		if (vis[arr[x]]) ret = max(ret, x - dis3[arr[x]]);
		else dis3[arr[x]] = x;
		vis[arr[x]] = true;
	}
	for (int x = l; x <= r; x++) vis[arr[x]] = false;
	return ret;
}
int res = 0;
void add(int x, bool right) {
	int v = arr[x];
	if (cnt[v] == 0) dis1[v] = dis2[v] = x;
	else {
		if (right) {
			dis2[v] = x;
			res = max(res, dis2[v] - dis1[v]);
		}
		else res = max(res, dis2[v] - x);
	}
	cnt[v] ++;
}
int main() {
	int n, m;
	scanf("%d", &n);
	for (int x = 1; x <= n; x++) scanf("%d", arr + x), brr[x] = arr[x];
	sort(brr + 1, brr + 1 + n);
	int k = unique(n);
	len = sqrt(n);
	for (int x = 1; x <= n; x++) {
		int l = 1, r = k, mid;
		while (l < r) {
			mid = l + r >> 1;
			if (brr[mid] >= arr[x]) r = mid;
			else l = mid + 1;
		}
		arr[x] = r;
	}
	scanf("%d", &m);
	for (int x = 1; x <= m; x++) {
		int l, r;
		scanf("%d%d", &l, &r);
		query[x] = { l, r, x };
	}
	sort(query + 1, query + 1 + m);
	int b = 1, q = 1;
	while (true) {
		int las = 0;
		res = 0;
		int rg = min(n, b * len);
		int l = rg + 1, r = rg;
		while (b == get_blo(query[q].l)) {
			int L = query[q].l, R = query[q].r, id = query[q].id;
			if (get_blo(L) == get_blo(R)) {
				ans[id] = brute(L, R);
				q++;
				continue;
			}
			while (r < R) add(++r, true);
			las = res;
			l = rg + 1;
			while (l > L) add(--l, false);
			while (l < rg + 1) {
				cnt[arr[l]] --;
				l++;
			}
			ans[id] = res;
			res = las;
			q++;
		}
		if (q > m) break;
		memset(cnt, 0, sizeof cnt);
		b++;
	}
	for (int x = 1; x <= m; x++) printf("%d\n", ans[x]);
	return 0;
}