#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 300000;
ll dp[(1<<23)];
int ima[N+5];
const ll INF = 1000000000000000000LL;
const int K = 200;
const int BLOCK = 400;
struct qvry{
int l, r, ind;
bool operator <(const qvry &b){
if(l/BLOCK == b.l/BLOCK) return r < b.r;
return l/BLOCK < b.l/BLOCK;
}
};
bool ins[N+5];
int cnt[N+5];
int tren[N+5];
ll pref[K+5][N+5];
vector <int> vals;
void Dodaj(int i){
cnt[tren[i]]--;
tren[i]++;
cnt[tren[i]]++;
if(cnt[tren[i]] == 1) vals.push_back(tren[i]);
}
void Brisi(int i){
cnt[tren[i]]--;
tren[i]--;
cnt[tren[i]]++;
if(cnt[tren[i]] == 1) vals.push_back(tren[i]);
}
ll sol[N+5];
int niz[N+5];
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
for(int i=1; i<=K; i++){
for(int j=1; j<=N; j++){
pref[i][j] = 1LL*j*(j+1)/2;
if(j > i) pref[i][j] += pref[i][j-i];
}
}
int n, qrs;
cin >> n >> qrs;
vector <int> vec;
for(int i=1; i<=n; i++){
cin >> niz[i];
}
vector <qvry> queries;
for(int i=1; i<=qrs; i++){
int l, r;
cin >> l >> r;
queries.push_back({l, r, i});
}
sort(queries.begin(), queries.end());
int tl = 1, tr = 1;
Dodaj(niz[1]);
for(auto qry : queries){
int l = qry.l;
int r = qry.r;
int ind = qry.ind;
while(tr < r) tr++, Dodaj(niz[tr]);
while(tl > l) tl--, Dodaj(niz[tl]);
while(tr > r) Brisi(niz[tr]), tr--;
while(tl < l) Brisi(niz[tl]), tl++;
vector <int> nvals;
for(auto c : vals){
if(!cnt[c] || c == 0 || ins[c]) continue;
ins[c] = 1;
nvals.push_back(c);
}
swap(vals, nvals);
nvals.clear();
sort(vals.begin(), vals.end());
int tl = 0, tr = 0, bl = 0, br = 0;
int len = r - l + 1;
ll res = 0;
for(auto x : vals){
int c = cnt[x];
res += 1LL*len*(len+1)*c/2;
if(x > K){
while(c--){
if(br < bl){
res -= 1LL*tr*(tr+1)/2;
res -= 1LL*(len-tr-x)*(len-tr-x+1)/2;
tr += x;
br++;
}
else{
res -= 1LL*tl*(tl+1)/2;
res -= 1LL*(len-tl-x)*(len-tl-x+1)/2;
tl += x;
bl++;
}
}
continue;
}
if(br < bl){
res -= 1LL*tr*(tr+1)/2;
res -= 1LL*(len-tr-x)*(len-tr-x+1)/2;
tr += x;
br++;
c--;
}
int dod = (c+1)/2;
if(dod == 0) continue;
/// tl, tl + x, ..., tl + (dod-1)* x
res -= pref[x][tl + (dod-1)*x];
if(tl > x) res += pref[x][tl-x];
/// len - tl - x, len - tl - 2*x, ..., len - tl - dod*x
res -= pref[x][len - tl - x];
if(len - tl - dod*x > x) res += pref[x][len - tl - dod*x - x];
tl += dod*x;
bl += dod;
dod = c/2;
if(dod == 0) continue;
/// tr, tr + x, ..., tr + (dod-1)*x
res -= pref[x][tr + (dod-1)*x];
if(tr > x) res += pref[x][tr-x];
/// len - tr - x, len - tr - 2*x, ..., len - tr - dod*x
res -= pref[x][len - tr - x];
if(len - tr - dod*x > x) res += pref[x][len - tr - dod*x - x];
tr += dod*x;
br += dod;
}
for(auto c : vals) ins[c] = 0;
sol[ind] = res;
}
for(int i=1; i<=qrs; i++) cout << sol[i] << "\n";
return 0;
}
