#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
int f[N];
ll ans = 0;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, q;
cin >> n >> q;
vector <int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
f[a[i]]++;
}
vector <ar <int, 2>> b;
for (int i = 1; i < N; i++) {
if (f[i] > 0) {
b.push_back({f[i], i});
}
}
sort(all(b));
vector <ar <int, 2>> c;
n = b.size();
for (int i = 0; i < n; i += 2)
c.push_back(b[i]);
for (int i = (n - 1) - ((n - 1) % 2 == 0); i > 0; i -= 2)
c.push_back(b[i]);
ll ans = 0, p = 0, ps = 0;
for (auto i : c) {
ans += 1ll * i[0] * (i[0] + 1) / 2;
ans += p * i[0];
ps += i[0];
p += i[0] + ps;
}
while (q--) {
int l, r;
cin >> l >> r;
cout << ans << '\n';
}
}
