#include<bits/stdc++.h>

using namespace std;

int n,m,cnt;
struct node{
	int val,l,r;
}tree[100010];
int a[100010],root[100010],ls[100010],rs[100010];
int ql,qr;

int up_date(int i){
	return tree[i].val = tree[tree[i].l].val + tree[tree[i].r].val;
}

int build_tree(int l,int r){
	int k = ++cnt;
	tree[k].val = 0;
	int mid = (l+r) >> 1;
	if(l < r){
		tree[k].l = build_tree(l,mid);
		tree[k].r = build_tree(mid+1,r);
	}
	return k;
}

int add_tree(int pre,int l,int r,int x){
	int k = ++cnt;
	tree[k].l = tree[pre].l;
	tree[k].r = tree[pre].r;
	tree[k].val = tree[pre].val+1;
	int mid = (l + r) >> 1;
	if(l < r){
		if(x <= mid){
			tree[k].l = add_tree(tree[pre].l,l,mid,x);
		}
		else{
			tree[k].r = add_tree(tree[pre].r,mid+1,r,x);
		}
	}
	return k;
}

int query(int u,int v,int l,int r,int ql,int qr){
	if(l == r) return 1;
	if(ql >= l && qr <= r) return tree[v].val - tree[u].val;
	else if(r < ql || l > qr) return 0; 
	else{
		int mid = (l+r) >> 1;
		return (query(tree[u].l,tree[v].l,l,mid,ql,qr) + query(tree[u].l,tree[v].r,mid+1,r,ql,qr));
	}
}
//链接https://roll.sohu.com/a/609841985_453160 END
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	root[1] = build_tree(1,n);
	cin >> m;
	for(int i = 2; i <= n; i++){
		root[i] = add_tree(root[i-1],1,n,i);
	}
	for(int i = 1; i <= m; i++){
		int l,r;
		cin >> l >> r;
		cout << query(root[l-1],root[r],1,n,l,r) << endl;
	}
	return 0;
}