#include <bits/stdc++.h>
using namespace std;
int n,q;
int arr[300005];
int cnt[300005];
const int sq=500;
const int sz=524288;
typedef pair<long long,long long> P;
typedef pair<P,int> Pi;
P seg[sz*2];
const int MAX=300000;
P pl(P a,P b) {
return P(a.first+b.first,a.second+b.second);
}
P sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
if (r<nodel||l>noder) {
return P(0,0);
}
if (l<=nodel&&noder<=r) {
return seg[node];
}
int mid=(nodel+noder)/2;
return pl(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
}
void update(int i,P val) {
i+=sz;
seg[i]=pl(seg[i],val);
while (i>1) {
i/=2;
seg[i]=pl(seg[i*2],seg[i*2+1]);
}
}
int pos[300005];
int tree[300005];
int sum(int i) {
i++;
int ret=0;
while (i>0) {
ret+=tree[i];
i-=(i&-i);
}
return ret;
}
void upd(int i,int val) {
i++;
while (i<=300004) {
tree[i]+=val;
i+=(i&-i);
}
}
bool comp(Pi a,Pi b) {
if (a.first.first/sq==b.first.first/sq) {
return a.first.second<b.first.second;
}
return a.first.first/sq<b.first.first/sq;
}
long long value=0;
void push(int ind) {
int now=arr[ind];
int p=sum(cnt[now])-1;
p=pos[p];
upd(cnt[now],-1);
upd(cnt[now]+1,1);
cnt[now]++;
P got=sum(0,p-1);
value+=p*got.second-got.first;
got=sum(p+1,MAX-1);
value+=got.first-p*got.second;
update(p,P(p,1));
}
void out(int ind) {
int now=arr[ind];
int p=sum(cnt[now]-1);
p=pos[p];
upd(cnt[now],-1);
upd(cnt[now]-1,1);
cnt[now]--;
P got=sum(0,p-1);
value-=p*got.second-got.first;
got=sum(p+1,MAX-1);
value-=got.first-p*got.second;
update(p,P(-p,-1));
}
long long ret[50005];
int main(void) {
scanf("%d %d",&n,&q);
for(int i=0;i<n;i++) {
scanf("%d",&arr[i]);
}
vector<int> v;
for(int i=1;i<=300000;i++) {
v.push_back(i-1);
}
sort(v.begin(),v.end());
vector<long long> v1;
for(int i=0;i<v.size();i+=2) {
v1.push_back(v[i]);
}
vector<long long> v2;
for(int i=1;i<v.size();i+=2) {
v2.push_back(v[i]);
}
reverse(v2.begin(),v2.end());
for(auto x:v2) {
v1.push_back(x);
}
for(int i=0;i<300000;i++) {
pos[v1[i]]=i;
}
upd(0,300000);
vector<Pi> query;
for(int i=0;i<q;i++) {
int l,r;
scanf("%d %d",&l,&r);
l--;
r--;
query.push_back(Pi(P(l,r),i));
}
sort(query.begin(),query.end(),comp);
int l=query[0].first.first;
int r=query[0].first.first-1;
for(int i=0;i<q;i++) {
int nl=query[i].first.first;
int nr=query[i].first.second;
while (l>nl) {
l--;
push(l);
}
while (r<nr) {
r++;
push(r);
}
while (l<nl) {
out(l);
l++;
}
while (r>nr) {
out(r);
r--;
}
int len=nr-nl+1;
ret[query[i].second]=value+1LL*len*(len+1)/2;
}
for(int i=0;i<q;i++) {
printf("%lld\n",ret[i]);
}
}
