#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 3e5 + 5;
const int b = 550;
ll n, Q, a[NMAX], ans[NMAX], l, r, c[NMAX], cnt[NMAX], ls, rs, x, y, res, in[NMAX];
vector<int> mp;
struct query{
int i, l, r;
bool operator <(const query& x){
if(l / b == x.l / b) return (l / b & 1) ? r > x.r : r < x.r;
else return l / b < x.l / b;
}
} q[NMAX];
void f(int x, int v){
cnt[c[x]]--;
c[x] += v;
if(!cnt[c[x]]++ && !in[c[x]]) mp.emplace_back(c[x]), in[c[x]] = 1;
return;
}
ll cal(ll l, ll x, ll c){ return x * (x + 1) * (2 * x + 1) / 6 * c * c + c * (l - c) * x * (x + 1) + (l - c) * (l - c) * x;}
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> Q;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 0; i < Q; i++) cin >> q[i].l >> q[i].r, q[i].i = i;
sort(q, q + Q);
l = 1, r = 0;
for(int i = 0; i < Q; i++){
while(l > q[i].l) f(a[--l], 1);
while(r < q[i].r) f(a[++r], 1);
while(l < q[i].l) f(a[l++], -1);
while(r > q[i].r) f(a[r--], -1);
for(int i = 0; i < mp.size(); i++)
if(!cnt[mp[i]]) {
in[mp[i]] = 0;
swap(mp[i], mp.back());
mp.pop_back(); i--;
}
sort(all(mp));
ls = rs = res = 0;
for(auto& c : mp){
if(!c) continue;
ll n = r - l + 1, t = cnt[c];
x = (t + 1) / 2; y = t - x;
res += (n * n + c) * t;
res -= cal(ls, x, c) + cal(n - ls - c - (x - 1) * c, x, c);
res -= cal(rs, y, c) + cal(n - rs - c - (y - 1) * c, y, c);
ls += x * c; rs += y * c;
if(x > y) swap(ls, rs);
}
ans[q[i].i] = res / 2;
}
for(int i = 0; i < Q; i++) cout << ans[i] << '\n';
return 0;
}
