#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int N = 123456;
ll P = 999999929;//1585931419LL;
ll MOD = 1000000007LL;
ll p[N], par[N], Hash[N], cp[N];
void pre(){
	p[0] = cp[0]=1LL;
	for(int i = 1; i<N; i++){
		p[i] = (p[i-1] * P) % MOD;
		cp[i] = (cp[i-1] + p[i])%MOD;
	}
}

void hashParent(int sz){
	for(int i = 1; i<=sz; i++)
		Hash[i] = (par[i-1] * p[i-1]) % MOD;
		
	for (int i = 1; i<=sz; i++)
		Hash[i] = (Hash[i] + Hash[i-1]) % MOD;
}
ll hashPattern(int l, int r){
	ll hp = 0LL;
	for(int i = l; i<=r; i++)
		hp = (hp + par[i-1] * p[i-l]) % MOD;
	return hp;
}
void solve()
{
	int n;
	cin >> n;
	for (int i = 0; i<n; i++)
		cin >> par[i];
	hashParent(n);

	int q;
	cin >> q;
	while (q--){
		int l, r, cnt = 0;
		cin >> l >> r;
		int sz = r-l+1;
		ll hp = hashPattern(l, r);
		
		for (int i = 0; i + sz < l; i++){
			ll part = (Hash[i+sz] - Hash[i] + MOD) % MOD;
			ll z = (par[l-1] + par[i]) % MOD;
			z = (z * cp[sz-1]) % MOD;
			ll cmp = (z - hp + MOD) % MOD;
			if (part == (cmp * p[i])%MOD)
			++cnt;
		}
		for(int i = r; i + sz <= n; i++){
			ll part = (Hash[i+sz] - Hash[i] + MOD) % MOD;
			ll z = (par[l-1] + par[i]);
			z = (z * cp[sz-1]) % MOD;
			ll cmp = (z - hp + MOD) % MOD;
			if (part == (cmp * p[i]) % MOD)
				++cnt;
		}
		cout << cnt << endl;
	}
}

int main()
{
	pre();
	solve();
	return 0;
}