#include <bits/stdc++.h>
using namespace std;
#define LL long long
inline int rd() {
    char c;
    int x = 0, f = 1;

    for (; !isdigit(c); c = getchar())
        if (c == '-')
            f = -1;

    for (; isdigit(c); c = getchar())
        x = x * 10 + c - '0';

    return x * f;
}
#define mp make_pair
#define pp pair<int,int>
int n, q, B, bl[300005], tong[300005], col[300005], len, c[2][300005], a[300005], K, oplen, num[1200005],
    Num[300005];
bool ok[300005];
pp opr[1200005];
LL ans[50005];
struct que {
    int l, r, id;
} Q[50005];
bool cmp(que a, que b) {
    return (bl[a.l] ^ bl[b.l]) ? bl[a.l] < bl[b.l] : ((bl[a.l] & 1) ? a.r<b.r: a.r>b.r);
}
set<int>S;
set<int>::iterator it;
void add(int x) {
    tong[col[a[x]]]--;

    if (!tong[col[a[x]]])
        opr[++oplen] = mp(-1, col[a[x]]);

    col[a[x]]++;

    if (col[a[x]] == 1)
        K++;

    tong[col[a[x]]]++;

    if (tong[col[a[x]]] == 1)
        opr[++oplen] = mp(1, col[a[x]]);
}
void dec(int x) {
    tong[col[a[x]]]--;

    if (!tong[col[a[x]]])
        opr[++oplen] = mp(-1, col[a[x]]);

    col[a[x]]--;

    if (col[a[x]] == 0)
        K--;

    tong[col[a[x]]]++;

    if (tong[col[a[x]]] == 1)
        opr[++oplen] = mp(1, col[a[x]]);
}
LL Sum1(int n) {
    return 1ll * n * (n + 1) / 2;
}
LL Sum2(int n) {
    return 1ll * n * (n + 1) * (2 * n + 1) / 6;
}
//0 1 2
LL calc1(int N, int c, int len) {
    return 1ll * c * c * (N + 1) + 1ll * Sum2(N) * len * len + 2ll * Sum1(N) * len * c;
}
LL calc2(int N, int c, int len) {
    return 1ll * c * c * (N + 1) + 1ll * Sum2(N) * len * len - 2ll * Sum1(N) * len * c;
}
//i^2len^2+2*i*lenl
LL solve(int L, int R) {
    int nlen = 0;

    for (int i = oplen; i >= 1; i--) {
        if (ok[opr[i].second])
            continue;

        ok[opr[i].second] = 1;

        if (opr[i].first == 1)
            Num[++nlen] = opr[i].second;
    }

    for (int i = 1; i <= len; i++) {
        if (ok[num[i]])
            continue;

        ok[num[i]] = 1;
        Num[++nlen] = num[i];
    }

    for (int i = oplen; i >= 1; i--)
        ok[opr[i].second] = 0;

    for (int i = 1; i <= len; i++)
        ok[num[i]] = 0;

    len = nlen;

    for (int i = 1; i <= len; i++)
        num[i] = Num[i];

    sort(num + 1, num + len + 1);

    for (int i = 1; i <= len; i++) {
        c[0][i] = num[i];
        c[1][i] = tong[num[i]];
    }

    int l = 0, r = 0, tot = 0, N = R - L + 1;
    LL Ans = 0;

    for (int i = 1; i <= len; i++) {
        int lput = 0, rput = 0, Len = c[0][i];

        if (tot % 2 == 0) {
            lput = (c[1][i] + 1) / 2;
            rput = c[1][i] / 2;
        } else {
            rput = (c[1][i] + 1) / 2;
            lput = c[1][i] / 2;
        }

        Ans += calc1(lput - 1, l, Len);
        Ans += calc2(lput - 1, N - l - Len, Len);
        Ans += calc1(rput - 1, r, Len);
        Ans += calc2(rput - 1, N - r - Len, Len);
        l += lput * Len, r += rput * Len;
        tot += c[1][i];
    }

    return 1ll * (1ll * K * N * (N + 1) - 1ll * N * (K - 1) - Ans) / 2;
}
int main() {
    scanf("%d %d", &n, &q);
    B = sqrt(n * 1.0);

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

    for (int i = 1; i <= n; i++)
        bl[i] = (i - 1) / B + 1;

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

    sort(Q + 1, Q + q + 1, cmp);
    int l = 1, r = 0;

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

        while (l < L)
            dec(l), l++;

        while (L < l)
            l--, add(l);

        while (r < R)
            r++, add(r);

        while (R < r)
            dec(r), r--;

        ans[Q[i].id] = solve(L, R);
    }

    for (int i = 1; i <= q; i++)
        printf("%lld\n", ans[i]);

    return 0;
}