#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FFOR(i,a,b,c) for(int i=(a);(c)>0?i<=(b):i>=(b);i+=(c))
#define FOOR(i,a,b) FFOR(i,a,b-1,1)
#define ROOF(i,a,b) FFOR(i,b-1,a,-1)
#define FOR(i,n) FOOR(i,0,n)
#define ROF(i,n) ROOF(i,0,n)
#define FORR(x,v) for(auto &x:v)
#define all(v) (v).begin(),(v).end()
#define lla(v) (v).rbegin(),(v).rend()
#define sz(v) (int)((v).size())
#define vc vector
#define pb push_back
#define ppb pop_back
#define bk back()
#define fr front()
#define pp pop()
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define bg begin()
#define en end()
#define em empty()
#define f first
#define s second
constexpr int T=300000,B=543;
int f[T+1],pos[T],lo[T+1],hi[T+1];
ll s;
struct node{
ll sum,up,dw;
int len=0;
node(){sum=up=dw=len=0;}
node(ll a){sum=a;up=dw=2*a;len=1;}
}st[2*T];
node operator+(const node &a, const node &b){
node c;
c.len=a.len+b.len;
c.sum=a.sum+b.sum;
c.up=a.up+b.up+b.sum*a.len;
c.dw=b.dw+a.dw+a.sum*b.len;
return c;
}
void update(int i,int v){
for(i+=T,st[i]=st[i].sum+v;i/=2;){
st[i]=st[i*2]+st[i*2+1];
}
}
node query(int l, int r){
node a,b;
for(l+=T,r+=T;l<r;l/=2,r/=2){
if(l&1) a=a+st[l++];
if(r&1) b=st[--r]+b;
}
return a+b;
}
void add(int v){
s-=1LL*f[v]*(f[v]+1)/2;
int p=hi[f[v]];
if(lo[f[v]]==hi[f[v]]){
lo[f[v]]=hi[f[v]]=-1;
}else hi[f[v]]--;
f[v]++;
lo[f[v]]=p;
if(hi[f[v]]==-1){
hi[f[v]]=p;
}
s+=1LL*f[v]*(f[v]+1)/2;
update(pos[p],1);
s+=query(0,pos[p]).dw+query(pos[p]+1,T).up;
}
void rem(int v){
s-=1LL*f[v]*(f[v]+1)/2;
int p=lo[f[v]];
if(lo[f[v]]==hi[f[v]]){
lo[f[v]]=hi[f[v]]=-1;
}else lo[f[v]]++;
f[v]--;
hi[f[v]]=p;
if(lo[f[v]]==-1){
lo[f[v]]=p;
}
s+=1LL*f[v]*(f[v]+1)/2;
update(pos[p],-1);
s-=query(0,pos[p]).dw+query(pos[p]+1,T).up;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
fill(lo,lo+T+1,-1);
fill(hi,hi+T+1,-1);
lo[0]=0;
hi[0]=T-1;
for(int i=0,l=0,r=T-1;i<T;i++){
pos[i]=i%2==0?l++:r--;
}
ROOF(i,T,2*T) st[i]=0;
ROOF(i,1,T) st[i]=st[i*2]+st[i*2+1];
int N,Q;
cin>>N>>Q;
vc<int> A(N);
FORR(x,A)cin>>x;
vc<tuple<int,int,int,int>> query(Q);
FOR(i,Q){
int l,r;
cin>>l>>r; l--;
query[i]={l/B,-r,l,i};
}
sort(all(query));
vc<ll> ans(Q);
int L=0,R=0;
for(auto[_,r,l,i]:query) {
r=-r;
while(l<L) add(A[--L]);
while(R<r) add(A[R++]);
while(L<l) rem(A[L++]);
while(r<R) rem(A[--R]);
ans[i]=s;
}
FORR(x,ans) cout<<x<<"\n";
return 6/22;
}
