#include <bits/stdc++.h>
typedef long long ll;
#define int long long
int min(int x, int y) { return x < y ? x : y; }
int max(int x, int y) { return x > y ? x : y; }

const int N = 2e5 + 10; 

int n, a[N];
int m;

int Dct[N]; // 表示编号为 i 的数在离散化后的编号
int pos[N]; // 表示编号为 i 的数所处的块
struct block {
	int st, ed;
} block[N];

int b[N];
void dct() {
	for (int i = 1; i <= n; ++ i) b[i] = a[i];
	std::sort(b + 1, b + 1 + n);
	int _m = std::unique(b + 1, b + 1 + n) - b - 1;
	for (int i = 1; i <= n; ++ i)
		Dct[i] = std::lower_bound(b + 1, b + 1 + _m, a[i]) - b;
	
//	for (int i = 1; i <= n; ++ i) std::cout << Dct[i] << " "; std::cout << "\n";
		
	return void();
}
void build() {
	int num = sqrt(n);
	int t = n / num + (n % num > 0);
	for (int i = 1; i <= t; ++ i) {
		block[i].st = (i - 1) * num + 1;
		block[i].ed = i * num;
	}
	block[t].ed = n;
	for (int i = 1; i <= n; ++ i)
		pos[i] = (i - 1) / num + 1;
	
//	for (int i = 1; i <= n; ++ i) std::cout << pos[i] << " "; std::cout << "\n";	
//	for (int i = 1; i <= t; ++ i) std::cout << block[i].st << " " << block[i].ed << "\n"; 
	
	return void();
}

struct node {
	int l, r, id;
	bool operator < (const node &cmp) const {
		if (pos[l] != pos[cmp.l]) return pos[l] < pos[cmp.l];
		return r < cmp.r;
	}
} q[N];

int ans[N];

const int inf = 1e18;
int pos_l[N], pos_r[N]; // 用莫队处理的计数数组
int pos_l_[N], pos_r_[N]; // 用暴力处理的计数数组 或者 用来处理左端点回滚的数组

void del(int p) {
	pos_l[Dct[p]] = pos_r[Dct[p]] = 0;
	return void();
}
void add_r(int p) { // 对于右端点的增加操作
	if (! pos_l[Dct[p]]) pos_l[Dct[p]] = p;
	pos_r[Dct[p]] = p;
	return void();
}
void add_l(int p) {
	pos_l_[Dct[p]] = p;
	if (! pos_r_[Dct[p]]) pos_r_[Dct[p]] = p;
	return void();
}
void del_l(int p) {
	pos_l_[Dct[p]] = pos_r_[Dct[p]] = 0;
	return void();
}

void getmax_l(int &ans, int p) {
	ans = max(ans, max(pos_r[Dct[p]], pos_r_[Dct[p]]) - pos_l_[Dct[p]]);
	return void();
}
void getmax_r(int &ans, int p) {
	ans = max(ans, pos_r[Dct[p]] - pos_l[Dct[p]]);
	return void();
}

void work() {
	int l = 1, r = 0, lstblock = 0;
	int max_r = 0; 
	
	for (int i = 1; i <= n; ++ i) pos_l[Dct[i]] = pos_l_[Dct[i]] = 0;
	for (int i = 1; i <= n; ++ i) pos_r[Dct[i]] = pos_r_[Dct[i]] = 0;
	
	for (int i = 1; i <= m; ++ i) {
		if (pos[q[i].l] == pos[q[i].r]) {
			
			for (int j = q[i].l; j <= q[i].r; ++ j) {
				if (! pos_l_[Dct[j]]) pos_l_[Dct[j]] = j;  // 之前没有出现过，即为最小的位置
				pos_r_[Dct[j]] = j; // 最后一次出现的位置
				ans[q[i].id] = max(ans[q[i].id], pos_r_[Dct[j]] - pos_l_[Dct[j]]);
			}
			for (int j = q[i].l; j <= q[i].r; ++ j) pos_l_[Dct[j]] = pos_r_[Dct[j]] = 0;
			continue ;
		}
		if (pos[q[i].l] != lstblock) {
			while (r > block[pos[q[i].l]].ed) del(r --);
			l = r + 1; lstblock = pos[q[i].l];
			max_r = 0; 
		}
		int max_l = 0; 
		while (r < q[i].r) add_r(++ r), getmax_r(max_r, r);
		while (l > q[i].l) add_l(-- l), getmax_l(max_l, l);
		ans[q[i].id] = max(max_l, max_r);
		while (l < block[pos[q[i].l]].ed + 1) del_l(l ++);
	}
	return void();
}

signed main() {

//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);

	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	std::cin >> n;
	for (int i = 1; i <= n; ++ i) std::cin >> a[i];
	dct(); build();
	std::cin >> m;
	for (int i = 1; i <= m; ++ i) std::cin >> q[i].l >> q[i].r, q[i].id = i;
	std::sort(q + 1, q + 1 + m);
	
	work();
	
	for (int i = 1; i <= m; ++ i) std::cout << ans[i] << "\n";

	return 0;
}