#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define ui unsigned int
#define i128 __int128
#define mems(x, y) memset((x), (y), sizeof (x))
#define lid (id << 1)
#define rid (id << 1 | 1)
#define pc(x) __builtin_popcount(x)
#define pcll(x) __builtin_popcountll(x)
#define De(x) cout << #x << ": " << x << '\n'
#define DE(x) cout << #x << ": " << x << ' '
const int N = 2e5+5;
const int intmin = -0x3f3f3f3f, intmax = 0x3f3f3f3f;
const ll llmin = -0x3f3f3f3f3f3f3f3f, llmax = 0x3f3f3f3f3f3f3f3f;
#ifdef ONLINE_JUDGE
#define cin IO::InputHelper::get_instance()
#define cout IO::OutputHelper::get_instance()
#define INPUT_FILE ""
#define OUTPUT_FILE ""
namespace IO {
	using size_type = size_t;
	static constexpr size_type INPUT_BUFFER_SIZE = 1 << 16, OUTPUT_BUFFER_SIZE = 1 << 16, MAX_INTEGER_SIZE = 20, MAX_FLOAT_SIZE = 50;static constexpr char input_file[] = INPUT_FILE, output_file[] = OUTPUT_FILE;
	struct InputHelper {
		FILE *m_file_ptr;char m_buf[INPUT_BUFFER_SIZE], *m_end, *m_cursor;bool m_ok;
		InputHelper &set_bad() { return m_ok = false, *this; }
		template <size_type BlockSize>
		void _reserve() {size_type a = m_end - m_cursor;if (a >= BlockSize) return;memmove(m_buf, m_cursor, a), m_cursor = m_buf;size_type b = a + fread(m_buf + a, 1, INPUT_BUFFER_SIZE - a, m_file_ptr);if (b < INPUT_BUFFER_SIZE) m_end = m_buf + b, *m_end = EOF;}
		template <typename Tp, typename BinaryOperation>
		InputHelper &fill_integer(Tp &ret, BinaryOperation op) {if (!isdigit(*m_cursor)) return set_bad();ret = op(Tp(0), *m_cursor - '0');size_type len = 1;while (isdigit(*(m_cursor + len))) ret = op(ret * 10, *(m_cursor + len++) - '0');m_cursor += len;return *this;}
		explicit InputHelper(const char *inputFileName) : m_ok(true), m_cursor(m_buf + INPUT_BUFFER_SIZE), m_end(m_buf + INPUT_BUFFER_SIZE) { m_file_ptr = *inputFileName ? fopen(inputFileName, "rt") : stdin; }
		~InputHelper() { fclose(m_file_ptr); }
		static InputHelper &get_instance() {static InputHelper s_obj(input_file);return s_obj;}
		static bool is_blank(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\r'; }static bool is_endline(char c) { return c == '\n' || c == EOF; }
		const char &getchar_checked() {_reserve<1>();return *m_cursor;}const char &getchar_unchecked() const { return *m_cursor; }
		void next() { ++m_cursor; }
		template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
		InputHelper &operator>>(Tp &num) {while (is_blank(getchar_checked())) next();_reserve<MAX_INTEGER_SIZE>();if (getchar_unchecked() != '-') return fill_integer(num, std::plus<Tp>());next();return fill_integer(num, std::minus<Tp>());}
		template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
		InputHelper &operator>>(Tp &num) {while (is_blank(getchar_checked())) next();_reserve<MAX_INTEGER_SIZE>();return fill_integer(num, std::plus<Tp>());}
		template <typename Tp, typename std::enable_if<std::is_floating_point<Tp>::value>::type * = nullptr>
		InputHelper &operator>>(Tp &num) {
			bool neg = false, integer = false, decimal = false;while (is_blank(getchar_checked())) next();_reserve<MAX_FLOAT_SIZE>();
			if (getchar_unchecked() == '-') {neg = true;next();}if (!isdigit(getchar_unchecked()) && getchar_unchecked() != '.') return set_bad();
			if (isdigit(getchar_unchecked())) {integer = true;num = getchar_unchecked() - '0';while (next(), isdigit(getchar_unchecked())) num = num * 10 + (getchar_unchecked() - '0');}
			if (getchar_unchecked() == '.') if (next(), isdigit(getchar_unchecked())) {if (!integer) num = 0;decimal = true;Tp unit = 0.1;num += unit * (getchar_unchecked() - '0');while (next(), isdigit(getchar_unchecked())) num += (unit *= 0.1) * (getchar_unchecked() - '0');}
			if (!integer && !decimal) return set_bad();if (neg) num = -num;return *this;
		}
		InputHelper &operator>>(char &c) {while (is_blank(getchar_checked())) next();if (getchar_checked() == EOF) return set_bad();c = getchar_checked(), next();return *this;}
		InputHelper &operator>>(std::string &s) {while (is_blank(getchar_checked())) next();if (getchar_checked() == EOF) return set_bad();s.clear();do {s += getchar_checked();next();} while (!is_blank(getchar_checked()) && getchar_unchecked() != EOF);return *this;}
		explicit operator bool() { return m_ok; }
	};
	struct OutputHelper {
		FILE *m_file_ptr = nullptr;char m_buf[OUTPUT_BUFFER_SIZE], *m_end, *m_cursor;char m_temp_buf[MAX_FLOAT_SIZE], *m_temp_buf_cursor, *m_temp_buf_dot;uint64_t m_float_reserve, m_float_ratio;
		void _write() { fwrite(m_buf, 1, m_cursor - m_buf, m_file_ptr), m_cursor = m_buf; }
		template <size_type BlockSize> void _reserve() {size_type a = m_end - m_cursor;if (a >= BlockSize) return;_write();}
		OutputHelper(const char *outputFileName, size_type prec = 6) : m_cursor(m_buf), m_end(m_buf + OUTPUT_BUFFER_SIZE), m_temp_buf_cursor(m_temp_buf) { m_file_ptr = *outputFileName ? fopen(outputFileName, "wt") : stdout, precision(prec); }
		static OutputHelper &get_instance() {static OutputHelper s_obj(output_file);return s_obj;}
		~OutputHelper() { flush(), fclose(m_file_ptr); }
		void precision(size_type prec) { m_float_reserve = prec, m_float_ratio = uint64_t(std::pow(10, prec)), m_temp_buf_dot = m_temp_buf + prec; }
		OutputHelper &flush() { return _write(), fflush(m_file_ptr), *this; }
		void putchar(const char &c) {if (m_cursor == m_end) _write();*m_cursor++ = c;}
		template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
		OutputHelper &operator<<(Tp ret) {_reserve<MAX_INTEGER_SIZE>();size_type len = 0;if (ret >= 0) do *(m_cursor + len++) = '0' + ret % 10, ret /= 10;while (ret);else {putchar('-');do *(m_cursor + len++) = '0' - ret % 10, ret /= 10;while (ret);}for (size_type i = 0, j = len - 1; i < j;) std::swap(*(m_cursor + i++), *(m_cursor + j--));m_cursor += len;return *this;}
		template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
		OutputHelper &operator<<(Tp ret) {_reserve<MAX_INTEGER_SIZE>();size_type len = 0;do *(m_cursor + len++) = '0' + ret % 10, ret /= 10;while (ret);for (size_type i = 0, j = len - 1; i < j;) std::swap(*(m_cursor + i++), *(m_cursor + j--));m_cursor += len;return *this;}
		template <typename Tp, typename std::enable_if<std::is_floating_point<Tp>::value>::type * = nullptr>
		OutputHelper &operator<<(Tp ret) {
			if (ret < 0) {putchar('-');return *this << -ret;}ret *= m_float_ratio;uint64_t integer = ret;if (ret - integer >= 0.4999999999) integer++;do {*m_temp_buf_cursor++ = '0' + integer % 10;integer /= 10;} while (integer);
			if (m_temp_buf_cursor > m_temp_buf_dot) {do putchar(*--m_temp_buf_cursor);while (m_temp_buf_cursor > m_temp_buf_dot);putchar('.');}else {putchar('0'), putchar('.');for (size_type i = m_temp_buf_dot - m_temp_buf_cursor; i--;) putchar('0');}
			do putchar(*--m_temp_buf_cursor);while (m_temp_buf_cursor > m_temp_buf);
			return *this;
		}
		OutputHelper &operator<<(const char &ret) {putchar(ret);return *this;}
		OutputHelper &operator<<(const char *ret) {while (*ret) putchar(*ret++);return *this;}
		OutputHelper &operator<<(const std::string &ret) { return *this << ret.data(); }
	};
	InputHelper &getline(InputHelper &ih, std::string &line) {line.clear();if (ih.getchar_checked() == EOF) return ih.set_bad();while (!InputHelper::is_endline(ih.getchar_checked())) line += ih.getchar_unchecked(), ih.next();if (ih.getchar_unchecked() != EOF) ih.next();return ih;}
}using IO::getline;
#endif
namespace funcqwq{
	random_device seed;
	mt19937 rd32(seed());
	mt19937_64 rd64(seed());
	inline ll qpow(ll a, ll b){ll res = 1;for (;b;a *= a, b >>= 1)if (b & 1)res = res * a;return res;}
	inline ll qpow(ll a, ll b,  ll p){ll res = 1;for (;b;a = (i128)a * a % p,b >>= 1){(b & 1 ? res = (i128)res * a % p : 0);}return res;}
	inline ll _gcd(ll a, ll b){if (!a || !b) return a | b;int t = __builtin_ctzll(a | b);a >>= __builtin_ctzll(a);do{b >>= __builtin_ctzll(b);if (b < a) swap(a, b);b -= a;}while(b);return a << t;}
	bool miller_rabin(const ll p){
		if (p < 64) return 0x28208a20a08a28ac >> p & 1;if (!(p % 2)||!(p % 3)||!(p % 5)||!(p % 7)) return 0;
		ll d = p - 1;short k = __builtin_ctzll(d);d >>= k;
		for (register short asd = 0;8 - asd;++asd){
			ll pw = qpow(rd64()%(p-1)+1,d,p),pw1;
			for (register short j = 0;k - j;++j){pw1=(i128)pw*pw%p;if(pw1==1&&(pw^1)&&(pw^(p - 1)))return 0;pw = pw1;}
			if (pw ^ 1) return 0;
		}
		return 1;
	}
	namespace PRqwq{
		inline ll PR(ll x){
			if (x == 4) return 2;
			ll c= rd64() % (x - 2) + 1;ll s = rd64() % (x - 2) + 1, t = s;
			s = (i128)(s * s + c) % x;t = (i128)(t * t + c) % x;t = ((i128)t * t + c) % x;
			for (short i = 1;s ^ t;i = min(128, i << 1)){
				ll sum = 1, sum1;
				for (short j = 0;i - j;++j){
					if (!(sum1 = (i128)sum * abs(t - s) % x)) break;
					sum = sum1;s = ((i128)s * s + c) % x;t = ((i128)t * t + c) % x;t = ((i128)t * t + c) % x;
				}
				if ((sum1 = _gcd(sum, x)) ^ 1) return sum1;
			}
			return x;
		}
		ll mxfc;
		vector<pair<ll, short> > fc;
		inline void maxfac(ll x){if (x<2||x<=mxfc)return;if(miller_rabin(x))return(mxfc<x?mxfc=x:0),void();ll tmp=x;while(tmp>=x)tmp=PR(tmp);while(!(x%tmp))x/=tmp;maxfac(x),maxfac(tmp);}
		inline ll max_fac(ll x){mxfc = 1;maxfac(x);return mxfc;}
		inline void getfac(ll x){if(x==1)return;mxfc=1;maxfac(x);if(mxfc==x)return fc.emplace_back(mxfc,1),void();else{short c=0;while(!(x%mxfc))x/=mxfc,++c;fc.emplace_back(mxfc,c);getfac(x);}}
		inline vector<pair<ll, short> > get_fac(ll x, bool op = 0){fc.clear();getfac(x);if(op)reverse(fc.begin(),fc.end());return fc;}
	}
	using PRqwq::max_fac;
	using PRqwq::get_fac;
}
using funcqwq::qpow;
using funcqwq::miller_rabin;
using funcqwq::_gcd;
using funcqwq::max_fac;
using funcqwq::rd64;
using funcqwq::get_fac;
using funcqwq::rd32;
namespace tianyu{
	int n, m;
	int a[N], b[N];
	int ri[N], le[N], ri1[N];
	int asd[N];
	int bl[350], br[350];
	int bel[N];
	int now;
	struct que{
		int l, r, id;
		que() : l(N - 1) {}
	}q[N];
	int len, tot;
	inline int baoli(int l, int r){
		int res = 0;
		for (int i = l;i <= r;i++){
			if (asd[a[i]]) res = max(res, i - asd[a[i]]);
			else asd[a[i]] = i;
		}
		for (int i = l;i <= r;i++) asd[a[i]] = 0;
		return res;
	}
	inline void add1(int p){
		if (ri1[a[p]]) now = max(now, p - ri1[a[p]]);
		else ri1[a[p]] = p;
		ri[a[p]] = p;
	}
	inline void add2(int p){
		if (ri[a[p]]) now = max(now, ri[a[p]] - p);
		if (le[a[p]]) now = max(now, le[a[p]] - p);
		else le[a[p]] = p;
	}
	ll ans[N];
	void awa(){
		cin >> n;
		for (int i = 1;i <= n;i++) cin >> a[i], b[i] = a[i];
		sort(b + 1, b + 1 + n);
		int asd = unique(b + 1, b + 1 + n) - b - 1;
		for (int i = 1;i <= n;i++) a[i] = lower_bound(b + 1, b + 1 + asd, a[i]) - b;
		len = sqrt(n), tot = (n - 1) / len + 1;
		for (int i = 1;i <= tot;i++) bl[i] = (i - 1) * len + 1, br[i] = i * len;
		br[tot] = n;
		for (int i = 1;i <= n;i++) bel[i] = (i - 1) / len + 1;
		cin >> m;
		for (int i = 1;i <= m;i++){
			cin >> q[i].l >> q[i].r;
			q[i].id = i;
		}
		sort(q + 1, q + 1 + m, [](que a, que b){
			return bel[a.l] == bel[b.l] ? a.r < b.r : bel[a.l] < bel[b.l];
		});
		for (int nb = 1, i = 1, l, r;nb <= tot && i <= m;nb++){
			memset(ri1, 0, sizeof ri1);
			memset(ri, 0, sizeof ri);
			r = br[nb];
			int rans = 0;
			while (bel[q[i].l] == nb){
				if (q[i].r - q[i].l + 1 <= len){
					ans[q[i].id] = baoli(q[i].l, q[i].r);
					++i;
					continue;
				}
				l = br[nb] + 1;
				now = rans;
				while (r < q[i].r) add1(++r);
				rans = now;
				while (l > q[i].l) add2(--l);
				ans[q[i].id] = now;
				for (;l <= br[nb];++l) le[a[l]] = 0;
				++i;
			}
		}
		for (int i = 1;i <= m;i++) cout << ans[i] << '\n';
	}
}
signed main(){
	int T = 1;
	while (T--) tianyu::awa();
	return 0;
}