#include <bits/stdc++.h>
using namespace std;

namespace io {
const int SIZE = (1 << 18) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1;
#define getchar() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
inline void flush() {
    fwrite(obuf, 1, oS - obuf, stdout);
    oS = obuf;
}
inline void putchar(char x) {
    *oS++ = x;

    if (oS == oT)
        flush();
}
template <class Int>
inline void in(Int &n) {
    Int X     = 0;
    char ch   = 0;
    bool sign = 0;

    while (!isdigit(ch))
        sign |= ch == '-', ch = getchar();

    while (isdigit(ch))
        X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();

    n = (sign ? -X : X);
}
template <class Int, class... Args>
inline void in(Int &head, Args &...args) {
    in(head), in(args...);
}
template <class Int>
inline void out(Int n) {
    static unsigned char stack[100], top = 0;

    if (n < 0)
        putchar('-'), n = -n;

    if (!n)
        putchar('0');

    while (n)
        stack[++top] = n % 10 + '0', n /= 10;

    while (top)
        putchar(stack[top--]);
}
inline void out(const char *s) {
    while (*s)
        putchar(*s++);
}
struct Flusher {
    ~Flusher() {
        flush();
    }
} flusher;
}  // namespace io
using io::in;
using io::out;
using io::putchar;
#define space putchar(' ')
#define enter putchar('\n')

typedef long long LL;
constexpr int maxn = 100010, maxm = 500010, maxb1 = 330, maxb2 = 20;
struct QUES {
    int l, r, id, bel;
    LL ans;
    inline bool operator<(const QUES &q) {
        return bel != q.bel ? bel < q.bel : bel & 1 ? r < q.r : r > q.r;
    }
} Q[maxm];
vector<tuple<int, int, int>> v1[maxn], v2[maxn];
LL ANS[maxm];
int n, m, len, B, B1, B2, Num1, Num2;
int a[maxn], belong1[maxn], belong2[maxn], End1[maxb1], EndB[maxb2];
int last[maxn], pre[maxn], suc[maxn];
int tmp[maxn], val[maxn], id[maxn];
int sum1[maxb2][maxb2], sum2[maxb1][maxb2], sum3[maxb2][maxb1], sum4[maxb1][maxb1], sum5[maxn];

inline void insert(int x) {
    const int y = val[x], xBEL1 = belong1[x], xBEL2 = belong2[x], yBEL1 = belong1[y], yBEL2 = belong2[y];

    for (int i = xBEL2 + 1; i <= Num2; i++)
        for (int j = yBEL2 + 1; j <= Num2; j++)
            sum1[i][j]++;

    for (int i = xBEL1 + 1; i <= EndB[xBEL2]; i++)
        for (int j = yBEL2 + 1; j <= Num2; j++)
            sum2[i][j]++;

    for (int i = xBEL2 + 1; i <= Num2; i++)
        for (int j = yBEL1 + 1; j <= EndB[yBEL2]; j++)
            sum3[i][j]++;

    for (int i = xBEL1 + 1; i <= EndB[xBEL2]; i++)
        for (int j = yBEL1 + 1; j <= EndB[yBEL2]; j++)
            sum4[i][j]++;

    for (int i = x + 1; i <= End1[xBEL1]; i++)
        (val[i] > y) && sum5[i]++;

    for (int i = y + 1; i <= End1[yBEL1]; i++)
        (id[i] > End1[xBEL1]) && sum5[id[i]]++;
}
inline void erase(int x) {
    const int y = val[x], xBEL1 = belong1[x], xBEL2 = belong2[x], yBEL1 = belong1[y], yBEL2 = belong2[y];

    for (int i = xBEL2 + 1; i <= Num2; i++)
        for (int j = yBEL2 + 1; j <= Num2; j++)
            sum1[i][j]--;

    for (int i = xBEL1 + 1; i <= EndB[xBEL2]; i++)
        for (int j = yBEL2 + 1; j <= Num2; j++)
            sum2[i][j]--;

    for (int i = xBEL2 + 1; i <= Num2; i++)
        for (int j = yBEL1 + 1; j <= EndB[yBEL2]; j++)
            sum3[i][j]--;

    for (int i = xBEL1 + 1; i <= EndB[xBEL2]; i++)
        for (int j = yBEL1 + 1; j <= EndB[yBEL2]; j++)
            sum4[i][j]--;

    for (int i = x + 1; i <= End1[xBEL1]; i++)
        (val[i] > y) && sum5[i]--;

    for (int i = y + 1; i <= End1[yBEL1]; i++)
        (id[i] > End1[xBEL1]) && sum5[id[i]]--;
}
inline int query(int x) {
    const int y = val[x], xBEL1 = belong1[x], xBEL2 = belong2[x], yBEL1 = belong1[y], yBEL2 = belong2[y];
    return sum1[xBEL2][yBEL2] + sum2[xBEL1][yBEL2] + sum3[xBEL2][yBEL1] + sum4[xBEL1][yBEL1] + sum5[x];
}

inline void solve1() {
    for (int i = 1; i <= n; i++)
        tmp[a[i]]++;

    for (int i = 1; i <= n; i++)
        tmp[i] += tmp[i - 1];

    for (int i = 1; i <= n; i++)
        id[val[i] = tmp[a[i]]--] = i;

    long long sum;

    for (int i = n, L, R, ID; i; i--) {
        suc[i] &&(erase(suc[i]), 0);
        insert(i);

        for (auto &it : v1[i]) {
            tie(L, R, ID) = it, sum = 0;

            for (int j = L; j <= R; j++)
                sum += query(j) - (pre[j] > i ? query(pre[j]) : 0);

            ID > 0 ? Q[ID].ans += sum : Q[-ID].ans -= sum;
        }
    }
}
inline void solve2() {
    memset(tmp, 0, sizeof(tmp)), memset(sum1, 0, sizeof(sum1)), memset(sum2, 0, sizeof(sum2)),
           memset(sum3, 0, sizeof(sum3)), memset(sum4, 0, sizeof(sum4)), memset(sum5, 0, sizeof(sum5));

    for (int i = 1; i <= n; i++)
        tmp[a[i]]++;

    for (int i = 1; i <= n; i++)
        tmp[i] += tmp[i - 1];

    for (int i = 1; i <= n; i++)
        id[val[i] = tmp[a[i]]--] = i;

#define R_ n + 1 -
    long long sum;

    for (int i = 1, L, R, ID; i <= n; i++) {
        pre[i] &&(erase(R_ pre[i]), 0);
        insert(R_ i);

        for (auto &it : v2[i]) {
            tie(L, R, ID) = it, sum = 0;

            for (int j = L; j <= R; j++)
                sum += query(R_ j) - (suc[j] && suc[j] < i ? query(R_ suc[j]) : 0);

            ID > 0 ? Q[ID].ans += sum : Q[-ID].ans -= sum;
        }
    }
}

int main() {
    in(n), B = __builtin_pow(n, 0.25) + 1, B1 = B * B, B2 = B1 * B;

    for (int i = 1; i <= n; i++)
        in(a[i]), a[i] = R_ a[i], belong1[i] = (i - 1) / B1 + 1, belong2[i] = (i - 1) / B2 + 1,  //
                                               pre[i] = last[a[i]], last[a[i]] = i;

    memset(last, 0, sizeof(last));

    for (int i = n; i; i--)
        suc[i] = last[a[i]], last[a[i]] = i;

    Num1 = belong1[n], Num2 = belong2[n];

    for (int i = 1; i <= Num1; i++)
        End1[i] = i == Num1 ? n : i * B1;

    for (int i = 1; i <= Num2; i++)
        EndB[i] = i == Num2 ? Num1 : i * B;

    in(m), len = n / __builtin_sqrt(m);

    for (int i = 1; i <= m; i++)
        in(Q[i].l, Q[i].r), Q[i].id = i, Q[i].bel = (Q[i].l - 1) / len + 1;

    sort(Q + 1, Q + m + 1);

    for (int i = 1, l = 1, r = 1; i <= m; i++) {
        const int L = Q[i].l, R = Q[i].r;

        if (r < R)
            v1[l].emplace_back(r + 1, R, i), r = R;

        if (l > L)
            v2[r].emplace_back(L, l - 1, i), l = L;

        if (r > R)
            v1[l].emplace_back(R + 1, r, -i), r = R;

        if (l < L)
            v2[r].emplace_back(l, L - 1, -i), l = L;
    }

    solve1();
    reverse(a + 1, a + n + 1);

    for (int i = 1; i <= n; i++)
        a[i] = R_ a[i];

    solve2();

    for (int i = 1; i <= m; i++)
        Q[i].ans += Q[i - 1].ans;

    for (int i = 1; i <= m; i++)
        ANS[Q[i].id] = Q[i].ans;

    for (int i = 1; i <= m; i++)
        out(ANS[i]), enter;
}