#include <bits/stdc++.h>
using namespace std;
#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define ll long long
int cnt[300005], a[300005], l[300005], r[300005];
ll n, out[50005];
const int SQRT = 900;
ll f(ll a, ll b, ll x) {
// sum((a+bi) choose 2) with x terms
return x*a*a + a*b*x*(x-1) + x*(x-1)*(2*x-1)/6*b*b - (2*a+b*(x-1))*x/2;
}
ll val(ll start, ll sz, ll num) {
// We have num blocks of size sz, starting at position start
// What is the total contribution?
if (!num || !sz) return 0;
ll res = n*(n+1)*num;
res -= f(start, sz, num);
res -= f(n-(start+sz*num-1)+1, sz, num);
return res/2;
}
bool comp(int x, int y) {
int p = l[x]/SQRT, q = l[y]/SQRT;
if (p != q) return p < q;
return p&1 ? (r[x] < r[y]) : (r[x] > r[y]);
}
vector<int> s;
bool included[300005];
int freq[300005], v[300005];
void add(int x) {
if (freq[x] && !--v[freq[x]]) included[freq[x]] = false;
v[++freq[x]]++;
if (!included[freq[x]]) {
included[freq[x]] = true;
s.push_back(freq[x]);
}
}
void remove(int x) {
if (!--v[freq[x]]) included[freq[x]] = false;
v[--freq[x]]++;
if (!included[freq[x]]) {
included[freq[x]] = true;
s.push_back(freq[x]);
}
}
ll solve() {
ll ans = 0;
int lsum = 0, rsum = 0;
sort(s.begin(), s.end());
vector<int> cur;
for (int sz : s) {
if (!included[sz]) continue;
included[sz] = false;
cur.push_back(sz);
int num = v[sz];
int lv = 0, rv = 0;
if (lsum < rsum) {
lv = num-num/2;
rv = num/2;
} else {
rv = num-num/2;
lv = num/2;
}
ans += val(lsum+1, sz, lv) + val(rsum+1, sz, rv);
lsum += sz*lv;
rsum += sz*rv;
}
s = cur;
for (int i : s) included[i] = true;
return ans;
}
int main() {
int q, x;
scan(n);
scan(q);
vector<int> order;
for (int i=1; i<=n; i++) scan(a[i]);
for (int i=1; i<=q; i++) {
scan(l[i]);
scan(r[i]);
order.push_back(i);
}
sort(order.begin(), order.end(), comp);
int L = 1, R = 0;
for (int i : order) {
while (R < r[i]) add(a[++R]);
while (L > l[i]) add(a[--L]);
while (R > r[i]) remove(a[R--]);
while (L < l[i]) remove(a[L++]);
n = R-L+1;
out[i] = solve();
}
for (int i=1; i<=q; i++) printf("%lld\n", out[i]);
}
