#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <deque>
using namespace std;
const int mx = 300'000;
const int mxQ = 50'000;
const int rt = 500;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
#define sz(x) (int(x.size()))
int N, Q;
vi a(1+mx);
vi l(1+mxQ), r(1+mxQ);
vll ans(1+mxQ);
int L = 1;
int R = 0;
vll ct(1+mx, 0);
vll freq(1+mx, 0);
vector<ll> sizes;
vector<bool> occ(1+mx, 0);
const ll bs = 1'000'000'000;
const int bc = 4;
struct largeint
{
vll x = vll(bc, 0);
largeint()
{
;
}
largeint(ll k)
{
for(int u = 0; u < bc; u++)
{
x[u] += k%bs;
k /= bs;
}
}
ll get_long()
{
return x[0] + bs*x[1] + bs*bs*x[2];
}
};
largeint operator + (largeint X, largeint Y)
{
largeint res;
for(int u = 0; u < bc; u++)
{
res.x[u] = X.x[u] + Y.x[u];
if(u+1 < bc)
{
res.x[u+1] += res.x[u] / bs;
res.x[u] %= bs;
}
}
return res;
}
largeint operator - (largeint X, largeint Y)
{
largeint res;
for(int u = 0; u < bc; u++)
{
res.x[u] = X.x[u] - Y.x[u];
if(res.x[u] < 0)
{
res.x[u] += bs;
res.x[u+1] -= 1;
}
}
return res;
}
largeint operator * (largeint X, largeint Y)
{
largeint res;
for(int u = 0; u < bc; u++)
{
for(int v = 0; v < bc; v++)
{
if(u+v >= bc) continue;
res.x[u+v] += X.x[u] * Y.x[v];
if(res.x[u+v] >= bs)
{
res.x[u+v+1] += res.x[u+v]/bs;
res.x[u+v] %= bs;
}
}
}
for(int u = 0; u+1 < bc; u++)
{
if(u+1 < bc)
{
res.x[u+1] += res.x[u] / bs;
res.x[u] %= bs;
}
}
return res;
// for(int u = 0; u < bc; u++)
// {
// res.x[u] = X.x[u] + Y.x[u];
// if(u+1 < bc)
// {
// res.x[u+1] += res.x[u] / bs;
// res.x[u] %= bs;
// }
// }
}
largeint ap_sum(ll a, ll d, ll n)
{
return largeint((n * (2*a + (n-1)*d))/2);
}
largeint ap_sq_sum(ll a, ll d, ll n)
{
/*
a^2 + (a+d)^2 + ... + (a+(n-1)*d)^2
= n * a^2 + 2*a*(0d + 1d + ... + (n-1)d) + 0d^2 + d^2 + ... (n-1)d ^ 2
= n*a^2 + 2*a*d * (n-1)*n/2 + d^2 * (n-1)*(n)*(2n-1)/6
*/
// assert(d*n <= 300'000);
// assert(d*d*n*n*2*n <= 1'000'000'000'000'0000);
return largeint(n*a*a + a*d*(n-1)*n) + largeint(d*d)*largeint(((n-1)*n*(2*n-1))/6LL);
}
ll get_ans()
{
vector<ll> sizes2;
for(ll s: sizes)
{
if(occ[s]) continue;
if(freq[s] == 0) continue;
sizes2.push_back(s);
occ[s] = 1;
}
sizes = sizes2;
sizes2.clear();
for(ll s: sizes) occ[s] = 0;
sort(sizes.begin(), sizes.end(), [] (int u, int v)
{
return u > v;
});
deque< pair<ll, ll> > ord;
int z = 0;
for(ll s: sizes)
{
if(freq[s] % 2 == 1)
{
if(z) ord.push_back({s, 1});
else ord.push_front({s, 1});
z = !z;
}
if(freq[s]/2)
{
ord.push_back({s, freq[s]/2});
ord.push_front({s, freq[s]/2});
}
}
ord.push_front({0, 0});
largeint ans(0);
ll tot = 0;
int P = sz(ord);
vll prefsum(1+P, 0);
for(int i = 1; i <= P; i++)
{
prefsum[i] = prefsum[i-1] + (ord[i].first * ord[i].second);
}
tot = prefsum[P];
for(int i = 1; i <= P; i++)
{
ans = ans + largeint(ord[i].second) * largeint((ord[i].first * (ord[i].first + 1))/2);
ans = ans + largeint(ord[i].second * largeint(largeint(ord[i].first) * (largeint(tot) - largeint(ord[i].first))));
ans = ans + largeint((tot - ord[i].first) * ap_sum(prefsum[i-1], ord[i].first, ord[i].second));
ans = ans - ap_sq_sum(prefsum[i-1], ord[i].first, ord[i].second);
}
return ans.get_long();
}
void add_species(int a)
{
freq[ct[a]]--;
ct[a]++;
freq[ct[a]]++;
sizes.push_back(ct[a]);
}
void remove_species(int a)
{
freq[ct[a]]--;
ct[a]--;
freq[ct[a]]++;
sizes.push_back(ct[a]);
}
void expand_right()
{
R++;
add_species(a[R]);
}
void expand_left()
{
L--;
add_species(a[L]);
}
void contract_right()
{
remove_species(a[R]);
R--;
}
void contract_left()
{
remove_species(a[L]);
L++;
}
int main()
{
cin >> N >> Q;
for(int i = 1; i <= N; i++) cin >> a[i];
for(int j = 1; j <= Q; j++) cin >> l[j] >> r[j];
vi I(Q);
for(int j = 0; j < Q; j++) I[j] = j+1;
sort(I.begin(), I.end(), [] (int u, int v)
{
if(l[u]/rt != l[v]/rt) return l[u]/rt < l[v]/rt;
else return r[u] < r[v];
});
freq[0] = mx;
for(int q: I)
{
while(R < r[q]) expand_right();
while(L > l[q]) expand_left();
while(R > r[q]) contract_right();
while(L < l[q]) contract_left();
ans[q] = get_ans();
}
for(int q = 1; q <= Q; q++) cout << ans[q] << '\n';
}
