#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using u64 = uint_fast64_t;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007;
//constexpr long long MOD = 998244353;
template<class T1, class T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return true;} return false; }
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return true;} return false; }
inline int popcount(int x) {return __builtin_popcount(x);}
inline int popcount(long long x) {return __builtin_popcountll(x);}
void print() { cout << "\n"; }
template<class T, class... Args>
void print(const T &x, const Args &... args) {
    cout << x << " ";
    print(args...);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////

template<typename T>
struct BinaryIndexedTree {
    int N;
    vector<T> data;

    BinaryIndexedTree(){}
    BinaryIndexedTree(int N) : N(N), data(N+1,0) {}

    // [0,k) (0-indexed) a[0] + … + a[k-1]
    T sum(int k) {
        T ret = 0;
        for(; k > 0; k -= k & -k) ret += data[k];
        return ret;
    }

    // [l,r) (0-indexed) a[l] + …　+ a[r-1]
    T sum(int l, int r) {
        if (l >= r) return 0;
        T vl = sum(l);
        T vr = sum(r);
        return vr - vl;
    }
    // (0-indexed) a[k] += x;
    void add(int k, T x) {
        for(++k; k <= N; k += k & -k) data[k] += x;
    }

    // (0-indexed)
    int lowerbound(T x) {
        int k = 1;
        int ret = 0;
        while ((k<<1) <= N) k <<= 1;
        while (k) {
            if (ret + k <= N && data[ret+k] < x) {
                x -= data[ret+k];
                ret += k;
            }
            k >>= 1;
        }
        return ret;
    }

    // (0-indexed)
    int upperbound(T x) {return lowerbound(x+1);}
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N; cin >> N;
    vector<int> p(N);
    rep(i,N) {
        cin >> p[i];
        --p[i];
    }

    int Q; cin >> Q;
    vector<int> L(Q),R(Q);
    rep(i,Q) {
        cin >> L[i] >> R[i];
        --L[i];
    }
    const int B = 500;
    vector<int> idx(Q);
    iota(all(idx),0);
    sort(all(idx),[&](int i, int j){
        if (L[i]/B==L[j]/B) return R[i] < R[j];
        return L[i] < L[j]; 
    });
    BinaryIndexedTree<int> BIT(N);
    vector<ll> ans(Q);
    int nl = 0, nr = 0;
    ll val = 0;
    rep(i,Q) {
        int u = idx[i];
        while (nl > L[u]) {
            nl--;
            val += BIT.sum(p[nl]);
            BIT.add(p[nl],1);
        }
        while (nr < R[u]) {
            val += BIT.sum(p[nr]+1,N);
            BIT.add(p[nr],1);
            nr++;
        }
        while (nl < L[u]) {
            BIT.add(p[nl],-1);
            val -= BIT.sum(p[nl]);
            nl++;
        }
        while (nr > R[u]) {
            nr--;
            BIT.add(p[nr],-1);
            val -= BIT.sum(p[nr]+1,N);
        }
        ans[u] = val;
    }

    for (auto i : ans) cout << i << ln;
}


Measured memory_bytes: 7644