#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define all(x) x.begin(), x.end()

const int N = 1e5 + 10;
const int B = 320; // roughly sqrt N
int a[N];
int cnt[N];
ll sum = 0;

void add(int v) {
    sum += cnt[v];
    cnt[v]++;
}

void del(int v) {
    cnt[v]--;
    sum -= cnt[v];
}

int L = 0, R = -1; // the pointers

void move(int l, int r) { // move pointers to the query point
    while (R < r) {
        ++R;
        add(a[R]);
    }
    while (R > r) {
        del(a[R]);
        R--;
    }
    while (L > l) {
        L--;
        add(a[L]);
    }
    while (L < l) {
        del(a[L]);
        L++;
    }
}

struct query {
    int l, r, i;
};

signed main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    int queries;
    cin >> queries;
    vector<query> q(queries);
    vector<ll> ans(queries);
    for (int i = 0; i < queries; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        q[i] = {l, r, i};
    }
    sort(all(q), [&](const query &a, const query &b) {
        int al = a.l / B;
        int bl = b.l / B;
        if (al != bl)
            return al < bl;
        return a.r < b.r;
    });
    for (auto &[l, r, i] : q) {
        move(l, r);
        ans[i] = sum;
    }
    for (int i = 0; i < queries; i++)
        cout << ans[i] << ' ';
    cout << '\n';
    return 0;
}

На движение указателей $$$L$$$ и $$$R$$$ можно смотреть как на передвижение по манхэттенской плоскости $$$n \times n$$$, где ось X отвечает за координату $$$L$$$, а ось Y — за $$$R$$$. Запросы в таком случае — просто точки на этой плоскости, которые мы в каком-то порядке обходим. Разобьём плоскость на квадратики $$$B \times B$$$. Тогда оценка снизу на время работы $$$O(n \sqrt n)$$$ достигается, если в левый нижний угол каждого квадратика поместить по запросу, их тогда будет как раз $$$\sqrt n \times \sqrt n = n$$$. Оценка сверху достигается таким обходом:

Мы будем обходить квадратики в порядке слева направо, сверху вниз. Тогда указатель $$$R$$$ двигается с $$$1$$$ до $$$n$$$ ровно $$$\frac{n}{B}$$$ раз, а указатель $$$L$$$ двигается в каждом квадратике не больше чем на $$$B$$$ для очередного запроса. Тем самым получается, что оба указателя двигаются $$$O(n \sqrt n)$$$ раз, что и составляет время работы.