#include <bits/stdc++.h>
using namespace std;
const int A = 3e5;
const int K = 1000;
inline long long getSum(int x)
{
return x * (x + 1LL) / 2;
}
long long calc(vector<int> &smallCnt, map<int, int> &bigCnt, int sumAll)
{
int side = 0;
long long sum[2] = {0}, res = 0;
auto go = [&](int k, int v)
{
int x = (v + 1) / 2, y = v / 2;
res += 1LL * x * (sumAll - sum[side]) * sum[side] + getSum(x) * k * (sumAll - sum[side]);
res -= getSum(x - 1) * k * sum[side] + (x - 1LL) * x * (x + 1) / 3 * k * k;
res -= getSum(k - 1) * x;
sum[side] += x * k;
if (y)
{
res += 1LL * y * (sumAll - sum[side ^ 1]) * sum[side ^ 1] + getSum(y) * k * (sumAll - sum[side ^ 1]);
res -= getSum(y - 1) * k * sum[side ^ 1] + (y - 1LL) * y * (y + 1) / 3 * k * k;
res -= getSum(k - 1) * y;
sum[side ^ 1] += y * k;
}
side ^= v % 2;
};
for (int i = 1; i < K; i++)
if (smallCnt[i])
go(i, smallCnt[i]);
for (auto [k, v] : bigCnt)
go(k, v);
return res;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
a[i]--;
}
vector<int> l(q), r(q);
for (int i = 0; i < q; i++)
{
cin >> l[i] >> r[i];
l[i]--;
r[i]--;
}
vector<int> id(q);
iota(begin(id), end(id), 0);
auto cmp = [&](int u, int v)
{
if (l[u] / K != l[v] / K)
return l[u] < l[v];
return l[u] / K & 1 ? r[u] < r[v] : r[u] > r[v];
};
sort(begin(id), end(id), cmp);
vector<int> cnt(A), smallCnt(K);
map<int, int> bigCnt;
auto add = [&](int x)
{
if (cnt[x] < K) smallCnt[cnt[x]]--;
else if (!--bigCnt[cnt[x]]) bigCnt.erase(cnt[x]);
cnt[x]++;
if (cnt[x] < K) smallCnt[cnt[x]]++;
else bigCnt[cnt[x]]++;
};
auto remove = [&](int x)
{
if (cnt[x] < K) smallCnt[cnt[x]]--;
else if (!--bigCnt[cnt[x]]) bigCnt.erase(cnt[x]);
cnt[x]--;
if (cnt[x] < K) smallCnt[cnt[x]]++;
else bigCnt[cnt[x]]++;
};
vector<long long> ans(q);
int curL = 0, curR = -1;
for (int i : id)
{
while (curL > l[i])
add(a[--curL]);
while (curR < r[i])
add(a[++curR]);
while (curL < l[i])
remove(a[curL++]);
while (curR > r[i])
remove(a[curR--]);
ans[i] = calc(smallCnt, bigCnt, r[i] - l[i] + 1);
}
for (auto x : ans)
cout << x << '\n';
}
