#include <vector>
#include <utility>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

inline int calcIndex(int i, int j) {
	return j * (j + 1) / 2 + (j - i);
}

int main() {
	const int BlockSize = 400;
	const int MaxN = 100000, MaxNumBlocks = (MaxN + BlockSize - 1) / BlockSize;
	static int counts[MaxNumBlocks + 1][MaxN + 1];
	static short counts2[BlockSize + 1][BlockSize + 1];

	int N;
	while(~scanf("%d", &N)) {
		int X = N;
		vector<int> p(N);
		for(int i = 0; i < N; ++ i) {
			scanf("%d", &p[i]), -- p[i];
		}
		int NumBlocks = (N + BlockSize - 1) / BlockSize;
		memset(counts, 0, sizeof counts);
		for(int bi = 0; bi < NumBlocks; ++ bi) {
			int L = bi * BlockSize, R = min((bi + 1) * BlockSize, N);
			for(int i = L; i < R; ++ i)
				++ counts[bi + 1][p[i] + 1];
			for(int x = 1; x <= X; ++ x)
				counts[bi + 1][x] += counts[bi][x] + counts[bi + 1][x - 1] - counts[bi][x - 1];
		}
		vector<vector<pair<int, int> > > sortedBlocks(NumBlocks);
		vector<vector<int> > inner(NumBlocks);
		for(int bi = 0; bi < NumBlocks; ++ bi) {
			int L = bi * BlockSize, R = min((bi + 1) * BlockSize, N);
			int M = R - L, Y = M;

			vector<pair<int, int> > &sorted = sortedBlocks[bi];
			sorted.resize(M);
			for(int i = L; i < R; ++ i)
				sorted[i - L] = make_pair(p[i], i);
			sort(sorted.begin(), sorted.end());
			
			vector<int> rank(M);
			for(int i = 0; i < M; ++ i)
				rank[sorted[i].second - L] = i;

			memset(counts2, 0, sizeof counts2);

			for(int i = 0; i < M; ++ i)
				++ counts2[i + 1][rank[i] + 1];
			for(int i = 0; i < M; ++ i) for(int y = 1; y <= Y; ++ y)
				counts2[i + 1][y] += counts2[i][y] + counts2[i + 1][y - 1] - counts2[i][y - 1];

			vector<int> &v = inner[bi];
			v.resize((R - L) * (R - L + 1) / 2);
			int k = 0;
			for(int j = 0; j < M; ++ j) {
				int sum = 0;
				for(int i = j; i >= 0; -- i) {
					sum += counts2[j + 1][rank[i]] - counts2[i + 1][rank[i]];
					v[k ++] = sum;
				}
			}
		}
		vector<vector<long long> > outer(NumBlocks + 1, vector<long long>(N));
		for(int bi = 0; bi <= NumBlocks; ++ bi) {
			vector<long long> &v = outer[bi];
			long long sum;
			sum = 0;
			for(int bj = bi; bj < NumBlocks; ++ bj) {
				int L = bj * BlockSize, R = min((bj + 1) * BlockSize, N);
				int num = (bj - bi) * BlockSize;
				for(int j = L; j < R; ++ j) {
					sum += num - (counts[bj][p[j] + 1] - counts[bi][p[j] + 1]);
					v[j] = sum;
				}
				sum += inner[bj][calcIndex(0, R - L - 1)];
			}
			sum = 0;
			for(int bj = bi - 1; bj >= 0; -- bj) {
				int L = bj * BlockSize, R = min((bj + 1) * BlockSize, N);
				for(int j = R - 1; j >= L; -- j) {
					sum += counts[bi][p[j]] - counts[bj + 1][p[j]];
					v[j] = sum;
				}
				sum += inner[bj][calcIndex(0, R - L - 1)];
			}
		}
		int Q;
		scanf("%d", &Q);
		for(int ii = 0; ii < Q; ++ ii) {
			int l; int r;
			scanf("%d%d", &l, &r), -- l;
			int bl = (l + BlockSize - 1) / BlockSize, br = r / BlockSize;
			long long ans = 0;
			if(l / BlockSize == (r - 1) / BlockSize) {
				ans = inner[l / BlockSize][calcIndex(l % BlockSize, (r - 1) % BlockSize)];
			} else {
				int L = bl * BlockSize, R = br * BlockSize;
				ans += outer[bl][r - 1];
				ans += inner[(r - 1) / BlockSize][calcIndex(0, (r - 1) % BlockSize)];
				if(l < R) {
					ans += outer[br][l];
					ans += inner[l / BlockSize][calcIndex(l % BlockSize, min(BlockSize, N - l / BlockSize * BlockSize) - 1)];
				}
				if(bl < br) {
					ans -= outer[bl][R - 1];
					ans -= inner[(R - 1) / BlockSize][calcIndex(0, BlockSize - 1)];
				}
				if(l < L && R < r) {
					const vector<pair<int, int> > &v = sortedBlocks[bl - 1], &w = sortedBlocks[br];
					int nv = (int)v.size(), nw = (int)w.size();
					for(int i = 0, j = 0, cnt = 0; i < nv; ++ i) {
						for(; j < nw && w[j].first < v[i].first; ++ j)
							cnt += w[j].second < r;
						if(l <= v[i].second)
							ans += cnt;
					}
				}
			}
			printf("%lld\n", ans);
			//fflush(stdout);
		}
	}
	return 0;
}

Measured memory_bytes: 377236