#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll MAXN = 3e5 + 5;
const ll MAXQ = 5e4 + 5;
const ll MAX = 1e18;
const ll BLOCK = 550;
const ll MAXBLOCK = BLOCK+5;
ll n, q;
ll answer[MAXQ];
ll arr[MAXN], compressed[MAXN], ccnt[MAXN];
vector<pair<ll, pll>> blocks[MAXBLOCK];
ll freq[MAXN];
map<ll,ll> comp;
ll count(ll parity, ll n) {
ll out = 0, bef = 0;
ll nowpar = 1;
for(auto i : comp) {
// i.fi (length)
// i.se (banyak)
ll len = 0;
if(nowpar != parity) {
len = (i.se/2);
} else {
len = ((i.se+1)/2);
}
out += len*bef*bef + (len-1)*len*bef*i.fi + (len-1)*len*(2*len-1)/6*i.fi*i.fi;
out += len*(n*n + bef*bef) - 2*len*n*bef + len*(len+1)*i.fi*(bef-n) + len*(len+1)*(2*len+1)/6*i.fi*i.fi;
bef += i.fi * len;
nowpar = ((ll)nowpar+i.se) % 2;
}
return out;
}
ll calc(ll l, ll r) {
ll n = r-l+1;
ll k = 0;
for(auto i : comp) {k += i.se;}
ll out = n*k*(n+1) - n*(k-1);
ll sqSum = 0;
sqSum += count(1, n);
sqSum += count(0, n);
out = (out - sqSum) / 2;
return out;
}
bool cmp(pair<ll,pll> a, pair<ll,pll> b) {
if(a.se.se == b.se.se) {return a.se.fi < b.se.fi;}
return a.se.se < b.se.se;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> arr[i];
}
for (int i = 1; i <= q; ++i) {
pll input;
cin >> input.fi >> input.se;
blocks[input.fi/BLOCK].push_back({i, input});
}
for (int nowBlock = 0; nowBlock <= BLOCK; ++nowBlock) {
if(blocks[nowBlock].empty()) {continue ;}
sort(blocks[nowBlock].begin(), blocks[nowBlock].end(), cmp);
// Reset freq, comp
for (int i = 1; i <= n; ++i) {
freq[i] = 0;
}
comp.clear();
ll pl = 1 + nowBlock*BLOCK, pr = pl;
freq[arr[pl]]++;
comp[freq[arr[pl]]]++;
for (int i = 0; i < blocks[nowBlock].size(); ++i) {
ll ansIdx = blocks[nowBlock][i].fi;
pll range = blocks[nowBlock][i].se;
// Shift pl
while (pl < range.fi) {
if(--comp[freq[arr[pl]]] == 0) {comp.erase(freq[arr[pl]]);}
if(--freq[arr[pl]] > 0) {comp[freq[arr[pl]]]++;}
pl++;
}
while (pl > range.fi) {
pl--;
freq[arr[pl]]++;
comp[freq[arr[pl]]]++;
if(freq[arr[pl]] > 1) {
if(--comp[freq[arr[pl]]-1] == 0){
comp.erase(freq[arr[pl]]-1);
}
}
}
// Shift pr
while(pr < range.se) {
pr++;
freq[arr[pr]]++;
comp[freq[arr[pr]]]++;
if(freq[arr[pr]] > 1) {
if(--comp[freq[arr[pr]]-1] == 0){
comp.erase(freq[arr[pr]]-1);
}
}
}
answer[ansIdx] = calc(range.fi, range.se);
}
}
for (int i = 1; i <= q; ++i) {
cout << answer[i] << "\n";
}
return 0;
}
