/* ( . .) */
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
// using namespace __gnu_pbds;
// tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>T;
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
typedef long double ldb;
#define umap unordered_map
#define mkp make_pair
#define prque priority_queue
#define emp emplace
#define empb emplace_back
#define empf emplace_front
mt19937 rd(chrono::high_resolution_clock().now().time_since_epoch().count());
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const double eps = 1e-8;
inline void enter(){putchar('\n');}
inline void space(){putchar(' ');}
inline ll readll(){ll ret=0,k=1;char c;do{c=getchar();}while(('0'>c)|('9'<c));do{ret=(ret<<3)+(ret<<1)+c-48;c=getchar();}while(('0'<=c)&(c<='9')&(c!=EOF));return ret*k;}
inline void read(ll&x){x=readll();}
inline string readstr(){string ret;char c;do{c=getchar();}while((c=='\n')|(c==' '));do{ret+=c;c=getchar();}while((c!='\n')&(c!=' ')&(c!=EOF));return ret;}
inline void read(string&x){x=readstr();}
inline void write(ll x){if(!x){putchar('0');return;}char op[20]={};ll cur=0;while(x){op[++cur]=x%10+48;x/=10;}while(cur){putchar(op[cur--]);}}
// -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

const ll MAXN = 2e5 + 5, B = 450;

struct qry {
	ll l, r, id;
	inline pair<ll, pll> cmpp() {
		return mkp(l / B, mkp(r, id)); 
	}
};
inline bool operator<(qry x, qry y) {
	return x.cmpp() < y.cmpp();
}

ll n, qc, a[MAXN], ans[MAXN], L, R, cura = 0;
__gnu_pbds::cc_hash_table<ll, deque<ll> > pos;
vector<qry> q[1000];

inline void move(ll l, ll r) {
	while (L > l) {
		--L;
		pos[a[L]].empf(L);
		cura = max(cura, pos[a[L]].back() - pos[a[L]].front());
	}
	while (R < r) {
		++R;
		pos[a[R]].empb(R);
		cura = max(cura, pos[a[R]].back() - pos[a[R]].front());
	}
}
inline void chexiao(ll l) {
	while (L < l) {
		pos[a[L]].pop_front();
		++L;
	}
}

int main() {
	read(n);
	for (ll i = 1; i <= n; ++i) {
		read(a[i]);
	}
	read(qc);
	for (ll i = 1; i <= qc; ++i) {
		qry cur;
		cur.id = i;
		read(cur.l), read(cur.r);
		q[cur.l / B].empb(cur);
	}
	for (ll i = 0; i * B <= n; ++i) {
		sort(q[i].begin(), q[i].end());
		for (auto& i : pos) {
			i.second.clear();
		}
		ll btb;
		for (btb = 0; btb < q[i].size(); ++btb) {
			if (q[i][btb].r / B != i) {
				break;
			}
		}
		for (ll j = 0; j < btb; ++j) {
			L = q[i][j].l, R = q[i][j].l - 1, cura = 0;
			move(q[i][j].l, q[i][j].r);
			ans[q[i][j].id] = cura;
			chexiao(q[i][j].r + 1);
		}
		L = (i + 1) * B, R = (i + 1) * B - 1, cura = 0;
		ll prea = 0;
		for (ll j = btb; j < q[i].size(); ++j) {
			// cerr << q[i][j].l << " " << q[i][j].r << endl;
			move((i + 1) * B, q[i][j].r);
			prea = cura;
			move(q[i][j].l, q[i][j].r);
			ans[q[i][j].id] = cura;
			chexiao((i + 1) * B);
			cura = prea;
		}
	}
	for (ll i = 1; i <= qc; ++i) {
		write(ans[i]), enter();
	}
	return 0;
}

1.13s