#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <functional>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef map<int,int> mii;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<string> vs;
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define forup(i,a,b) for(int i=(a);i<=(b);i++)
#define fordn(i,a,b) for(int i=(a);i>=(b);i--)
#define drep(i,n) for(i=0;i<(n);i++)
#define dforup(i,a,b) for(i=(a);i<=(b);i++)
#define dfordn(i,a,b) for(i=(a);i>=(b);i--)
#define all(x) x.begin(),x.end()
#define permute(x) next_permutation(all(x))
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define gi(x) scanf("%d",&x)
 
/************************BIT Codechunk**************************/
 
struct BIT
{
	int bn; //bn>0
	vector<int> bA;
	
	BIT(){ bn=0; }
	BIT(int bn_){ bn=bn_; bA.resize(bn+1); fill(bA.begin(),bA.end(),0); }
	
	int prefix(int bposn)
	{
		if(bposn<=0) return 0;
		if(bposn>bn) bposn=bn;
		
		int ret=0;
		for(int i=bposn; i>0; i-=((i)&(-i)))
			ret+=bA[i];
		return ret;
	}
	
	void update(int bposn, int bincr)
	{
		if(bposn<=0) return;
		if(bposn>bn) return;
		
		for(int i=bposn; i<=bn; i+=((i)&(-i)))
			bA[i]+=bincr;
	}
	
	int query(int bl, int br)
	{
		if(br<=0 or bl>bn or bl>br) return 0;
		if(bl<=0) bl=1;
		if(br>bn) br=bn;
		return (prefix(br)-prefix(bl-1));
	}
};
 
/******************End of BIT Codechunk*************************/
 
struct query_t {
	int l,r,ix;
	query_t(int l_,int r_,int ix_) {
		l=l_; r=r_; ix=ix_;
	}
};
 
bool operator<(query_t q1,query_t q2) {
	return (q1.r<q2.r);
}
 
const int max_n=20010;
const int max_q=20010;
int n,q,l,r;
int a[max_n]; int ta[max_n];
mii M; int cnt;
vector<query_t> chunks[150];
int ans[max_q];
BIT bit;
 
int main() {
	gi(n);
	assert(n <= 20000);
	assert(n >= 1);
	int root=(int)ceil(sqrt(double(n)));
	rep(i,n) {
		gi(a[i]);
		assert(a[i] <= 1000000000);
		assert(a[i] >= 0);
		ta[i]=a[i];
	}
	gi(q);
	assert(q <= 20000);
	assert(q >= 1);
	rep(i,q) {
		gi(l); gi(r);
		assert(l <= r);
		assert(r <= n);
		assert(l >= 1);
		l--; r--;
		chunks[l/root].pb(query_t(l,r,i));
	}
 
	sort(ta,ta+n);
	cnt=int(unique(ta,ta+n)-ta);
	rep(i,n)
		a[i]=1+int(lower_bound(ta,ta+cnt,a[i])-ta);
	int sz=(n+root-1)/root;
	n=cnt;
	rep(i,sz) {
		int cl=root*i;
		int cr=cl-1;
		int res=0;
		bit=BIT(n);
		sort(chunks[i].begin(),chunks[i].end());
		rep(j,chunks[i].size()) {
			l=chunks[i][j].l; r=chunks[i][j].r; int ix=chunks[i][j].ix;
			while(cr!=r) {
				++cr;
				res+=bit.query(a[cr]+1,n);
				bit.update(a[cr],1);
			}
			if(l>=cl) {
				while(cl!=l) {
					res-=bit.prefix(a[cl]-1);
					bit.update(a[cl],-1);
					++cl;
				}
			}
			else {
				while(cl!=l) {
					--cl;
					res+=bit.prefix(a[cl]-1);
					bit.update(a[cl],1);
				}
			}
			ans[ix]=res;
		}
	}
	rep(i,q) printf("%d\n",ans[i]);
	return 0;
}