#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10,SQ=1342;// 1342
const int M=N/SQ+10;
#define ll long long
#define vl vector<ll>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
vl get_order(vl inp)
{
vl bas=inp,b,bag,bbk;
sort(all(bas));
for(int i=0;i<bas.size();i++)
{
if(i%2==0)
{
bag.pb(bas[i]);
}
else
{
bbk.pb(bas[i]);
}
}
reverse(all(bbk));
b=bag;
for(auto x:bbk)
{
b.pb(x);
}
return b;
}
int a[N],cnt[N],ccnt[N];
ll ans[N];
vector<vector<int>> query[M];
set<int> dif; // try to change to unordered
void add(int idx)
{
// cout<<endl;
// cout<<"Adding "<<a[idx]<<endl;
// cout<<endl;
if(cnt[a[idx]]!=0)
{
--ccnt[cnt[a[idx]]];
if(ccnt[cnt[a[idx]]]==0)
dif.erase(cnt[a[idx]]);
}
++cnt[a[idx]];
if(ccnt[cnt[a[idx]]]==0)
dif.insert(cnt[a[idx]]);
++ccnt[cnt[a[idx]]];
}
void rem(int idx)
{
// cout<<endl;
// cout<<"Removing "<<a[idx]<<endl;
// cout<<endl;
--ccnt[cnt[a[idx]]];
if(ccnt[cnt[a[idx]]]==0)
dif.erase(cnt[a[idx]]);
--cnt[a[idx]];
if(cnt[a[idx]] != 0)
{
if(ccnt[cnt[a[idx]]]==0)
dif.insert(cnt[a[idx]]);
++ccnt[cnt[a[idx]]];
}
}
ll f(ll x)
{
return (x*(x+1))/2;
}
ll g(ll x)
{
// f(1)+f(2)+f(3)+..+f(x)
// 2C2 + 3C2 +4C2+ .. + (x+1)C2 == x+2 C 3
return ((x+2)*(x+1)*x)/6;
}
void solve()
{
int n,q;
cin>>n>>q;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
// sort(a,a+n);
for(int id=0;id<q;id++)
{
int l,r;
cin>>l>>r;
ll len=(r-l+1);
ans[id]=(len*(len+1))/2;
l--;
int bl=l/SQ;
query[bl].push_back({r,id,l});
}
int cl=0,cr=0;
// [cl,cr)
// inclusive exclusive
for(int cb=0;cb<=(n/SQ);cb++)
{
// cl<=cr
cr=cl=0;
sort(all(query[cb]));
for(auto qry:query[cb])
{
int r=qry[0],id=qry[1],l=qry[2];
while(cl<l)
{
rem(cl);
cl++;
}
while(l<cl)
{
cl--;
add(cl);
}
while(cr<r)
{
// cout<<"Do "<<cr<<' '<<a[cr]<<endl;
add(cr);
cr++;
}
int tl=0;
// cout<<"Range "<<cl<<' '<<cr<<endl;
// cout<<l<<' '<<r<<endl;
vector<pair<ll,ll>> part[2]={};// array is compressed
// RLE
// (x,c) x appear c times
// cout<<"Query "<<l<<' '<<r<<" index "<<id<<endl;
for(auto x:dif) // O(sqrt(N))
{
// cout<<"Cnt of cnt = "<<x<<" is "<<ccnt[x]<<endl;
part[tl%2].pb({x,(ccnt[x]+1)/2});
part[1-tl%2].pb({x,ccnt[x]/2});
tl=(tl+ccnt[x])%2;
}
// reverse(all(part[1]));// O(sqrt(N))
for(int j=part[1].size();j>=1;j--)
{
part[0].pb(part[1][j-1]);
}
ll len=r-l;
ll sm=0;
ll cu=0;
// f(x) = x*(x+1)/2
// cout<<"Order: ";
for(auto xp:part[0])
{
// cout<<xp.first<<' '<<xp.second<<endl;
// Val cu Val to add sm
// cu+1*xp.first len-cu-1*xp.first
// cu+2*xp.first 2*len-2*cu-(1+2)*xp.first
// cu+3*xp.first 3*len-3*cu-(1+2+3)*xp.first
// . .
// . .
// . .
// xp.second*xp.first xp.second*len-xp.second*cu-f(xp.second)*xp.first
sm+=(xp.second*len-xp.second*cu-f(xp.second)*xp.first);
cu+=(xp.second*xp.first);
}
cu=0;
for(auto xp:part[0])
{
// xp = (x,y)
//ans[id] + 1*x*sm cu+x sm-len+cu+x
//ans[id] + 2*x*sm - x*len + x*cu + x*x cu+2*x sm-2*len+2*cu+f(2)*x
//ans[id] + 3*x*sm - f(2)*x*len + f(2)*x*cu + (f(1)+f(2))*x*x cu+2*x sm-3*len+3*cu+f(3)*x
// .
// .
// .
// .
// ans[id]= y*x*sm - f(y-1)*x*len + f(y-1)*x*cu + (f(1)+f(2)+..+f(y-1))*x*x
ll x=xp.first;
ll y=xp.second;
ans[id]+=y*x*sm - f(y-1)*x*len + f(y-1)*x*cu + (g(y-1))*x*x;
sm-=y*len;
sm+=(y*cu);
sm+=(f(y)*x);
cu+=(x*y);
}
// for(auto x:b)
// {
// fnl+=(x*sm);
// cu+=x;
// sm-=(len-cu);
// }
// return fnl;
}
while(cl<cr)
{
rem(cl);
cl++;
}
// cout<<"Left with "<<cl<<' '<<cr<<' '<<dif.size()<<endl;
}
for(int i=0;i<q;i++)
{
cout<<ans[i]<<'\n';
}
// cout<<endl;
// ll fnl=0;
// // for(int i=0;i<n;i++)
// // {
// // set<int> cur;
// // for(int j=i;j<n;j++)
// // {
// // cur.insert(a[j]);
// // fnl+=(ll)cur.size();
// // }
// // }
// vl xp;
// for(int i=1;i<N;i++)
// {
// if(cnt[i])
// {
// xp.pb(cnt[i]);
// }
// }
// // sort(all(xp));
// xp=get_order(xp);
// int m=xp.size();
// vl pre(m+2),suf(m+2);
// ll cp=0;
// for(int i=1;i<=m;i++)
// {
// pre[i]=pre[i-1]+xp[i-1];
// cp+=(n-pre[i]);
// }
// for(int i=0;i<m;i++)
// {
// fnl+=(xp[i]*cp);
// cp-=(n-pre[i+1]);
// }
// fnl+=((n*(n+1))/2);
// cout<<fnl<<endl;
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
