1 #include <cstdio>
2 #include <cstring>
3 #include <cmath>
4 #include <algorithm>
5 #include <iostream>
6 using namespace std;
7 const int maxn = 50010;
8 struct Qry{
9 int l, r, pos, id;
10 bool operator < (const Qry &a)const {
11 if(pos == a.pos) return r < a.r;
12 return pos < a.pos;
13 }
14 }q[maxn];
15 int res[maxn];
16 struct BIT{
17 int n, c[maxn];
18 inline void init(int _n){
19 n = _n;
20 memset(c, 0, sizeof c);
21 }
22 inline void add(int i, int v){
23 for(; i <= n; i += i & -i) c[i] += v;
24 }
25 inline int sum(int i){
26 int res = 0;
27 for(; i; i -= i & -i){
28 res += c[i];
29 }
30 return res;
31 }
32 inline int sum(int l, int r){
33 return sum(r) - sum(l - 1);
34 }
35 }bit;
36 int ans;
37 int a[maxn], mp[maxn];
38 void solve(int n, int m){
39 int l = 1, r = 0;
40 ans = 0;
41 for(int i = 0; i < m; i++){
42 while(l < q[i].l) ans -= bit.sum(1, a[l] - 1), bit.add(a[l], -1), l++;
43 while(l > q[i].l) l--, ans += bit.sum(1, a[l] - 1), bit.add(a[l], 1);
44 while(r > q[i].r) ans -= bit.sum(a[r] + 1, n), bit.add(a[r], -1), r--;
45 while(r < q[i].r) r++, ans += bit.sum(a[r] + 1, n), bit.add(a[r], 1);
46 res[q[i].id] = ans;
47 }
48 }
49 int n;
50 int BIN(int x){
51 int l = 1, r = n;
52 while(l <= r){
53 int m = l + r >> 1;
54 if(x < mp[m]) r = m - 1;
55 else if(x == mp[m]) return m;
56 else l = m + 1;
57 }
58 }
59 int main(){
60 while(scanf("%d", &n) != EOF){
61 bit.init(n);
62 int SZ = sqrt(n * 1.0);
63 for(int i = 1; i <= n; i++){
64 scanf("%d", &a[i]);
65 mp[i] = a[i];
66 }
67 sort(mp + 1, mp + n + 1);
68 for(int i = 1; i <= n; i++) a[i] = BIN(a[i]);
69 int m;
70 scanf("%d", &m);
71 for(int i = 0; i < m; i++){
72 scanf("%d %d", &q[i].l, &q[i].r);
73 q[i].id = i;
74 q[i].pos = (q[i].l - 1) / SZ + 1;
75 }
76 sort(q, q + m);
77 solve(n, m);
78 for(int i = 0; i < m; i++) printf("%d\n", res[i]);
79 }
80 return 0;
81 }
