#include <bits/stdc++.h>
using namespace std;
#define int long long
map<int, int> freq;
int val(int a, int b, int c)
{
return a*c*(a+(c-1)*b)+b*b*((((c-1)*c*(2*c-1))/6LL));
}
int get()
{
int n=0, k=0;
for(auto [i, l]: freq)
{
n+=i*l;
k+=l;
}
int mod=1;
int l=0, r=0, ans=0;
for(auto [i, j]: freq)
{
if(j<=0) continue;
int addleft=(j+mod)/2;
int addright=j-addleft;
ans+=val(l, i, addleft);
ans+=val(n-l-i, -i, addleft);
ans+=val(r, i, addright);
ans+=val(n-r-i, -i, addright);
l+=addleft*i;
r+=addright*i;
mod=(j+mod)%2;
}
return (k*n*(n+1)-n*(k-1)-ans)/2LL;
}
int32_t main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
int n, q, b=400, cnt=0; cin>>n>>q;
vector<int> a(n), ans(q);
vector<array<int, 3>> query[n/b+2];
for(int i=0; i<n; i++) cin>>a[i];
while(q--)
{
int l, r; cin>>l>>r;
l--; r--;
query[l/b].push_back({l, r, ++cnt});
}
int l=0, r=-1;
vector<int> count(3000005);
for(int i=0; i<n/b+1; i++)
{
sort(query[i].begin(), query[i].end());
for(auto x: query[i])
{
while(x[0]>l)
{
if(count[a[l]]!=0)
count[a[l]]--;
freq[count[a[l]]]++;
freq[count[a[l]]+1]--;
l++;
}
while(x[0]<l)
{
l--;
count[a[l]]++;
freq[count[a[l]]]--;
if(freq[count[a[l]]-1]>0)
freq[count[a[l]]-1]--;
}
while(x[1]<r)
{
if(count[a[r]]!=0)
freq[count[a[r]]]--;
count[a[r]]--;
freq[count[a[r]]]++;
r--;
}
while(x[1]>r)
{
r++;
if(count[a[r]]!=0)
freq[count[a[r]]]--;
count[a[r]]++;
freq[count[a[r]]]++;
}
ans[x[2]-1]=get();
}
}
for(int i=0; i<ans.size(); i++) cout<<ans[i]<<"\n";
}
