# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
int n,q;
int arr[300005];
int cnt[300005];
const int sq=1000;
typedef pair<long long,long long> P;
long long tree1[300005];
long long tree2[300005];
typedef pair<P,int> Pi;
const int MAX=300000;
long long h1,h2;
P pl(P a,P b) {
return P(a.first+b.first,a.second+b.second);
}
P mi(P a,P b) {
return P(a.first-b.first,a.second-b.second);
}
inline long long sum1(int i) {
long long ret=0;
i++;
while (i>0) {
ret+=tree1[i];
i-=(i&-i);
}
return ret;
}
inline long long sum2(int i) {
long long ret=0;
i++;
while (i>0) {
ret+=tree2[i];
i-=(i&-i);
}
return ret;
}
inline P sum3(int i) {
i++;
P ret=P(0,0);
while (i>0) {
ret.first+=tree1[i];
ret.second+=tree2[i];
i-=(i&-i);
}
return ret;
}
inline void update(int i,P val) {
i++;
h1+=val.first;
h2+=val.second;
while (i<=300004) {
tree1[i]+=val.first;
tree2[i]+=val.second;
i+=(i&-i);
}
}
int pos[300005];
int tree[300005];
inline int sum(int i) {
i++;
int ret=0;
while (i>0) {
ret+=tree[i];
i-=(i&-i);
}
return ret;
}
inline 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;
inline 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=sum3(p);
long long one=got.first;
long long two=got.second;
value+=p*got.second-got.first;
got=P(h1-one,h2-two);
value+=got.first-p*got.second;
update(p,P(p,1));
}
inline 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=sum3(p);
long long one=got.first;
long long two=got.second;
value-=p*got.second-got.first;
got=P(h1-one,h2-two);
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--;
ret[i]=1LL*(r-l+1)*(r-l+2)/2;
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--;
}
ret[query[i].second]+=value;
}
for(int i=0;i<q;i++) {
printf("%lld\n",ret[i]);
}
}
