#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=3e5+5,inf=1e18,minf=-1e18,lg=30,base=191;
//#undef int
int n,q;
int val[mxn+10];
struct seg{
int cnt[4*mxn+10],sum[4*mxn+10][2],sumpref[4*mxn+10][2],sumsquare[4*mxn+10][2];
int vx[4*mxn+10][2];
void build(int l,int r,int pos){
if(l==r){
for(int j=0;j<2;j++){
cnt[pos]=0;
vx[pos][j]=sum[pos][j]=sumpref[pos][j]=sumsquare[pos][j]=0;
}
return;
}
int mid=l+(r-l)/2;
build(l,mid,pos*2);
build(mid+1,r,pos*2+1);
}
void merge(int l,int r,int pos){
cnt[pos]=cnt[l]+cnt[r];
for(int j=0;j<2;j++){
int x=cnt[l]%2,cr=cnt[r]/2;
if((x^j)&&cnt[r]%2)cr++;
sum[pos][j]=sum[l][j]+sum[r][j^x];
sumpref[pos][j]=sumpref[l][j]+(sum[l][j]*cr)+sumpref[r][j^x];
sumsquare[pos][j]=sumsquare[l][j]+sumsquare[r][j^x]+(2*(sum[l][j]*sumpref[r][j^x]))
+cr*(sum[l][j]*sum[l][j]);
vx[pos][j]=vx[l][j]+vx[r][j^x]+(sum[r][j^x]*sum[l][j]);
}
}
void update(int pos,int l,int r,int qpos,int V,int C){
if(l==r){
cnt[pos]=C;
sum[pos][0]=sumpref[pos][0]=sumsquare[pos][0]=0;
sum[pos][1]=sumpref[pos][1]=V;
sumsquare[pos][1]=vx[pos][1]=V*V;
return;
}
int mid=l+(r-l)/2;
if(qpos<=mid)update(pos*2,l,mid,qpos,V,C);
else update(pos*2+1,mid+1,r,qpos,V,C);
merge(pos*2,pos*2+1,pos);
}
}t;
int root=500,cursz[mxn+10],ans[mxn+10],curans=0,ord[mxn+10];
bool cmp(pair<pii,int> a,pair<pii,int> b){
if((a.f.f/root)==(b.f.f/root))return a.f.s<b.f.s;
return (a.f.f/root)<(b.f.f/root);
}
int get(int x){return (x*(x+1))/2;}
void add(int x){
curans+=(cursz[x]*cursz[x]);
curans-=get(cursz[x]);
int pos=0;
int l=1,r=n;
while(l<=r){
int mid=l+(r-l)/2;
if(ord[mid]<=cursz[x])l=mid+1,pos=max(pos,mid);
else r=mid-1;
}
ord[pos]++;
t.update(1,1,n,pos,ord[pos],1);
cursz[x]++;
curans+=get(cursz[x]);
curans-=(cursz[x]*cursz[x]);
}
void del(int x){
curans+=(cursz[x]*cursz[x]);
curans-=get(cursz[x]);
int pos=n;
int l=1,r=n;
while(l<=r){
int mid=l+(r-l)/2;
if(ord[mid]>=cursz[x])r=mid-1,pos=min(pos,mid);
else l=mid+1;
}
ord[pos]--;
t.update(1,1,n,pos,ord[pos],(!!ord[pos]));
cursz[x]--;
curans+=get(cursz[x]);
curans-=(cursz[x]*cursz[x]);
}
int getra(int l,int r){
int ra=0;
for(int j=0;j<2;j++){
ra+=(t.sumpref[1][j]*(r-l+1));
ra-=t.sumsquare[1][j];
ra+=t.vx[1][j];
ra-=t.sum[1][j]*(r-l+1);
}
return ra;
}
/*
mo's algo would this pass??
*/
int32_t main(){
fastio
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>val[i];
vector<pair<pii,int>>qry(q);
for(int i=0;i<q;i++)cin>>qry[i].f.f>>qry[i].f.s,qry[i].s=i;
sort(all(qry),cmp);
int l=-1,r=-1;
for(int i=0;i<q;i++){
if(l==-1){
for(int c=qry[i].f.f;c<=qry[i].f.s;c++)add(val[c]);
l=qry[i].f.f,r=qry[i].f.s;
ans[qry[i].s]=(r-l+1)*(r-l+1)+curans+getra(l,r);
continue;
}
while(r<qry[i].f.s){
add(val[r+1]);
r++;
}
while(r>qry[i].f.s){
del(val[r]);
r--;
}
while(l>qry[i].f.f){
add(val[l-1]);
l--;
}
while(l<qry[i].f.f){
del(val[l]);
l++;
}
ans[qry[i].s]=(r-l+1)*(r-l+1)+curans+getra(l,r);
}
for(int i=0;i<q;i++)cout<<ans[i]<<'\n';
}
/*
3 1
1 2 3
1 3
4 2
1 1 1 1
1 2
2 4
5 3
1 2 1 3 2
2 5
1 3
3 4
5 1
1 5 1 3 5
2 5
*/
