#include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 using namespace std;

 #define N 50010

 struct node {

     int l, r, id, ans;

 } p[N];

 int bit[N], a[N], b[N], num[N], ans, kuai, n;

 bool cmp(const node &a, const node &b) {

     if(a.l / kuai == b.l / kuai) return a.r < b.r;

     return a.l / kuai < b.l / kuai;

 }

 bool cmpid(const node &a, const node &b) { return a.id < b.id; }

 int lowbit(int x) { return x & (-x); }

 void add(int x, int w) { for( ; x <= n; x += lowbit(x)) bit[x] += w; }

 int sum(int x) { int ans = ; for( ; x ; x -= lowbit(x)) ans += bit[x]; return ans; }

 int main() {

     while(~scanf("%d", &n)) {

         for(int i = ; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];

         int q; scanf("%d", &q);

         for(int i = ; i <= q; i++) scanf("%d%d", &p[i].l, &p[i].r), p[i].id = i;

         memset(bit, , sizeof(bit));

         ans = ; kuai = sqrt(n);

         sort(b + , b +  + n);

         int cnt = unique(b + , b +  + n) - b - ;

         for(int i = ; i <= n; i++) a[i] = lower_bound(b + , b +  + cnt, a[i]) - b;

         sort(p + , p +  + q, cmp);

         for(int L = , R = , i = ; i <= q; i++) {

             int l = p[i].l, r = p[i].r;

             for( ; L < l; L++) { ans -= sum(a[L] - ); add(a[L], -); }

             for( ; L > l; L--) { ans += sum(a[L-] - ); add(a[L-], ); }

             for( ; R < r; R++) { ans += R - L +  - sum(a[R+]); add(a[R+], ); }

             for( ; R > r; R--) { ans -= R - L +  - sum(a[R]); add(a[R], -); }

             p[i].ans = ans;

         }

         sort(p + , p +  + q, cmpid);

         for(int i = ; i <= q; i++) printf("%d\n", p[i].ans);

     }

     return ;

 }