#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ld long double
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
const int N=300007;
int a[N];
int ile[N];
int cnt[N];
struct qry
{
int l,r,i;
};
const int S=sqrt(300000);
bool cmp(qry l,qry r)
{
if(l.l/S==r.l/S) return l.r<r.r;
return l.l/S<r.l/S;
}
ll ans[N];
bool was[N];
ll pref[N];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++) pref[i]=pref[i-1]+(ll)i*(ll)(i+1)/2;
for(int i=1;i<=n;i++) cin>>a[i];
vector<qry>Q;
for(int i=1;i<=q;i++)
{
int l,r;
cin>>l>>r;
Q.pb({l,r,i});
}
sort(all(Q),cmp);
vector<int>is;
int l=1,r=0;
for(auto x:Q)
{
while(r<x.r)
{
r++;
cnt[ile[a[r]]]--;
ile[a[r]]++;
cnt[ile[a[r]]]++;
is.pb(ile[a[r]]);
}
while(r>x.r)
{
cnt[ile[a[r]]]--;
ile[a[r]]--;
cnt[ile[a[r]]]++;
is.pb(ile[a[r]]);
r--;
}
while(l>x.l)
{
l--;
cnt[ile[a[l]]]--;
ile[a[l]]++;
cnt[ile[a[l]]]++;
is.pb(ile[a[l]]);
}
while(l<x.l)
{
cnt[ile[a[l]]]--;
ile[a[l]]--;
cnt[ile[a[l]]]++;
is.pb(ile[a[l]]);
l++;
}
vector<int>nis;
for(auto i:is)
{
if(i==0||cnt[i]==0) continue;
if(!was[i]) nis.pb(i);
was[i]=1;
}
is=nis;
sort(all(is));
vector<pair<ll,ll>>V1,V2,V;
int s=0;
for(auto i:is)
{
// cout<<i<<" "<<cnt[i]<<endl;
was[i]=0;
if(s%2==0)
{
V1.pb({cnt[i]/2+cnt[i]%2,i});
if(cnt[i]>1) V2.pb({cnt[i]/2,i});
}
else
{
if(cnt[i]>1) V1.pb({cnt[i]/2,i});
V2.pb({cnt[i]/2+cnt[i]%2,i});
}
s+=cnt[i];
}
for(auto i:V1) V.pb(i);
reverse(all(V2));
for(auto i:V2) V.pb(i);
ll res=0,sum=0,S=0;
// cout<<x.i<<endl;
for(auto x:V)
{
// cout<<x.st<<" "<<x.nd<<" "<<res<<" "<<sum<<" "<<S<<endl;
res+=x.st*x.nd*(x.nd+1)/2;
// cout<<res<<endl;
res+=S*x.st*x.nd;
// cout<<res<<endl;
res+=sum*(x.st)*(x.st+1)/2*x.nd;
// cout<<res<<endl;
res+=(pref[x.st]-x.st)*x.nd*x.nd;
// cout<<res<<endl;
S+=x.st*sum;
S+=x.nd*x.st*(x.st+1)/2;
sum+=x.st*x.nd;
}
ans[x.i]=res;
}
for(int i=1;i<=q;i++) cout<<ans[i]<<endl;
return 0;
}
