#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#ifndef ONLINE_JUDGE
// #include "debug.h"
#else
#define dbg(...) 42
template<typename T>ostream&operator<<(ostream&os,vector<T>&vec){for(int i=0;i+1<vec.size();++i){os<<vec[i]<<" ";}if(vec.size()>0)os<<vec.back();return os;}
#endif
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename T>istream&operator>>(istream&is,vector<T>&vec){for(T&element:vec){is>>element;}return is;}
template<typename T>void chmin(T&x,T y){x=min(x,y);}
template<typename T>void chmax(T&x,T y){x=max(x,y);}
const int N = 3e5+6;
const int Qn = 1337;
const int block = 2000;
int ar[N];
int qu_lengths[Qn];
int qu_cnt[Qn];
int cnt[N];
int mp[N];
int64_t qAns[N];
bitset<N> bs;
set<int> lengths;
void rem_c(int c) {
mp[c]--;
if (mp[c] == 0) bs[c] = 0;
}
void add(int val) {
if (cnt[val] != 0)
rem_c(cnt[val]);
cnt[val]++;
mp[cnt[val]]++;
if (mp[cnt[val]] == 1) bs[cnt[val]] = 1;
}
void rem(int val) {
rem_c(cnt[val]);
cnt[val]--;
if (cnt[val] != 0) {
mp[cnt[val]]++;
if (mp[cnt[val]] == 1) bs[cnt[val]] = 1;
}
}
struct segment {
int length;
int diffs;
int64_t ans;
int64_t ans_left;
int64_t ans_right;
};
segment merge_two(segment A, segment B) {
if (A.length == 0) return B;
if (B.length == 0) return A;
segment res;
res.diffs = A.diffs + B.diffs;
res.length = A.length + B.length;
res.ans_right = B.ans_right + 1ll*A.ans_right + 1ll*(B.diffs)*A.length;
res.ans_left = A.ans_left + 1ll*B.ans_left + 1ll*(A.diffs)*B.length;
res.ans = A.ans + B.ans + 1ll*A.ans_right*B.length + 1ll*B.ans_left*A.length;
return res;
}
segment form_one(int length, int cnt) {
segment cur = segment{length, 1, 1ll*length*(length+1)/2, length, length};
segment res = {0, 0, 0, 0, 0};
for (; cnt > 0; cnt >>= 1) {
if (cnt & 1) {
res = merge_two(res, cur);
}
cur = merge_two(cur, cur);
}
return res;
}
void go(int ind) {
vector<int> lengths;
for (int i = bs._Find_first(); i < bs.size(); i = bs._Find_next(i)) lengths.push_back(i);
memset(qu_lengths, 0, sizeof(qu_lengths));
memset(qu_cnt, 0, sizeof(qu_cnt));
bool odd_to_left = true;
int ptr = 0;
for (int le : lengths) {
int c = mp[le];
int to_left = c / 2;
int to_right = c / 2;
if (c % 2 != 0) {
if (odd_to_left) {
to_left++;
}
else {
to_right++;
}
odd_to_left ^= 1;
}
qu_lengths[ptr] = le;
qu_lengths[Qn - ptr - 1] = le;
qu_cnt[ptr] = to_left;
qu_cnt[Qn - ptr - 1] = to_right;
++ptr;
}
segment res{0, 0, 0, 0, 0};
for (int i = 0; i < Qn; ++i) {
if (qu_cnt[i] == 0) continue;
segment now = form_one(qu_lengths[i], qu_cnt[i]);
res = merge_two(res, now);
}
qAns[ind] = res.ans;
}
void test_case(signed num) {
int n, q;
cin >> n >> q;
for (int i = 0; i < n; ++i) {
cin >> ar[i];
}
vector<array<int, 3>> queries;
for (int i = 0; i < q; ++i) {
int l, r;
cin >> l >> r;
--l, --r;
queries.push_back({l, r, i});
}
sort(queries.begin(), queries.end(), [&] (const array<int, 3>& a, const array<int, 3>& b) {
return make_pair(a[0] / block, a[1]) < make_pair(b[0] / block, b[1]);
});
int ql = 0, qr = -1;
for (int i = 0; i < queries.size(); ++i) {
while (ql > queries[i][0]) {
--ql;
add(ar[ql]);
}
while (qr < queries[i][1]) {
++qr;
add(ar[qr]);
}
while (ql < queries[i][0]) {
rem(ar[ql]);
++ql;
}
while (qr > queries[i][1]) {
rem(ar[qr]);
--qr;
}
go(queries[i][2]);
}
for (int i = 0; i < q; ++i) {
cout << qAns[i] << "\n";
}
}
signed main(void) {
cin.tie(0)->sync_with_stdio(false);
test_case(69420);
}
