#include <bits/stdc++.h>
using namespace std;
int L,R;
int a[300010];
long long freq[300010],freq2[300010];
bitset <300010> have;
long long calcans(){
long long ans=0,lps=0,rps=0,s=R-L+1;
for (int i=have._Find_first(); i<300010; i=have._Find_next(i)){
long long cntl,cntr;
int f;
if (lps<=rps){
f=min(freq2[i],(rps-lps)/i+1);
cntl=f+(freq2[i]-f)/2,cntr=(freq2[i]-f+1)/2;
} else {
f=min(freq2[i],(lps-rps)/i+1);
cntl=(freq2[i]-f+1)/2,cntr=f+(freq2[i]-f)/2;
}
ans+=cntl*lps*lps+cntl*(cntl+1)*lps*i+cntl*(cntl+1)/2*(2*cntl+1)/3*i*i;
ans-=s*(lps+i+lps+i*cntl)*cntl/2;
lps+=cntl*i;
long long t=s-rps;
ans+=cntr*t*t-cntr*(cntr-1)*t*i+(cntr)*(cntr-1)/2*(2*cntr-1)/3*i*i;
ans-=s*(t+t-(cntr-1)*i)*cntr/2;
rps+=cntr*i;
}
return s*(s+1)/2-ans;
}
const int BLOCK=800;
bool cmp(pair <pair <int,int>,int> a,pair <pair <int,int>,int> b){
int ax=a.first.first/BLOCK,bx=b.first.first/BLOCK;
if (ax!=bx) return ax<bx;
return a.first.second<b.first.second;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n,q;
cin>>n>>q;
for (int i=1; i<=n; i++) cin>>a[i];
pair <pair <int,int>,int> qu[q+1];
for (int i=1; i<=q; i++){
cin>>qu[i].first.first>>qu[i].first.second;
qu[i].second=i;
}
sort(qu+1,qu+q+1,cmp);
L=1; R=0;
long long op[q+1];
for (int i=1; i<=q; i++){
while (R<qu[i].first.second){
R++;
if (freq[a[R]]){
freq2[freq[a[R]]]--;
if (!freq2[freq[a[R]]]) have[freq[a[R]]]=0;
}
freq[a[R]]++;
if (!freq2[freq[a[R]]]) have[freq[a[R]]]=1;
freq2[freq[a[R]]]++;
}
while (L>qu[i].first.first){
L--;
if (freq[a[L]]){
freq2[freq[a[L]]]--;
if (!freq2[freq[a[L]]]) have[freq[a[L]]]=0;
}
freq[a[L]]++;
if (!freq2[freq[a[L]]]) have[freq[a[L]]]=1;
freq2[freq[a[L]]]++;
}
while (R>qu[i].first.second){
freq2[freq[a[R]]]--;
if (!freq2[freq[a[R]]]) have[freq[a[R]]]=0;
freq[a[R]]--;
if (freq[a[R]]&&!freq2[freq[a[R]]]) have[freq[a[R]]]=1;
freq2[freq[a[R]]]++;
R--;
}
while (L<qu[i].first.first){
freq2[freq[a[L]]]--;
if (!freq2[freq[a[L]]]) have[freq[a[L]]]=0;
freq[a[L]]--;
if (freq[a[L]]&&!freq2[freq[a[L]]]) have[freq[a[L]]]=1;
freq2[freq[a[L]]]++;
L++;
}
op[qu[i].second]=calcans();
}
for (int i=1; i<=q; i++) cout<<op[i]<<'\n';
}
