#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <cmath>
#include <array>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")
using namespace std;
typedef long long ll;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
#define arr3 array<int, 3>
const int A = 3e5;
struct FT {
ll bit[A + 1], a[A + 1], s;
int n;
FT(int ns) {
n = ns;
for (int i = 1; i <= n; i++) {
bit[i] = a[i] = 0;
}
s = 0;
}
void upd(int v, ll x) {
s += x;
a[v] += x;
while (v <= n) {
bit[v] += x;
v |= (v + 1);
}
}
ll get(int v) {
ll out = 0;
while (v > 0) {
out += bit[v];
v = (v & (v + 1)) - 1;
}
return out;
}
ll get(int l, int r) {
if (l > r) return 0;
return get(r) - get(l - 1);
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
vector<arr3> qs;
for (int i = 1; i <= q; i++) {
int l, r;
cin >> l >> r;
qs.pb({l, r, i});
}
const int S = 2000;
auto cmp = [&](arr3 x, arr3 y) {
int x1 = x[0] / S, y1 = y[0] / S;
if (x1 != y1) {
return x[0] < y[0];
}
return (x1 & 1) ? (x[1] < y[1]) : (x[1] > y[1]);
};
sort(qs.begin(), qs.end(), cmp);
vector<int> p(n + 1);
for (int i = 1; i <= n; i++) {
if (i % 2) {
p[i] = (i + 1) / 2;
} else {
p[i] = n - i / 2 + 1;
}
}
ll sum = 0, s1, s2;
vector<int> f(n + 1), cnt(A + 1);
pii rr[n + 1];
rr[0] = {1, n};
for (int i = 1; i <= n; i++) rr[i] = {0, 0};
FT T1(n), T2(n);
auto add = [&](int x) {
x = a[x];
int k = cnt[x], j1 = rr[k].ss, j = p[j1];
sum += (f[j1] + 1);
s1 = T1.get(1, j - 1);
s2 = T2.get(1, j - 1);
sum += (1LL * j * s1);
sum -= (s2 - s1);
sum += (T2.s - s2 - T2.a[j]);
sum -= 1LL * (j - 1) * (T1.s - s1 - T1.a[j]);
if (rr[k].ff == rr[k].ss) rr[k] = {0, 0};
else rr[k].ss--;
cnt[x]++;
f[j1]++;
k++;
T1.upd(j, 1);
T2.upd(j, j);
if (!rr[k].ff) rr[k] = {j1, j1};
else rr[k].ff--;
};
auto rem = [&](int x) {
x = a[x];
int k = cnt[x], j1 = rr[k].ff, j = p[j1];
sum -= f[j1];
s1 = T1.get(1, j - 1);
s2 = T2.get(1, j - 1);
sum -= (1LL * j * s1);
sum += (s2 - s1);
sum -= (T2.s - s2 - T2.a[j]);
sum += 1LL * (j - 1) * (T1.s - s1 - T1.a[j]);
if (rr[k].ff == rr[k].ss) rr[k] = {0, 0};
else rr[k].ff++;
cnt[x]--;
f[j1]--;
k--;
T1.upd(j, -1);
T2.upd(j, -j);
if (!rr[k].ff) rr[k] = {j1, j1};
else rr[k].ss++;
};
vector<ll> out(q + 1);
int lc = 1, rc = 0;
for (auto [l, r, ii] : qs) {
while (lc > l) add(--lc);
while (rc < r) add(++rc);
while (lc < l) rem(lc++);
while (rc > r) rem(rc--);
out[ii] = sum;
}
for (int i = 1; i <= q; i++) {
cout << out[i] << "\n";
}
}
