#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct E {
	int v, i;
};
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<E> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i].v;
		v[i].i = i + 1;
	}
	sort(v.begin(), v.end(), [](const E& a, const E& b) {
		if (a.v != b.v) return a.v < b.v;
		return a.i < b.i;
	});
	vector<int> u;
	vector<pair<int, int>> r;
	for (int i = 0; i < n; ) {
		int j = i;
		while (j < n && v[j].v == v[i].v) j++;
		u.push_back(v[i].v);
		r.push_back({i, j});
		i = j;
	}
	int q;
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		auto itX = lower_bound(u.begin(), u.end(), x);
		if (itX == u.end() || *itX != x) {
			cout << "0\n";
			continue;
		}
		auto itY = lower_bound(u.begin(), u.end(), y);
		if (itY == u.end() || *itY != y) {
			cout << "0\n";
			continue;
		}
		int iX = itX - u.begin(), iY = itY - u.begin();
		int sX = r[iX].first, eX = r[iX].second;
		int sY = r[iY].first, eY = r[iY].second;
		int cX = eX - sX, cY = eY - sY;
		int low = 1, high = min(cX, cY), k = 0;
		while (low <= high) {
			int mid = (low + high) / 2;
			int valX = v[sX + mid - 1].i;
			int countY = lower_bound(v.begin() + sY, v.begin() + eY, valX, [](const E& e, int val) {
				return e.i < val;
			}) - (v.begin() + sY);
			if (mid + countY <= cY) {
				k = mid;
				low = mid + 1;
			} else {
				high = mid - 1;
			}
		}
		cout << k << '\n';
	}
	return 0;
}